Please note that some topics may take more/less time than planned and may not be covered in exactly this order.

Week | Date | Topic | Reading |
---|---|---|---|

Week1 | 7/2 | Introduction, analyzing running times, O, Omega, Theta notation, short math review |
Chapter 1: 1.2.2,1.2.3; Chapter 2: 2.1 |

7/3 | Recursion and runtime analysis: binary search, gcd, Towers of Hanoi | Chapter 2: 2.4.4 | |

7/5 | Sorting: bubble sort, insertion sort | Chapter 7: 7.2 | |

7/6 | Sorting: lowerbound on simple sorting, mergesort, comparison with quicksort | Chapter 7: 7.3, 7.6 | |

Week2 | 7/9 | Sorting: quicksort, runtime analysis, special case: bucket sort | Chapter 7: 7.7, 7.9 |

7/10 | List ADT, array and linked list implementation, hw1 due |
Chapter 3: 3.1,3.2,3.4,3.5 | |

7/11 | Generic classes and Iterator interface, Stack ADT, implementation overview | Chapter 3: 3.4,3.5,3.6 | |

7/12 | Stack applications: balancing symbols, evaluating postfix expressions. Queue ADT, array and link list implementation | Chapter 3: 3.6,3.7 | |

Week3 | 7/16 | Trees: introduction, terminology, tree properties, traversals, Binary Search Trees | Chapter 4: 4.1,4.3 |

7/17 | BST implementation. Balanced trees: AVL trees, hw2 due |
Chapter 4: 4.3, 4.4 | |

7/18 | Wrap up trees, midterm review | Chapter 4: 4.3 | |

7/19 | MIDTERM | ||

Week4 | 7/23 | Heaps | Chapter 6: 6.1-6.3 |

7/24 | Leftist heaps, heapsort, hw3 due |
Chapter 6: 6.6; Chapter 7: 7.5 | |

7/25 | Hashing: introduction, examples, collision resolution with chaining | Chapter 5: 5.1-5.3 | |

7/26 | Hashing: other collision resolution strategies, rehashing | Chapter 5: 5.4,5.5 | |

Week5 | 7/30 | Introduction to graphs, terminology, different graph representations | Chapter 9: 9.1 |

7/31 | Topological sort, Depth First Search, hw4 due |
Chapter 9: 9.2, 9.6.1 | |

8/1 | Unweighted shortest paths: Breadth First Search | Chapter 9: 9.3.1 | |

8/2 | Minimum Spanning Trees: Prim's and Kruskal's algorithms | Chapter 9: 9.5 | |

Week6 | 8/6 | Weighted shortest paths: Dijkstra's algorithm | Chapter 9: 9.3.2 |

8/7 | Dijkstra runtime analysis, final review, hw5 due |
Chapter 9: 9.3.2 | |

8/8 | Final review, course evaluations | ||

8/9 | FINAL |