Class meeting time: TR 3:45 - 5:00pm @ SMH 108 Office hours: TR 1:30-3:30pm @ MSB 352, and by appointment
Office hours during finals week: Tues 12pm-2pm; Thurs 1:30pm-3:30pm, and by appointment.
This schedule is not final. It may change.
| Topics | Subtopics & Slides | Examples | Reading | Date |
|---|---|---|---|---|
| Introduction | Syllabus | |||
| Intro | 8/22 | |||
| Ch 1: Algorithm Analysis | Analysis of Algorithms | 1.1, 1.2, 1.3, 1.4 | 8/22; 8/27 | |
| Ch 2: Basic Data Structures | Elementary Data Structures | 1.5, 2.1, 2.2, 2.3 | 8/27; 8/29; 9/3 | |
| Priority Queues and Heaps | heap insert, heap removeMin | 2.4.1 - 2.4.4 | 9/3; 9/5 | |
| Dictionaries and Hash Tables | chaining, linear probing, double hashing | 2.5.1 - 2.5.6 | 9/10; 9/12 | |
| Ch 3: Search Trees and Skip Lists | Binary Search Trees | insert, find, remove | 3.1.1 - 3.1.6 | 9/12; 9/17 |
| Red-Black Trees | insert | 3.3.3 | 9/19 | |
| Ch 4: Sorting, Sets, and Selection | Merge Sort | merge sort | 4.1.1 | 9/24 |
| Quick Sort | quick sort | 4.3.1, 4.6 | 9/26 | |
| Sorting Lower Bound | 4.4 | 10/1 | ||
| Radix Sort | bucket sort, radix sort | 4.5.1, 4.5.2 | 10/1; 10/3 | |
| Sets | 4.2.1 | 10/3 | ||
| Selection | quick select | 4.7, 4.7.1 - 4.7.3 | 10/3; 10/8 | |
| Ch 5: Fundamental Techniques | Greedy Method | fractional knapsack, task scheduling | 5.1, 5.1.1, 5.1.2 | 10/22 |
| Divide and Conquer | master theorem | 5.2, 5.2.1 - 5.2.3 | 10/24; 10/29 | |
| Dynamic Programming | matrix chain product, 0-1 knapsack | 5.3, 5.3.1 - 5.3.3 | 10/31; 11/5 | |
| Ch 6: Graphs | Graphs | 6.1 - 6.2 | 11/5 | |
| Depth-First Search | dfs | 6.3.1 | 11/7 | |
| Breadth-First Search | bfs | 6.3.3 | 11/7 | |
| Biconnectivity | 6.3.2 | 11/12 | ||
| Directed Graphs | 6.4.1, 6.4.2, 6.4.4 | 11/14 | ||
| Ch 7: Weighted Graphs | Shortest Paths | dijkstra (on undirected graph), dijkstra (on digraph), dag-based, bellman-ford | 7.1, 7.1.1 - 7.1.3, 7.2, 7.2.1 | 11/19; 11/21 |
| Minimum Spanning Trees | prim-jarnik, kruskal | 7.3, 7.3.1 - 7.3.3 | 11/26; 12/3 | |
| Ch 8: Network Flow and Matching | Network Flow | ford-fulkerson, edmond-karp | 8.1.1, 8.1.2, 8.2.1 - 8.2.3 | 12/3; 12/5 |
Clearly number your solution to each problem. Staple your solutions and bring them to class on the due date. Express your algorithms in pseudo-code when directed. Always provide justification for your answer when asked to give the running time of an algorithm, or when asked to given an algorithm running in a specific time. Be brief and concise, and draw pictures where appropriate.
Sign up for Piazza, a Q&A web service where you can ask and answer questions related to the class.