Computer Science 385
Design and Analysis of Algorithms
Spring 2017, 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 17 | Lecture 1: Introduction To Algorithms; Lab 1: Counting Operations [PDF] | Class Handout: Basics of Algorithm Analysis; Levitin Ch. 1.2-1.4, 2.3 |
| January 20 | Lecture 2: Graph Structures | Class Handout: Graphs |
| January 23 | Lecture 3: More Graphs | |
| January 24 | Lab 2: Introduction to METAL Graph Data | |
| January 27 | Lecture 4: Asymptotic Analysis; Homework Set 1 Out | Topic Notes: Analysis Fundamentals; Levitin Ch. 2.1-2.2 |
| January 30 | Lecture 5: Asymptotic Analysis | |
| January 31 | Lab 3: Algorithm Analysis Practice | |
| February 3 | Lecture 6: Brute-Force Algorithms | Topic Notes: Brute-Force Algorithms; Levitin Ch. 3 |
| February 6 | Lecture 7: Brute-Force Algorithms | |
| February 7 | Lab 4: Brute-Force Algorithms [PDF] | |
| February 10 | Lecture 8: Depth-First Search; Homework 1 Due | Class Handout: DFS/BFS |
| February 13 | Lecture 9: Review; More Practice with Brute Force | Class Handout: Review Problems |
| February 13 | Optional Exam 1 Review, 7:00 PM, RB 328 | |
| February 14 | Exam 1, during lab meetings (Happy Valentine's Day!) | |
| February 17 | No Class | |
| February 20-24 | No Classes: President's Week Break | |
| February 27 | Lecture 10: Decrease and Conquer Algorithms | Topic Notes: Decrease and Conquer Algorithms; Levitin Ch. 2.4, 4 |
| February 28 | Lab 5: Recurrence Formulas and Binary Search [PDF] | |
| March 3 | Lecture 11: More Decrease and Conquer; Introduction to Divide and Conquer; Homework Set 2 Out | Topic Notes: Divide and Conquer Algorithms; Levitin Ch. 5 |
| March 6 | Lecture 12: Divide and Conquer | |
| March 7 | Lab 6: Divide/Decrease and Conquer Algorithms [PDF] | |
| March 10 | No Class: College Holiday | |
| March 13 | Lecture 13: Binary Trees; 2-3 Trees | |
| March 14 | Lab snowed out: see Blackboard for what you need to do | |
| March 17 | Lecture 14: More Divide and Conquer; Homework 2 Due | |
| March 20 | Lecture 15: Hashing | Levitin Ch. 7.3 |
| March 20 | Optional Exam 2 Review, 7:00 PM, RB 340 | |
| March 21 | Exam 2, during lab meetings | |
| March 24 | Lecture 16: Greedy Algorithms | Topic Notes: Greedy Algorithms; Levitin Ch. 9 |
| March 27 | Lecture 17: Greedy Algorithms | Topic Notes: Dijkstra's Algorithm Handout |
| March 28 | Lab 8: Greedy Algorithms [HTML] [PDF] | |
| March 31 | Lecture 18: Implementing Graph Algorithms; Homework Set 3: [HTML] [PDF] Out | |
| April 3 | Lecture 19: Dynamic Programming | |
| April 4 | Lab 9: Dynamic Programming [PDF] | |
| April 7 | Lecture 20: Dynamic Programming | |
| April 10 | Lecture 21: Exam Review; Homework 3 Due | |
| April 11 | Exam 3, during lab meetings | |
| April 14 | No Class: Happy Easter! | |
| April 17 | No Class: Happy Easter! | |
| April 18 | Lab 10: Limitations of Algorithm Power [PDF] | |
| April 21 | Lecture 22: Backtracking | Topic Notes: Backtracking; Levitin Ch. 12.1 |
| April 24 | Lecture 23: P, NP, and NP-Complete Problems | Levitin Ch. 11.3 |
| April 25 | Lab 11: Backtracking [HTML] [PDF] | |
| April 28 | Lecture 24: P, NP, and NP-Complete Problems | |
| May 1 | Lecture 25: Wrapup; Final Exam Information | |
| May 5 | Final Exam, 8:30-10:30 AM, RB 250 and RB 302 | |