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


LECTURES (All Fall 2017 lecture notes bundled together) 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 lists (notes)   (slides)
  2. singly linked lists  (notes)   (slides)  
  3. doubly linked lists  (notes)   (slides)  
  4. iterative 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: iterative 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 [Fall 2018: see updated lecture notes for recurrences] (PDF)
  2. recurrences 2

  3. big O         [Fall 2018: see updated lecture notes for big O, Omega, Theta] (PDF)
  4. big Omega
  5. big Theta


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. heaps 1 [Fall 2018: I covered heaps in two lectures only. See (PDF)
  6. heaps 2
  7. heaps 3
  8. maps, hash codes (notes)   (slides)
  9. hash maps (notes)   (slides)  
  10. graphs (notes)   (slides)
  11. 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
  1. inheritance (notes)   (slides)
  2. interfaces, abstract classes (notes)   (slides)
  3. examples of interfaces (notes)   (slides)
    Comparable, Iterable, Iterator
  4. type conversion, polymorphism, Class class (notes)   (slides)
  5. garbage collection (notes)   (slides)
    mark and sweep
  6. coding tutorial on OOD (Caitrin)
  7. modifiers (notes)   (slides)



Exercises 13: object oriented design (PDF)
EXTRA
  1. why (or why not) go to grad school ?
  2. beyond COMP 250, final exam (slides)