Introduction to Computer Science      COMP 250       Fall 2017

Instructor: Professor Michael Langer

Office hours :           MWR 13:00-14:00         ENGMC 329                  

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


Resources (New)
Resources (Old)
LECTURES   (Links with yellow font are from Fall 2016 and will be updated) EXERCISES, ASSIGNMENTS
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)

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)
    examples: factorial & Fibonacci, reverse/sort list, Tower of Hanoi
  3. recursion 2 (notes)   (slides)
    binary search, recursion & call stack
  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
  2. recurrences 2 (notes)   (slides)
    mergesort, quicksort, properties of logarithms (review)
  3. big O (notes)   (slides)
  4. big Omega, big Theta (notes)   (slides)
  5. best and worst case, using limits (notes)   (slides)


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 tables (notes)   (slides)  
  10. graphs (notes)   (slides)
  11. graph traversal (breadth vs depth first) (notes)   (slides)
  1. graph applications 1 (slides)
    garbage collection (mark and sweep)
  2. graph applications 2
    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. interfaces (notes)   (slides)
  2. inheritance (notes)   (slides)
  3. abstract classes, casting (notes)   (slides)
  4. polymorphism (notes)   (slides)
  5. modifiers (notes)   (slides)



Exercises 13: object oriented design (PDF)
EXTRA (not on final exam)
  1. grad school (slides)
  2. beyond COMP 250, tips for final exam (slides)