Introduction to Computer Science      COMP 250       Fall 2017

Instructor: Professor Michael Langer

Lectures:     Sec. 001       MWF  10:35-11:25     MCMED 522
Sec. 002       MRF  14:35-15:25     MDHAR G-10

 Prof. Langer Office hours (ENGMC 329):   MWR 13:00-14:00 (during semester only) All lecture notes bundled together [Dec. 5, 2017]     Course Outline (Fall 2017) Resources Eclipse download     free Java book: "How to think like a computer scientist" LECTURES 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 list (notes)   (slides) singly linked lists  (notes)   (slides)   doubly linked lists  (notes)   (slides)   list 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: O(n^2) 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 (notes)   (slides) back substitution method, examples, brief review of logarithms recurrences 2 (notes)   (slides) mergesort, quicksort big O   1 (notes)   (slides) analogy to limits in Calculus, formal big O definition big O   2 (notes)   (slides) rules for big O, big Omega, some incorrect proofs big O   3 (notes)   (slides) big Theta, best and worst case, limits rules 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) priority queue, heaps 1 (notes)   (slides) heaps 2 (notes)   (slides) heaps 3 (notes)   (slides) 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)