Computer Science 385
Design and Analysis of Algorithms
Spring 2019, Siena College
"Levitin" indicates readings from Introduction to The Design and Analysis of Algorithms, Third Edition, by Anany Levitin, "Bailey" from Java Structures: Data Structures in Java for the Principled Programmer, "Root 7" Edition, by Duane Bailey. Additional readings will be given occasionally. Links will be added here with additional information about lectures and problem sets. All assignment dates are subject to change, and are provided only as a general guideline until the actual assignment is handed out in class.
|
Date | Topic and/or Event | Readings |
| January 14 | Lecture 1: Introduction and Overview; Lab 0: GitHub Setup | Topic Notes: Introduction and Overview; Topic Notes: Fundamental Data Structures; Levitin Ch. 1.2-1.4, 2.3; Graph structures introductory video (see link in email) |
| January 15/16 | Lecture 2: Bubble Sort; Counting Operations; Lab Meeting #1; Lab 1: Counting Operations (paper handout only) | Knuth article: NYT Site or Library Archive |
| January 18 | Lecture 3: Graph Data Structures | Bailey Ch. 16.1-16.3 |
| January 21 | No class: MLK Jr. Day | |
| January 22/23 | Lecture 4: Lab Meeting #2; Lab 2: Introduction to METAL Graph Data | |
| January 25 | Lecture 5: Asymptotic Analysis; Problem Set 1: [PDF] Out | Topic Notes: Analysis Fundamentals; Levitin Ch. 2.1-2.2 |
| January 28 | Lecture 6: Asymptotic Analysis | |
| January 29/30 | Lecture 7: Lab Meeting #3; Lab 3: Algorithm Analysis Practice (paper handout only) | |
| February 1 | Lecture 8: Brute-Force Algorithms | Topic Notes: Brute-Force Algorithms; Levitin Ch. 3 |
| February 4 | Lecture 9: Brute Force and Exhaustive Search; Quiz 1; Problem Set 2: [PDF] Out | |
| February 5/6 | Lecture 10: Lab Meeting #4; Lab 4: Brute-Force Algorithms (paper handout only) | |
| February 8 | Lecture 11: Exhaustive Search | |
| February 11 | Lecture 12: Decrease and Conquer Algorithms; Recurrences; Quiz 2 | Topic Notes: Decrease and Conquer Algorithms; Levitin Ch. 2.4, 4 |
| February 12/13 | Lecture 13: Lab Meeting #5; Lab 5: Graph Traversals (paper handout only) | |
| February 15 | Lecture 14: Solving Recurrences | |
| February 18 | Lecture 15: More Recurrences; Review | |
| February 19 | Exam 1, RB 302, 2:35-4:35 or RB 202, Start between 6 and 8 PM, done between 8 and 10 PM | |
| February 19/20 | No labs: Evening exam instead | |
| February 22 | Lecture 16: Decrease and Conquer Wrapup; Problem Set 3: [HTML] [PDF] out | |
| February 25 | No Class: Winter Break | |
| February 26/27 | No Labs: Winter Break | |
| March 1 | No Class: Winter Break | |
| March 4 | Lecture 17: Divide and Conquer; Problem Set 4: [PDF] Out; Academic Showcase Project: [HTML] [PDF] Introduction | Topic Notes: Divide and Conquer Algorithms; Levitin Ch. 5 |
| March 5/6 | Lecture 18: Lab Meeting #6; Lab 6: Working With Recurrences | |
| March 8 | Lecture 19: Divide and Conquer Algorithms | |
| March 11 | Lecture 20: 2-3 Trees; AVL Tree Review | Topic Notes: Binary Search Trees; Topic Notes: 2-3 Trees; Levitin Ch. 6.3 |
| March 12/13 | Lecture 21: Lab Meeting #7; Lab 7: Divide and Conquer | |
| March 15 | Lecture 22: Hashing; Dynamic Programming | ; Levitin Ch. 7.3; Topic Notes: Hashing; Levitin Ch. 8; Topic Notes: Dynamic Programming |
| March 18 | Lecture 23: More Dynamic Programming; Problem Set 5: [PDF] Out | |
| March 19/20 | Lecture 24: Lab Meeting #8; Lab 8: Search Trees and Dynamic Programming | |
| March 22 | Lecture 25: Problem Set Recap; Dynamic Programming Practice; Quiz 3 | Levitin Ch. 8.4 |
| March 25 | Lecture 26: Greedy Algorithms | Topic Notes: Greedy Algorithms; Levitin Ch. 9 |
| March 26/27 | Lecture 27: Lab Meeting #9; Lab 9: More Dynamic Programming (and Some Heaps) | Levitin Ch. 6.4-6.5; Topic Notes: Heaps |
| March 29 | No Class: Siena President's Holiday, but thanks for all the help with the HS programming contest! | |
| April 1 | Lecture 28: Problem Set Recap and Exam Review | |
| April 2 | Exam 2, RB 302, 2:35-4:35, or RB 202, Start between 6 and 8 PM, done between 8 and 10 PM | |
| April 2/3 | No Labs: Exam Week | |
| April 5 | Lecture 29: Dijkstra's Algorithm; Backtracking; Problem Set 6: [PDF] Out | Topic Notes: Dijkstra's Algorithm Handout; Topic Notes: Backtracking; Levitin Ch. 12.1 |
| April 8 | Lecture 30: Backtracking; Exam 2 Recap; Quiz 4 | |
| April 9/10 | Lecture 31: ; Lab 10: Greedy Algorithms/Backtracking | |
| April 12 | Lecture 32: Limitations of Algorithms | Levitin Ch. 11; Topic Notes: Limitations of Algorithms; |
| April 15 | Lecture 33: Limitations of Algorithms: Tractability | |
| April 16/17 | No Labs: Happy Easter! | |
| April 19 | No Class: Happy Easter! | |
| April 22 | No Class: Happy Easter! | |
| April 23/24 | Lecture 34: Lab Meeting #11; Lab 11: Limitations of Algorithm Power | |
| April 26 | Academic Showcase: Our Session 2:30-3:30 in RB 340 | |
| April 29 | Lecture 35: P and NP; Wrapup; Quiz 5 | |
| May 1 | Final Exam, 8:30-10:30 AM, RB 202 | |