Introduction to Computer Science      COMP 250       Fall 2016

Instructor: Professor Michael Langer
Office hours (ENGMC 329) : MWF 3:00-4:15 pm or by appt.

Lectures MWF  4:35-5:25 pm       Adams Auditorium (FDA)


Announcements
  • Final exam held in GYM Fieldhouse Dec. 14, 2pm
Resources
LECTURES EXERCISES, ASSIGNMENTS, EXAMS
Preliminaries
  1. introductions (slides)
  2. grade school algorithms for arithmetic  (notes)   (slides)
  3. binary numbers  (notes)   (slides)

Exercises 1: number representations (PDF )

Assignment 1 (PDF)   (code)   (grading)   (Tester)   (solutions)

Lists
  1. array list (notes)   (slides)
  2. singly linked lists  (notes)   (slides)  
  3. doubly linked lists  (notes)   (slides)  
  4. bubble, selection, & insertion sort (notes)   (slides)  
  5. stacks (notes)   (slides)  
  6. queues (notes)   (slides)

Exercises 2: arrays (PDF )

Exercises 3: linked lists (PDF )   (code)   E3 Q2 figures  

Exercises 4: O(n^2) sorting (PDF )

Exercises 5: stacks and queues (PDF )
Mathematical Tools for Analysis of Algorithms
  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
  5. recurrences 1 (notes)   (slides)
    back substitution method, examples
  6. recurrences 2 (notes)   (slides)
    mergesort, quicksort, properties of logarithms (review)
  7. big O (notes)   (slides)
  8. big Omega, big Theta (notes)   (slides)



Assignment 2 (PDF) (code)

Exercises 6: induction and recursion (PDF )


Test 1 with solutions

Exercises 7: recurrences (PDF )

Exercises 8: big O (PDF )
Trees, Heaps, Maps, Graphs
  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. more on asymptotic bounds (NEW notes)   (slides)
  6. priority queue, heaps 1 (notes)   (slides)
  7. heaps 2 (notes)   (slides)
  8. heaps 3 (notes)   (slides)
  9. maps, hash codes (notes)   (slides)
  10. hash tables (notes)   (slides)  
  11. graphs (notes)   (slides)
  12. graph traversal (breadth vs depth first) (notes)   (slides)

Exercises 9: trees (PDF )

    Assignment 3 (PDF)   (code)

Exercises 10: heaps (PDF )

Exercises 11: hashing (PDF)

    Test 2 with solutions

    Assignment 4 (PDF)   (code)

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)

  6. This lecture is part of Graph material.
  7. graph applications (slides)
    garbage collection (mark and sweep), Google search (pagerank)



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