Computer Science 385
Analysis of Algorithms

Spring 2011, Siena College

Home     Syllabus     Schedule

Course Schedule

"Levitin" indicates readings from Introduction to the Design and Analysis of Algorithms, Second Edition, by Anany Levitin. 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
Jan. 18 Lecture 1: Introduction and Overview Levitin Ch. 1; Topic Notes: Introduction
Jan. 20 Lecture 2: Fundamental Data Structures
Jan. 25 Lecture 3: Asymptotic Analysis Levitin Ch. 2; Topic Notes: Analysis
Jan. 27 Lecture 4: Asymptotic Analysis
Feb. 1 Lecture 5: More Asymptotic Analysis
Feb. 3 Lecture 6: More Mathematical Analysis; Problem Set 1 Programs Due 2/4 at 4 PM
Feb. 8 Lecture 7: More Mathematical Analysis; Empirical Analysis; Problem Set 1 written problems due start of class
Feb. 10 Lecture 8: Brute-Force Algorithms Levitin Ch. 3; Topic Notes: Brute-Force Algorithms
Feb. 15 Lecture 9: More Brute Force
Feb. 17 Lecture 10: Exhaustive Search; Divide and Conquer; Problem Set 2 Due 2/18 at 4 PM Levitin Ch. 4; Topic Notes: Divide-and-Conquer Algorithms
Feb. 22 Lecture 11: Exam Review; Exam 1 Out
Feb. 24 Lecture 12: More Divide and Conquer; Exam 1 Due
Mar. 1 Lecture 13: Guest Lecture: Decrease and Conquer Levitin Ch. 5; Topic Notes: Decrease-and-Conquer Algorithms
Mar. 3 Lecture 14: Guest Lecture: More Decrease and Conquer
Mar. 8 Lecture 15: Binary Search Trees; Balanced Trees Levitin Ch. 6.3 ; Topic Notes: Binary Search Trees
Mar. 11 Lecture 16: Guest Lecture: String Matching Levitin Ch. 7.2
Mar. 14-18 Spring Break
Mar. 22 Lecture 17: AVL Tree Wrapup; Introduction to Heaps Levitin Ch. 6.4 ; Topic Notes: Heaps
Mar. 24 Lecture 18: Heaps and Heapsort
Mar. 29 Lecture 19: Counting Sorts; Hashing; Problem Set 4 due at 4:30 PM Levitin Ch. 7.1; Topic Notes: Counting Sorts; Levitin Ch. 7.3; Topic Notes: Hashing
Mar. 31 Lecture 20: Hashing Wrapup
Apr. 5 Lecture 21: Exam Review; Problem Set 5 due at 10:00 AM; Exam 2 Out
Apr. 7 Lecture 22: Dynamic Programming; Exam 2 Due Levitin Ch. 8; Topic Notes: Dynamic Programming
Apr. 12 Lecture 23: Exam 2 Recap
Apr. 14 Lecture 24: Graph Algorithms Levitin Ch. 9; Topic Notes: Graph Algorithms
Apr. 19 Lecture 25: More Graphs; Huffman Codes; Problem Set 6 due Apr. 20 Topic Notes: Huffman Codes
Apr. 21 No Class: Easter Break
Apr. 26 Lecture 26: Limitations of Algorithms Levitin Ch. 11; Topic Notes: Limitations of Algorithms
Apr. 28 Lecture 27: NP-completeness, Wrapup
May 2 Problem Set 7 due
May 5-6 Final Exam

The topic notes were developed from the Introduction to the Design and Analysis of Algorithms, Second Edition, by Anany Levitin main text, the supplemental materials, and from material borrowed from Dr. Robin Flatland and Dr. Eric Breimer.