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) |

Email: | cce@ccs.neu.edu |

Web: | http://www.ccs.neu.edu/~cce |

Days: | Monday, Wednesday, and Thursday |

Time: | 9:15am to 10:20am |

Room: | Ell Hall 312 |

Days: | Tuesday and Friday |

Time: | 9:15am to 10:20am |

Room: | West Village H 330 |

Either one of the following:

- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, MIT Press, 2009.
*(recommended)* - Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2006.

Plus:

- Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998.

Supplemental:

- Dasgupta, Papadimitriou, and Vazirani, Algorithms, unpublished online draft.

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:

- Source files for sample solutions are available in the syllabus.
- The recommended LaTeX document class is
`homework.cls`. - A good (if old) LaTeX reference can be found at the Goddard Institute for Space Studies website.
- I encourage students to use Piazza to figure out LaTeX together. It has been a long time since I learned LaTeX, you guys will know what the hard parts are better than I.
- As new tutorials, Emacs modes, etc. come to my attention, I will add links here.

Date | Topic | Assignments |
---|---|---|

Sept. 5-6 | Administrivia Introduction: The Stable Matching Problem | Read K&T: Chapter 1 Problem Set 1 Out: Assignment |

Sept. 10, 12-13 | Introduction: 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-20 | Sorting: 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-27 | Analysis: 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-4 | Graphs: 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-11 | Graphs: Minimum Spanning Trees | Read CLRS: Chapter 23, K&T: Chapter 4.5 |

Oct. 15, 17-18 | Graphs: Maximum Network Flow | Read CLRS: Chapter 26.1-26.3, K&T: Chapter 7.1-7.3, 7.5 |

Oct. 22 | Midterm Review | Problem Set 3 Due: Oct. 22; Solution (GitHub, work in progress) |

Oct. 24-26 | Midterm Exam | |

Oct. 31; Nov. 1 | Data 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-8 | Proof Methods: Structural / Procedural Induction Proof Methods: Loop Invariants Data Structures: Hash Tables | Read CLRS: Chapter 11, K&T: Chapter 13.6 |

Nov. 14-15, 19 | Data Structures: Hash Tables, Continued Algorithm Design: Dynamic Programming | Read CLRS: Chapter 15, K&T: Chapter 6 Problem Set 4 Out: GitHub |

Nov. 26, 28-29 | Algorithm Design: Greedy Algorithms | Read CLRS: Chapter 16, K&T: Chapter 4 |

Dec. 3, 5 | Analysis: NP-completeness Algorithm Design: Approximation Algorithms | Read CLRS: Chapter 34, 35, K&T: Chapter 8, 11 Problem Set 4 Due: Dec. 5 |

Dec. 14 | Final Exam | Ryder Hall 233; 8am-10am Sample Exam |