Computer Science 431

Spring 2013, The College of Saint Rose

Course Schedule

"Levitin" indicates readings from Introduction to The Design and Analysis of Algorithms, Third 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.


Topic and/or Event Readings
January 15 Lecture 1: Introduction and Overview Levitin Ch. 1; Topic Notes: Introduction
January 17 Lecture 2: Fundamental Data Structures
January 22 Lecture 3: Asymptotic Analysis Levitin Ch. 2; Topic Notes: Analysis
January 24 Lecture 4: Asymptotic Analysis
January 29 Lecture 5: Asymptotic Analysis
January 31 Lecture 6: Mathematical Analysis
February 5 Lecture 7: Mathematical Analysis; Empirical Analysis; Problem Set 1 due
February 7 Lecture 8: Brute-Force Algorithms Levitin Ch. 3; Topic Notes: Brute-Force Algorithms
February 12 Lecture 9: Brute-Force Algorithms
February 14 Lecture 10: More Brute Force; Exhaustive Search; Problem Set 2 due
February 19 Lecture 11: Review; Exam 1 In-Class; Exam 1 Take-Home Portion Out
February 21 Lecture 12: Decrease and Conquer; Exam 1 Take-Home Portion Due Levitin Ch. 4; Topic Notes: Decrease-and-Conquer Algorithms
February 26 Lecture 13: Exam and Problem Set Recaps
February 28 Lecture 14: More Decrease and Conquer; Problem Set 3 due (Friday)
March 5 & 7 Spring Break!
March 12 Lecture 15: Divide and Conquer Levitin Ch. 5; Topic Notes: Divide-and-Conquer Algorithms
March 14 Lecture 16: More Divide and Conquer; Trees Topic Notes: Binary Search Trees
March 19 No Class: Advisement Day
March 21 Lecture 17: Balanced Trees; Problem Set 4 due Levitin Ch. 6.3
March 26 Lecture 18: Heaps and Heapsort Levitin Ch. 6.4; Topic Notes: Heaps;
March 28 Lecture 19: Review
April 2 Lecture 20: Virtual Lecture: Counting Sorts Levitin Ch. 7.1; Topic Notes: Counting Sorts
April 4 Lecture 21: Review; Problem Set 5 due
April 9 Exam 2 In-Class; Exam 2 Take-Home Portion Out
April 11 Lecture 22: Hashing; Exam 2 Take-Home Portion Due Levitin Ch. 7.3; Topic Notes: Hashing
April 16 Lecture 23: Hashing Wrapup; Dynamic Programming Levitin Ch. 8; Topic Notes: Dynamic Programming
April 18 Lecture 24: Graphs and Graph Algorithms; Problem Set 6 due Levitin Ch. 9; Topic Notes: Graph Algorithms
April 23 Lecture 25: Graph Algorithms
April 25 Lecture 26: Graph Algorithm Wrapup
April 30 Lecture 27: Huffman Codes; Limitations of Algorithms Topic Notes: Huffman Codes; Levitin Ch. 11; Topic Notes: Limitations of Algorithms
May 2 Lecture 28: Limitations of Algorithms; Wrapup; Course Evaluations; Problem Set 7 due
May 6 Final Exam, 10:45 AM

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