CS 4800: Algorithms and Data, Spring 2013

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.

Contact

Instructor:Carl Eastlund
Office:West Village H 330
Email:cce@ccs.neu.edu
Web:http://www.ccs.neu.edu/~cce
Tutor:Eric Chin
Email:chiner@ccs.neu.edu

Lectures

Days:Monday, Wednesday, and Thursday
Time:9:15am to 10:20am
Room:West Village H 110

Office Hours

Instructor

Days:Monday and Thursday
Time:3pm to 5pm
Room:West Village H 330

Tutor

Days:Tuesday
Time:3pm to 5pm
Room:West Village H 102

Textbook

Recommended Reading

Resources

Piazza

I have set up a Piazza page for the course: CS4800

Racket

We will be using Racket for all programming in this course. Some useful resources:

Git

We will be using Git for code-sharing, revision control, and online homework submission. Some useful resources:

LaTeX

We will be using the LaTeX typesetting language for proofs in homework submissions. Some useful resources:

Grading

Collaboration Policy

Your work in this course must be your own. You may not copy solutions from other students in this class, from people outside of the class, from the internet, or from any other source. You may not share solutions with other students in this class.

Where an assignment specifically states that you are allowed to do so, you may discuss the problems, concepts, and general techniques used in that assignment with other students, so long as you do not share actual solutions.

You may not discuss any aspect of an exam in this course with any other student. This applies whether the exam is taken in class or is a take-home exam. This restriction applies until every student has had a chance to take the exam in question. Due to illness, travel, or other special circumstances, some students may take exams at different times than others.

If you are in doubt about what you may and may not do, ask the course instructor before proceeding. If you violate the collaboration policy, you will receive a zero as your grade for the entire assignment or exam in question and you will be reported to OSCCR (northeastern.edu/osccr).

Grade Breakdown

Syllabus

DateTopicAssignments
Jan. 7, 9-10Administrivia
Introduction: The Cost of Things
Analysis: Asymptotic Notation
Sorting: Insertion Sort
Read CLRS: Chapters 2-3
Problem Set 1 Out: PDF
Jan. 14, 16-17Design: Divide and Conquer
Sorting: Quick Sort
Sorting: Merge Sort
Read CLRS: Chapter 2.3, Chapter 7.1-7.2,7.4; see also Appendix A
Problem Set 1 Due: Wed., Jan. 16 at 9:00pm
Jan. 23-24Analysis: Solving RecurrencesRead CLRS: Chapter 4.3-4.5
Problem Set 2 Out: PDF
Jan. 28, 30-31Sorting: Selection Sort
Sorting: Heap Sort
Data Structures: Binary Heaps
Read CLRS: Chapter 6.1-6.4
Problem Set 2 Due: Wed., Jan. 30 at 9:00pm
Exam #1: Thu. Feb. 7, 6pm-9pm / WVH 110
Practice Exam / Practice Solutions
Actual Exam / Actual Solutions
Feb. 4, 6-7Data Structures: Arrays and Lists
Data Structures: Doubly-Linked Lists
Data Structures: Self-Balancing Trees
Read CLRS: Chapter 10.1-10.2, Chapter 12.1-12.3, Chapter 13
Feb. 11, 13-14Data Structures: Extensible Arrays
Analysis: Amortized Analysis
Read CLRS: Chapter 17
Feb. 20-21Data Structures: Hash TablesRead CLRS: Chapter 11.1-11.4
Problem Set 3 Out: PDF
Feb. 25, 27-28Design: Dynamic ProgrammingRead CLRS: Chapter 15
Problem Set 3 Due: Wed., Feb. 27 at 9:00pm
Exam #2: Wed. Mar. 13, 6pm-9pm / WVH 108
Practice Exam / Practice Solution
Email the instructor ASAP if you have a conflict.
Mar. 11, 13-14Design: Greedy AlgorithmsRead CLRS: Chapter 16.1-16.3
Problem Set 4 Out: PDF
Mar. 18, 20-21Graphs: Representations
Graphs: Breadth-First Search
Graphs: Depth-First Search
Read CLRS: Chapter 22.1-22.3
Mar. 25, 27-28Graphs: Topological Sort
Graphs: Strongly-Connected Components
Problem Set 4 Due: Mon., Mar. 25 at 9:00pm
Read CLRS: Chapter 22.4-22.5
Problem Set 5 Out: PDF
Apr. 1, 3-4Graphs: Minimum Spanning Trees
Graphs: Shortest Paths
Read CLRS: Chapter 23, Chapter 24.1-24.3
Apr. 8, 10-11Review: EverythingProblem Set 5 Due: Mon., Apr. 8 at 9:00pm
Read Okasaki: TBD
Exam #3: Tue., Apr. 16, 6-9pm / WVH 108
Practice Exam / Practice Solution
Apr. 17No lecture.