Computer Science 431

Spring 2015, The College of Saint Rose

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.


Topic and/or Event Readings
January 12 Lecture 1: Introduction and Overview; Problem Set 1: Data Structures [HTML] [PDF] Levitin Ch. 1; Topic Notes: Introduction
January 14 Lecture 2: Fundamental Data Structures Bailey Ch. 16.1-16.3; Topic Notes: Data Structures
January 19 No Class: MLK Jr. Day
January 21 Lecture 3: More Data Structures; Asymptotic Analysis Levitin Ch. 2; Topic Notes: Analysis
January 26 Lecture 4: Asymptotic Analysis; Problem Set 2: Asymptotic Analysis [HTML] [PDF]
January 28 Lecture 5: Asymptotic Analysis; Analyzing Non-Recursive Algorithms
February 2 No Class: Snow Day!
February 4 Lecture 6: Analyzing Recursive Algorithms
February 9 Lecture 7: Analysis Wrapup; Problem Set 3: Theoretical and Empirical Analysis [HTML] [PDF]
February 11 Lecture 8: Brute-Force Algorithms Levitin Ch. 3; Topic Notes: Brute-Force Algorithms
February 16 Lecture 9: More Brute Force; Exhaustive Search
February 18 Lecture 10: Problem Set Recaps
February 23 Lecture 11: Exam 1 In-Class; Exam 1 Take-Home Portion Out
February 25 Lecture 12: Decrease and Conquer; Problem Set 4: Brute Force and Decrease and Conquer [HTML] [PDF]; Exam 1 Take-Home Portion Due Levitin Ch. 4; Topic Notes: Decrease-and-Conquer Algorithms
March 2 & 4 Spring Break!
March 9 Lecture 13: Decrease and Conquer, Divide and Conquer Levitin Ch. 5; Topic Notes: Divide-and-Conquer Algorithms
March 11 Lecture 14: Divide and Conquer; Problem Set 5: Divide and Conquer [HTML] [PDF]
March 16 Lecture 15: More Divide and Conquer; Trees Topic Notes: Binary Search Trees
March 18 Lecture 16: Balanced Trees; Problem Set 6: Trees [HTML] [PDF] Levitin Ch. 6.3
March 23 Lecture 17: Heaps and Heapsort Levitin Ch. 6.4-6.5; Topic Notes: Heaps;
March 25 Lecture 18: Problem Set Recaps
March 30 Lecture 19: More Problem Set Recaps; Counting Sorts; Problem Set 7: Working with Map Data [HTML] [PDF] Levitin Ch. 7.1; Topic Notes: Counting Sorts
April 1 Lecture 20: Hashing Levitin Ch. 7.3; Topic Notes: Hashing
April 6 No Class: Happy Easter
April 8 Exam 2 In-Class; Exam 2 Take-Home Portion Out
April 13 Lecture 21: Hashing Wrapup; String Matching; Dynamic Programming; Exam 2 Take-Home Portion Due Levitin Ch. 7.2; Levitin Ch. 8; Topic Notes: Dynamic Programming
April 15 Lecture 22: More Dynamic Programming
April 20 Lecture 23: Dynamic Programming Wrapup; Graphs and Graph Algorithms; Problem Set 8: Dijkstra's Road Trip and More [HTML] [PDF] Levitin Ch. 9; Topic Notes: Graph Algorithms
April 22 Lecture 24: Graph Algorithms
April 27 Lecture 25: Huffman Codes; Graph Algorithm Wrapup Topic Notes: Huffman Codes
April 29 Lecture 26: Limitations of Algorithms; Wrapup; Course Evaluations Levitin Ch. 11; Topic Notes: Limitations of Algorithms
May 4 Review and Final PS Recap, 8:00 PM
May 5 Final Exam, 1:30 PM

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, its supplemental materials, and from material borrowed from Dr. Robin Flatland and Dr. Eric Breimer.