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 Meeting #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 Meeting #2; Lab 2: Introduction to METAL Graph Data
January 25 Lecture 5: Asymptotic Analysis; Problem Set 1: [PDF] Out Topic Notes: Analysis Fundamentals; Levitin Ch. 2.1-2.2
January 28 Lecture 6: Asymptotic Analysis
January 29/30 Lecture 7: Lab Meeting #3; Lab 3: Algorithm Analysis Practice (paper handout only)
February 1 Lecture 8: Brute-Force Algorithms Topic Notes: Brute-Force Algorithms; Levitin Ch. 3
February 4 Lecture 9: Brute Force and Exhaustive Search; Quiz 1; Problem Set 2: [PDF] Out
February 5/6 Lecture 10: Lab Meeting #4; Lab 4: Brute-Force Algorithms (paper handout only)
February 8 Lecture 11: Exhaustive Search
February 11 Lecture 12: Decrease and Conquer Algorithms; Recurrences; Quiz 2 Topic Notes: Decrease and Conquer Algorithms; Levitin Ch. 2.4, 4
February 12/13 Lecture 13: Lab Meeting #5; Lab 5: Graph Traversals (paper handout only)
February 15 Lecture 14: Solving Recurrences
February 18 Lecture 15: More Recurrences; Review
February 19 Exam 1, RB 302, 2:35-4:35 or 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: Decrease and Conquer Wrapup; Problem Set 3: [HTML] [PDF] out
February 25 No Class: Winter Break
February 26/27 No Labs: Winter Break
March 1 No Class: Winter Break
March 4 Lecture 17: Divide and Conquer; Problem Set 4: [PDF] Out; Academic Celebration Project: [HTML] [PDF] Introduction Topic Notes: Divide and Conquer Algorithms; Levitin Ch. 5
March 5/6 Lecture 18: Lab Meeting #6; Lab 6: Working With Recurrences
March 8 Lecture 19: Divide and Conquer Algorithms
March 11 Lecture 20: 2-3 Trees; AVL Tree Review Topic Notes: Binary Search Trees; Topic Notes: 2-3 Trees; Levitin Ch. 6.3
March 12/13 Lecture 21: Lab Meeting #7; Lab 7: Divide and Conquer
March 15 Lecture 22: Hashing; Dynamic Programming ; Levitin Ch. 7.3; Topic Notes: Hashing; Levitin Ch. 8; Topic Notes: Dynamic Programming
March 18 Lecture 23: More Dynamic Programming; Problem Set 5: [PDF] Out
March 19/20 Lecture 24: Lab Meeting #8; Lab 8: Search Trees and Dynamic Programming
March 22 Lecture 25: Greedy Algorithms; Quiz 3 Topic Notes: Greedy Algorithms; Levitin Ch. 9
March 25 Lecture 26: Greedy Algorithms; Problem Set 6 Out
March 26/27 Lecture 27: ; Lab 9: Dynamic Programming
March 29 No Class: Siena President's Holiday, but plan to be here for the HS programming contest!
April 1 Lecture 28: Quiz and Problem Set Recaps and Exam Review; 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