
Professor Harriet Fell
Office: 340 WVH
Phone: (617) 3732198
email: fell@ccs.neu.edu
Office Hours: Mondays 3 PM to 4 PM; Thursdays 3 PM to 5 PM

Course Description
Niklaus Wirth famously wrote "programs = algorithms + data structures". This course is about developing algorithms and data structures. It is distinguished from programming in that we will work primarily
with pseudocode.

This course 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 divideandconquer 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.

Prerequisites
CS 3500 (CS U370) and CS 3800 (CS U390)
Examples include:
 fast multiplication of polynomials of degree n (in time O(n log n) instead of in time O(n2))
 search (breadth first and depth first search)
 data compression (Human encoding, which is the second stage of the Deflate
algorithm used by zip and gzip)
 flows in networks
 zerosum games

Textbook
Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani; McGrawHill, 2006.

Exams and Grades
Course grades will be based on
 homeworks 40%
 midterm exam 20% (in class, one 2sided 8.5" by 11" sheet of notes)
 final exam 40% (in class, one 2sided 8.5" by 11" sheet of notes)
Homework
 There will be ~10 written assignments. There will be links to the assignments on the home page and on the schedule page. Some of the problems will be difficult, and it will often be helpful to discuss them with others. Feel free to form study groups. However, the idea is for everyone to understand the problems and experience working through the solutions, so you may not simply "give" a solution to another classmate. In particular, each student must write up his or her own homework solutions and must not read or copy the solutions of others. If you work with others on a problem, you must note with whom you discussed the problem at the beginning of your solution writeup.
 Late homework policy: Homework is due at the beginning of class on the announced due date. You will be granted one homework extension of 1 week, to be used at your discretion, no questions asked. After the first late assignment, unexcused late assignments will be penalized 20% per calendar day late. I normally will not accept assignments after the date on which the following assignment is due or after the solutions have been handed out, whichever comes first. If you will have a valid reason for turning in an assignment late, please see me in advance to obtain fullcredit.
Academic Honesty
 All work submitted for credit must be your own.
 You may discuss the homework problems or projects with your classmates, the teaching assistant(s), and instructor. You must acknowledge the people with whom you discussed your work, and you must write up your own solutions. Any written sources used (apart from the text) must also be acknowledged; however, you may not consult any solutions from previous years' assignments whether they are student or faculty generated.
 Please ask if you have any questions about academic honesty as it applies to CS4800.
