Computer Science 385
Design and Analysis of Algorithms
Spring 2025, 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 21 | Lecture 1: Introduction and Overview; Lab Meeting #0; Lab 0: Data Structures Refresher; In-class Introductory Topics Handout | Topic Notes: Introduction and Overview; Topic Notes: Fundamental Data Structures; Levitin Ch. 1 |
| January 24 | Lecture 2: Bubble Sort; Counting Operations; GCD; Bubble Sort Introduction; Summations Practice | Levitin Ch. 2.3; Topic Notes: Counting Operations |
| January 27 | Lecture 3: Graph Data Structures; In-class Graph Structures Intro Handout | Bailey Ch. 16.1-16.3 |
| January 28 | Lecture 4: Lab Meeting #1; Lab 1: Counting Operations, Graphs (paper handout only) | Knuth article: NYT Site or Library Archive also in Canvas |
| January 31 | Lecture 5: Asymptotic Analysis; Analysis Practice | Topic Notes: Analysis Fundamentals; Levitin Ch. 2.1-2.2 |
| February 3 | Lecture 6: Asymptotic Analysis | |
| February 4 | Lecture 7: Lab Meeting #2; Lab 2: METAL Data and Analysis Practice (paper handout and shared document) | |
| February 7 | Lecture 8: Brute-Force Algorithms; Brute Force Practice | Topic Notes: Brute-Force Algorithms; Levitin Ch. 3 |
| February 10 | Lecture 9: Brute Force/Exhaustive Search; Exhaustive Search Practice | Topic Notes: Exhaustive Search |
| February 11 | Lecture 10: Lab Meeting #3; Lab 3: Brute-Force Closest Pair (paper handout and shared document) | |
| February 14 | Lecture 11: Brute-Force Convex Hull | |
| February 17 | Lecture 12: Decrease and Conquer Algorithms; Recurrences; Decrease and Conquer Practice | Topic Notes: Decrease and Conquer Algorithms; Topic Notes: Analysis with Recurrences; Levitin Ch. 2.4, 4 |
| February 18 | Lecture 13: Lab Meeting #4; Lab 4: Brute Force and Decrease and Conquer (paper handout only) | |
| February 21 | Lecture 14: Solving Recurrences | |
| February 24 | Lecture 15: Exam 1 Review; More Decrease and Conquer | |
| February 25 | Exam 1 During Lab Meeting Times | |
| February 28 | No Class: SIGCSE 2025 | |
| March 3-7 | No Classes or Labs: Spring Break! | |
| March 10 | Lecture 16: Exam 1 Recap; Decrease and Conquer Wrapup; Divide and Conquer Introduction; Mergesort Practice | Topic Notes: Divide and Conquer Algorithms; Levitin Ch. 5 |
| March 11 | Lecture 17: Graph Traversals Intro; Lab Meeting #5; Lab 5: Graph Traversals (shared document only) | |
| March 14 | Lecture 18: More Divide and Conquer; Quicksort Practice | |
| March 17 | Lecture 19: More Divide and Conquer; Academic Showcase Project Introduction | |
| March 18 | Lecture 20: Lab Meeting #6; Lab 6: Recurrences and Divide and Conquer (paper handout only) | |
| March 21 | Lecture 21: D&C Closest Pair Wrapup; AVL Trees; Balanced Trees Practice | Topic Notes: Balanced Trees |
| March 24 | Lecture 22: AVL Trees; 2-3 Trees | Levitin Ch. 6.3 |
| March 25 | Lecture 23: Lab Meeting #7; Lab 7: Search Trees | |
| March 28 | Lecture 24: Dynamic Programming; Dynamic Programming Practice | Levitin Ch. 8; Topic Notes: Dynamic Programming |
| March 31 | Lecture 25: Exam Review; Dynamic Programming | |
| April 1 | Exam 2 During Lab Meeting Times | |
| April 4 | Lecture 26: (Virtual Lecture) Hashing | Levitin Ch. 7.3; Topic Notes: Hashing |
| April 7 | Lecture 27: Greedy Algorithms | Topic Notes: Greedy Algorithms; Levitin Ch. 9 |
| April 8 | Lecture 28: Lab Meeting #8; Lab 8: Dynamic Programming | |
| April 11 | Lecture 29: Heaps | Levitin Ch. 6.4-6.5; Topic Notes: Heaps |
| April 14 | Lecture 30: Greedy Algorithms Wrapup; Backtracking | Topic Notes: Dijkstra's Algorithm Handout; Levitin Ch. 12.1 |
| April 15 | Lecture 31: Lab Meeting #9; Lab 9: Prim's Algorithm, Dijkstra's Algorithm, Traversals | |
| April 18 and 21 | No Classes: Happy Easter! | |
| April 22 | Lecture 32: Lab Meeting #10; Lab 10: Backtracking | |
| April 25 | Lecture 33: Limitations of Algorithms | Levitin Ch. 11; Topic Notes: Limitations of Algorithms |
| April 28 | Lecture 34: Limitations of Algorithms | |
| April 29 | Lecture 35: Lab Meeting #11 | |
| May 2 | Academic Showcase: TBD - this is a required part of the course | |
| May 5 | Lecture 36: P and NP; Wrapup | |
| May TBD | Final Exam, TBD | |