Computer Science 385
Design and Analysis of Algorithms
Spring 2018, 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.
The complete course schedule will appear in this space soon.
|
Date | Topic and/or Event | Readings |
| January 16/17 | Lecture 1: Introduction To Algorithms; Course Overview; Lab 0: GitHub Setup; Lab 1: Counting Operations (handout) | Topic Notes: Introduction and Overview; Levitin Ch. 1.2-1.4, 2.3 |
| January 19 | Lecture 2: Graph Structures | Topic Notes: Fundamental Data Structures |
| January 22 | Lecture 3: More Graphs | |
| January 23/24 | Lab 2: Introduction to METAL Graph Data | |
| January 26 | Lecture 4: Asymptotic Analysis; Problem Set 1: [HTML] [PDF] Out | Topic Notes: Analysis Fundamentals; Levitin Ch. 2.1-2.2 |
| January 29 | Lecture 5: Asymptotic Analysis | |
| January 30/31 | Lab 3: Algorithm Analysis Practice | |
| February 2 | Lecture 6: Brute-Force Algorithms | Topic Notes: Brute-Force Algorithms; Levitin Ch. 3 |
| February 5 | Lecture 7: Brute-Force Algorithms; Quiz on Graph Structures; Problem Set 2: [PDF] Out | |
| February 6/7 | Lab 4: Brute-Force Algorithms [HTML] [PDF] | |
| February 9 | Lecture 8: Exhaustive Search | |
| February 12 | Lecture 9: Decrease and Conquer Algorithms; Recurrences | Topic Notes: Decrease and Conquer Algorithms; Levitin Ch. 2.4, 4 |
| February 13/14 | Lab 5: Graph Traversals [HTML] [PDF] | |
| February 16 | Lecture 10: More Decrease and Conquer | |
| February 19 | Lecture 11: Review; Decrease and Conquer Wrapup | |
| February 20 | Exam 1, RB 202, Start between 6 and 8 PM, done between 8 and 10 PM | |
| February 20/21 | No labs: Evening exam instead | |
| February 23 | No Classes: President's Week Break | |
| February 26 | Lecture 12: Divide and Conquer; Problem Set 3 out | Topic Notes: Divide and Conquer Algorithms; Levitin Ch. 5 |
| February 27/28 | Lab 6: Working With Recurrences [PDF] | |
| March 2 | No class: Snow day! | |
| March 5 | Lecture 13: Divide and Conquer; Problem Set 4: [PDF] Out | |
| March 6/7 | Lab 7: Decrease and Conquer and Divide and Conquer [PDF] | |
| March 9 | Lecture 14: 2-3 Trees | Topic Notes: Binary Search Trees; Topic Notes: 2-3 Trees; Levitin Ch. 6.3 |
| March 12 | Lecture 15: Hashing; Problem Set 5: [PDF] Out | Levitin Ch. 7.3 |
| March 13/14 | Lab 8: Search Trees [PDF] | |
| March 16 | Lecture 16: Dynamic Programming | Levitin Ch. 8; Topic Notes: Dynamic Programming |
| March 19 | Lecture 17: More Dynamic Programming | |
| March 20/21 | Lab 9: Dynamic Programming [PDF] | |
| March 23 | Lecture 18: Greedy Algorithms | Topic Notes: Greedy Algorithms; Levitin Ch. 9 |
| March 26 | No Class: Happy Easter! | |
| March 27/28 | No Labs: Happy Easter! | |
| March 30 | No Class: Happy Easter! | |
| April 2 | No Class: Happy Easter! | |
| April 3/4 | Lab 10: Greedy Algorithms and Heaps [PDF] | Topic Notes: Dijkstra's Algorithm Handout; Levitin Ch. 6.4-6.5; Topic Notes: Heaps |
| April 6 | Lecture 19: Quiz and Problem Set Recaps and Exam Review; Problem Set 6 Out | |
| April 9 | Lecture 20: Backtracking | Topic Notes: Backtracking; Levitin Ch. 12.1 |
| April 10 | Exam 2, Evening, RB 202, Start between 6 and 8 PM, done between 8 and 10 PM | |
| April 10/11 | No labs: Evening exam instead | |
| April 13 | Lecture 21: More Graph Algorithms | Levitin Ch. 8.4 |
| April 16 | Lecture 22: Exam 2 Recap | |
| April 17/18 | Lab 11: Backtracking [PDF] | |
| April 20 | No Class: CCSCNE 2018 | |
| April 23 | Lecture 23: Limitations of Algorithm Power | Levitin Ch. 11; Topic Notes: Limitations of Algorithms |
| April 24/25 | Lab 12: Limitations of Algorithm Power (paper handout only) | |
| April 27 | Lecture 24: Tractability | |
| April 30 | Lecture 25: More Tractability; Wrapup | |
| May 2 | Final Exam, Sarazen Great Room, start between 4:00 and 5:30 PM | |