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: | West Village H 330 |
Email: | cce@ccs.neu.edu |
Web: | http://www.ccs.neu.edu/~cce |
Tutor: | Eric Chin |
Email: | chiner@ccs.neu.edu |
Days: | Monday, Wednesday, and Thursday |
Time: | 9:15am to 10:20am |
Room: | West Village H 110 |
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 |
I have set up a Piazza page for the course: CS4800
We will be using Racket for all programming in this course. Some useful resources:
We will be using Git for code-sharing, revision control, and online homework submission. Some useful resources:
We will be using the LaTeX typesetting language for proofs in homework submissions. Some useful resources:
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).
Date | Topic | Assignments |
---|---|---|
Jan. 7, 9-10 | Administrivia Introduction: The Cost of Things Analysis: Asymptotic Notation Sorting: Insertion Sort | Read CLRS: Chapters 2-3 Problem Set 1 Out: PDF |
Jan. 14, 16-17 | Design: 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-24 | Analysis: Solving Recurrences | Read CLRS: Chapter 4.3-4.5 Problem Set 2 Out: PDF |
Jan. 28, 30-31 | Sorting: 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-7 | Data 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-14 | Data Structures: Extensible Arrays Analysis: Amortized Analysis | Read CLRS: Chapter 17 |
Feb. 20-21 | Data Structures: Hash Tables | Read CLRS: Chapter 11.1-11.4 Problem Set 3 Out: PDF |
Feb. 25, 27-28 | Design: Dynamic Programming | Read 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 | ||
Mar. 11, 13-14 | Design: Greedy Algorithms | Read CLRS: Chapter 16.1-16.3 Problem Set 4 Out: PDF |
Mar. 18, 20-21 | Graphs: Representations Graphs: Breadth-First Search Graphs: Depth-First Search | Read CLRS: Chapter 22.1-22.3 |
Mar. 25, 27-28 | Graphs: 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-4 | Graphs: Minimum Spanning Trees Graphs: Shortest Paths | Read CLRS: Chapter 23, Chapter 24.1-24.3 |
Apr. 8, 10-11 | Review: Everything | Problem 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. 17 | No lecture. |