Computer Science 385

Design and Analysis of Algorithms

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

| 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 | |