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 |

- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, MIT Press, 2009. (a.k.a.
**CLRS**)

- Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998. (a.k.a.
**Okasaki**)

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:

- The Racket Guide
- The Racket Reference
- Search all online Racket documentation.
- Why the instructor's Racket code is so funny-lookin'.

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

- CS4800 Github Organization
- Github
- The Fundies II (Honors) introduction to Git.
- Git for Computer Scientists
- An introduction to Git for Racket developers by Northeastern's own Eli Barzilay.

See especially Additional Resources for more links.

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

- Essential LaTeX (PDF)
- Inessential LaTeX (PDF)
- A good (if old) LaTeX reference can be found at the Goddard Institute for Space Studies website.
- Detexify lets you draw symbols and tells you the LaTeX command for them
- Rubber is a useful tool for building LaTeX documents.
- As new tutorials, Emacs modes, etc. come to my attention, I will add links here.

Your work in this course must be your own. You

may notcopy solutions from other students in this class, from people outside of the class, from the internet, or from any other source. Youmay notshare solutions with other students in this class.Where an assignment

specificallystates that you are allowed to do so, youmaydiscuss the problems, concepts, and general techniques used inthatassignment with other students, so long as you do not share actual solutions.You

may notdiscussanyaspect 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 untileverystudent 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

mayandmay notdo, 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).

**35%**: Homework**20%**: Exam #1**20%**: Exam #2**25%**: Exam #3**Up to 5%**: Discretionary Bonus for Extra Effort

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 110Practice 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 108Practice 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 108Practice Exam / Practice Solution | ||

Apr. 17 | No lecture. |