Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Course Schedule

"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