Computer Science 385
Design and Analysis of Algorithms

Spring 2019, 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.

Date

Topic and/or Event Readings
January 14 Lecture 1: Introduction and Overview; Lab 0: GitHub Setup Topic Notes: Introduction and Overview; Topic Notes: Fundamental Data Structures; Levitin Ch. 1.2-1.4, 2.3; Graph structures introductory video (see link in email)
January 15/16 Lecture 2: Bubble Sort; Counting Operations; Lab 1; Lab 1: Counting Operations (paper handout only) Knuth article: NYT Site or Library Archive
January 18 Lecture 3: Graph Data Structures Bailey Ch. 16.1-16.3
January 21 No class: MLK Jr. Day
January 22/23 Lecture 4: ; Lab 2: Introduction to METAL Graph Data
January 25 Lecture 5: Asymptotic Analysis; Problem Set 1 Out Topic Notes: Analysis Fundamentals; Levitin Ch. 2.1-2.2
January 28 Lecture 6: Asymptotic Analysis
January 29/30 Lecture 7: ; Lab 3: Algorithm Analysis Practice
February 1 Lecture 8: Brute-Force Algorithms Topic Notes: Brute-Force Algorithms; Levitin Ch. 3
February 4 Lecture 9: Brute-Force Algorithms; Problem Set 2 Out
February 5/6 Lecture 10: ; Lab 4: Brute-Force Algorithms
February 8 Lecture 11: Exhaustive Search
February 11 Lecture 12: Decrease and Conquer Algorithms; Recurrences Topic Notes: Decrease and Conquer Algorithms; Levitin Ch. 2.4, 4
February 12/13 Lecture 13: ; Lab 5: Graph Traversals
February 15 Lecture 14: More Decrease and Conquer
February 18 Lecture 15: Review; Decrease and Conquer Wrapup
February 19 Exam 1, RB 202, Start between 6 and 8 PM, done between 8 and 10 PM
February 19/20 No labs: Evening exam instead
February 22 Lecture 16: Divide and Conquer; Problem Set 3 out Topic Notes: Divide and Conquer Algorithms; Levitin Ch. 5
February 25 No Classes: President's Week Break
February 26/27 No Labs: President's Week Break
March 1 No Classes: President's Week Break
March 4 Lecture 17: Divide and Conquer; Problem Set 4 Out
March 5/6 Lecture 18: ; Lab 6: Working With Recurrences
March 8 Lecture 19: 2-3 Trees Topic Notes: Binary Search Trees; Topic Notes: 2-3 Trees; Levitin Ch. 6.3
March 11 Lecture 20: Hashing; Problem Set 5 Out Levitin Ch. 7.3
March 12/13 Lecture 21: ; Lab 7: Decrease and Conquer and Divide and Conquer
March 15 Lecture 22: Dynamic Programming Levitin Ch. 8; Topic Notes: Dynamic Programming
March 18 Lecture 23: More Dynamic Programming
March 19/20 Lecture 24: ; Lab 8: Search Trees
March 22 Lecture 25: Greedy Algorithms Topic Notes: Greedy Algorithms; Levitin Ch. 9
March 25 Lecture 26: Quiz and Problem Set Recaps and Exam Review; Problem Set 6 Out
March 26/27 Lecture 27: ; Lab 9: Dynamic Programming
March 29 No Classes: Siena President's Holiday, but plan to be here for the HS programming contest!
April 1 Lecture 28: Backtracking Topic Notes: Backtracking; Levitin Ch. 12.1
April 2 Exam 2, Evening, RB 202, Start between 6 and 8 PM, done between 8 and 10 PM
April 2/3 Lecture 29: ; Lab 10: Greedy Algorithms and Heaps Topic Notes: Dijkstra's Algorithm Handout; Levitin Ch. 6.4-6.5; Topic Notes: Heaps
April 5 Lecture 30: More Graph Algorithms; Exam 2 Recap Levitin Ch. 8.4
April 8 Lecture 31: Limitations of Algorithm Power Levitin Ch. 11; Topic Notes: Limitations of Algorithms
April 9/10 Lecture 32: ; Lab 11: Backtracking
April 12 Lecture 33: Tractability
April 15 Lecture 34: More Tractability
April 16/17 No Labs: Happy Easter!
April 19 No Class: Happy Easter!
April 22 No Class: Happy Easter!
April 23/24 Lecture 35: ; Lab 12: Limitations of Algorithm Power (paper handout only)
April 26 Academic Showcase: participation required! Details TBA
April 29 Lecture 36: Wrapup
May 1 Final Exam, 8:30-10:30 AM