Computer Science 385
Design and Analysis of Algorithms

Spring 2018, 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 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