COMP 250 Introduction to Computer Science Fall 2017 Instructor: Michael Langer

### ANNOUNCEMENT (Fall 2020)

Starting Fall 2020, COMP 250 no longer assumes that incoming students know Java. Rather it only assumes students know how to program in some high level language (e.g. COMP 202/204/208 teaches Python). Since Java will be used for the programming assignments, COMP 250 will begin with a crash course in Java programming. Engineering students who have learned Java in ECSE 202 should treat the first weeks of COMP 250 as a Java review.

 LECTURES (All Fall 2017 lecture notes bundled together) EXERCISES (with solutions) Preliminaries introductions (slides) grade school algorithms for arithmetic (notes) (slides) binary numbers (notes) (slides) Eclipse IDE and debugging tutorial   (example code)   (slides) Exercises 1: grade school arithmetic, number representations (PDF) Linear Data Structures array lists (notes) (slides) singly linked lists (notes) (slides) doubly linked lists (notes) (slides) iterative sorting algorithms (notes) (slides) bubble, selection, & insertion sort stacks (notes) (slides) queues (notes) (slides) + ADTs, Java API, interfaces Exercises 2: arrays and array lists (PDF) Exercises 3: linked lists (PDF)   (code)   Exercises 4: iterative sorting (PDF) Exercises 5: stacks and queues (PDF) Induction and Recursion mathematical induction (notes) (slides) recursion 1 (notes) (slides) factorial & Fibonacci, reverse/sort list, Tower of Hanoi; call stack recursion 2 (notes) (slides) power, binary search recursion 3 (notes) (slides) mergesort, quicksort Exercises 6: induction and recursion (PDF) Mathematical Tools for Analysis of Algorithms recurrences 1 (PDF: updated Fall 2018) recurrences 2 big O (PDF: updated Fall 2018)) big Omega big Theta Exercises 7: recurrences (PDF) Exercises 8: big O (PDF) Non-linear Data Structures rooted trees (notes) (slides) tree traversal (notes) (slides) binary trees e.g. expression trees (notes) (slides) binary search trees (notes) (slides) heaps 1 (PDF: updated Fall 2018) heaps 2 :s 3 maps, hash codes (notes) (slides) hash maps (notes) (slides) graphs (notes) (slides) graph traversal (breadth vs depth first) (notes) (slides) Exercises 9: trees (PDF) Exercises 10: heaps (PDF) Exercises 11: hashing (PDF) Exercises 12: graphs (PDF) Object Oriented Design in Java inheritance (notes) (slides) interfaces, abstract classes (notes) (slides) examples of interfaces (notes) (slides) Comparable, Iterable, Iterator type conversion, polymorphism, Class class (notes) (slides) garbage collection (notes) (slides) mark and sweep coding tutorial on OOD (Caitrin) modifiers (notes) (slides) Exercises 13: object oriented design (PDF) EXTRA why (or why not) go to grad school ? beyond COMP 250, final exam (slides)