Introduction to Computer Science      COMP 250       Fall 2017

Instructor: Professor Michael Langer

Lectures:           MWF  10:35-11:25         MCMED 522            
           MRF  14:35-15:25     MDHAR G-10


  Prof. Langer Office hours (ENGMC 329):   MWR 13:00-14:00

  T.A. Office hours (Trottier 3090) for Lecture/Quiz/Exercises:
  • Data structures (lec. 4-9, 19-29):
    • Tue 11:30 - 13:00 (Roman)
    • Thu 11:30 - 13:00 (Jeremy)
  • Preliminaries (lec 1-3), Induction...bigO (lec. 10-18), OOD (lec. 30-34)
    • Monday 12-1:30 (Caitrin)
    • Tuesday 10:00-11:00 (Caitrin)
    • Tue 11:30 - 13:00 (Roman )
Resources
LECTURES   (Links with yellow font are from Fall 2016 and will be updated) EXERCISES (with solutions)
Preliminaries
  1. introductions (slides)
  2. grade school algorithms for arithmetic  (notes)   (slides)
  3. binary numbers  (notes)   (slides)
  4. Eclipse IDE and debugging tutorial   (example code)   (slides)




Exercises 1: grade school arithmetic, number representations (PDF)
Linear Data Structures
  1. array list (notes)   (slides)
  2. singly linked lists  (notes)   (slides)  
  3. doubly linked lists  (notes)   (slides)  
  4. list sorting algorithms (notes)   (slides)  
    bubble, selection, & insertion sort
  5. stacks (notes)   (slides)  
  6. 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
  1. mathematical induction (notes)   (slides)
  2. recursion 1 (notes)   (slides)
    factorial & Fibonacci, reverse/sort list, Tower of Hanoi; call stack
  3. recursion 2 (notes)   (slides)
    power, binary search
  4. recursion 3 (notes)   (slides)
    mergesort, quicksort

Exercises 6: induction and recursion (PDF)
Mathematical Tools for Analysis of Algorithms
  1. recurrences 1 (notes)   (slides)
    back substitution method, examples, brief review of logarithms
  2. recurrences 2 (notes)   (slides)
    mergesort, quicksort
  3. big O   1 (notes)   (slides)
    analogy to limits in Calculus, formal big O definition
  4. big O   2 (notes)   (slides)
    rules for big O, big Omega, some incorrect proofs
  5. 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
  1. rooted trees (notes)   (slides)
  2. tree traversal (notes)   (slides)
  3. binary trees e.g. expression trees (notes)   (slides)
  4. binary search trees (notes)   (slides)
  5. priority queue, heaps 1 (notes)   (slides)
  6. heaps 2 (notes)   (slides)
  7. heaps 3 (notes)   (slides)
  8. maps, hash codes (notes)   (slides)
  9. hash maps (notes)   (slides)  
  10. graphs (notes)   (slides)
  11. graph traversal (breadth vs depth first) (notes)   (slides)
  1. graph applications (slides)
    garbage collection (mark and sweep), Google search (pagerank)



Exercises 9: trees (PDF)



Exercises 10: heaps (PDF)


Exercises 11: hashing (PDF)


Exercises 12: graphs (PDF)
Object Oriented Design in Java
  1. inheritance (notes)   (slides)
  2. interfaces (notes)   (slides)
  3. abstract classes, casting (notes)   (slides)
  4. polymorphism (notes)   (slides)
  5. modifiers (notes)   (slides)



Exercises 13: object oriented design (PDF)
EXTRA
  1. grad school (slides)
  2. review session for final exam
  3. beyond COMP 250 (slides)