CS 4800: Algorithms and Data, Fall 2012

From the online course catalog:

Introduces the basic principles and techniques for the design, analysis, and implementation of efficient algorithms and data representations. Discusses asymptotic analysis and formal methods for establishing the correctness of algorithms. Considers divide-and-conquer algorithms, graph traversal algorithms, and optimization techniques. Introduces information theory and covers the fundamental structures for representing data. Examines flat and hierarchical representations, dynamic data representations, and data compression. Concludes with a discussion of the relationship of the topics in this course to complexity theory and the notion of the hardness of problems.


Instructor:Carl Eastlund
Office:WVH 330 (but see office hours)


Days:Monday, Wednesday, and Thursday
Time:9:15am to 10:20am
Room:Ell Hall 312

Office Hours

Days:Tuesday and Friday
Time:9:15am to 10:20am
Room:West Village H 330


Either one of the following:




35% homework, 25% midterm exam, 35% final exam, 5% extra effort.


We have a course set up at Piazza for notifications, question resolution, group formation, etc.


Homework will be submitted by groups of 2-4 students. You can work with whoever you like, as long as everyone finds a group. Outside of your group, you may discuss the lecture and text material as you see fit, but do not share answers to assigned homework problems. Cheating will not be tolerated.

For individual assignments, see the syllabus.


I strongly recommend using the LaTeX typesetting language for proofs in homework submissions. Some useful resources:


Sept. 5-6Administrivia
Introduction: The Stable Matching Problem
Read K&T: Chapter 1
Problem Set 1 Out: Assignment
Sept. 10, 12-13Introduction: More about the Stable Matching Problem
Analysis: Asymptotic Running Times
Sorting: Insertion Sort
Read CLRS: Chapter 3.1, Chapter 2, K&T: Chapter 2.1-2.2, 2.4
Problem Set 1 Due: Sept. 13; Solution (LaTeX source)
Sept. 17, 19-20Sorting: Quicksort
Sorting: Mergesort
Sorting: Lower Bounds
Read CLRS: Chapters 7.1-7.2, 7.4 (Mon), 4.3-4.5 (Wed), 8.1 (Thu), K&T: Chapter 5.1-5.2 (Wed)
Problem Set 2 Out: Assignment (updated 8:21am on 9/24) Use this script to check your solution's input and output. Run it on login.ccs.neu.edu and provide your executable name as an argument. It will pass a JSON list to your program and report an error unless your program returns a JSON list.
Sept. 24, 26-27Analysis: Recurrences
Graphs: Depth-First Traversal
Graphs: Breadth-First Traversal
Graphs: Topological Sort
Read CLRS: Chapter 22.1-22.4, K&T: Chapter 3.1-3.3, 3.5-3.6
Oct. 1, 3-4Graphs: Dijkstra's Algorithm
Data Structures: Binary Heaps
Data Structures: AVL Trees
Problem Set 2 Due: Oct. 4; Solution (PDF, LaTeX, Racket) Note: You will need /proj/racket/bin in your PATH to run solution programs on login.ccs.neu.edu.
Problem Set 3 Out: Assignment (updated 5:03pm on 10/19)
Oct. 10-11Graphs: Minimum Spanning TreesRead CLRS: Chapter 23, K&T: Chapter 4.5
Oct. 15, 17-18Graphs: Maximum Network FlowRead CLRS: Chapter 26.1-26.3, K&T: Chapter 7.1-7.3, 7.5
Oct. 22Midterm ReviewProblem Set 3 Due: Oct. 22; Solution (GitHub, work in progress)
Oct. 24-26Midterm Exam
Oct. 31; Nov. 1Data Structures: Comparison of Arrays, Lists, and Trees
Data Structures: Array Slices
Data Structures: Extensible Arrays
Analysis: Amortized Analysis
Read CLRS: Chapter 17.1
Nov. 5, 7-8Proof Methods: Structural / Procedural Induction
Proof Methods: Loop Invariants
Data Structures: Hash Tables
Read CLRS: Chapter 11, K&T: Chapter 13.6
Nov. 14-15, 19Data Structures: Hash Tables, Continued
Algorithm Design: Dynamic Programming
Read CLRS: Chapter 15, K&T: Chapter 6
Problem Set 4 Out: GitHub
Nov. 26, 28-29Algorithm Design: Greedy AlgorithmsRead CLRS: Chapter 16, K&T: Chapter 4
Dec. 3, 5Analysis: NP-completeness
Algorithm Design: Approximation Algorithms
Read CLRS: Chapter 34, 35, K&T: Chapter 8, 11
Problem Set 4 Due: Dec. 5
Dec. 14Final ExamRyder Hall 233; 8am-10am
Sample Exam