CS4800 Algorithms and Data Spring, 2009 Syllabus

Professor Harriet Fell
Office: 340 WVH
Phone: (617) 373-2198
e-mail: 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 pseudo-code.
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 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.
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 fi rst and depth fi rst search)
  • data compression (Hu man encoding, which is the second stage of the Deflate algorithm used by zip and gzip)
  • flows in networks
  • zero-sum games
Textbook Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani; McGraw-Hill, 2006.
Exams and Grades Course grades will be based on
  • homeworks 40%
  • mid-term exam 20% (in class, one 2-sided 8.5" by 11" sheet of notes)
  • final exam 40% (in class, one 2-sided 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 write-up.
  • 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 full-credit.

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.