CAS CS 330 - Spring 2013 - Introduction to Algorithms

Syllabus

Course Overview

Official Description: Examines the basic principles of algorithm analysis; techniques of efficient programming; analysis of sorting and searching; graph algorithms; string-matching algorithms; matrix algorithms; integer and polynomial arithmetic; the fast Fourier transform; and NP-hard and NP-complete problems.

Topics: We will no doubt drift from any formal plan, but a rough schedule of where we are headed is provided in the roadmap below. Each of the topics will take roughly one week, except as noted. A more detailed and continually updated schedule will be maintained on the main course homepage.

  1. Course overview. Stable matching, implementation, running times.
  2. Graphs and basic graph algorithms (2 weeks)
  3. Greedy algorithms for optimization problems (2 weeks)
  4. Divide-and-conquer; fast multiplication of integers, matrices, and polynomials (2 weeks)
  5. Dynamic programming for optimization problems (2 weeks)
  6. Max-flow/min-cut
  7. Optimization problems for which no polynomial time algorithms are known; introduction to NP (2 weeks)
  8. Lower bounds and approximation algorithms
  9. Local search and heuristic approaches
  10. Randomized algorithms, including median-finding and order statistics

Class meeting time:   Tues/Thurs 11 - 12:30,   CAS 222.

Lab meeting times:    Mon 11-12 (MCS B31) and Mon 12-1 (MCS B19).

Course homepage:   http://www.cs.bu.edu/fac/byers/cs330.html


Staff

Instructor:  Prof. John W. Byers
Email (preferred): byers @ cs . bu . edu
Phone: 617-353-8925

Office Hours:    Mon 9:30 - 11AM and Wed 3-4:30 PM, held in MCS 270 (John's office).


Teaching Fellow:  Sanaz Bahargam
Email: bahargam @ cs . bu . edu

Office Hours:    Tues 4-5:30 and Wed 11-12:30, held in EMA 302 (next to ugrad lab).

We encourage you to come to our office hours. If you need to talk to us but can't make the office hours, please send us an email. We check it a few times on a weekday and usually at least once a weekend.


Piazza:     We will be using the online forum called Piazza for class announcements, homework clarifications and as a place for students to get fast answers to their questions about material covered in class. We encourage everyone to participate!

Prerequisites:     The class assumes working knowledge of CS 112 and CS 131 (or MA 293). (MA 242 or CS 232) and (MA 294 or CS 235) are co-requisites. If you don't have the prerequisites, please talk to the instructor before deciding to continue with this class.

Textbooks:     The required textbook is:

Workload:     Be forewarned -- the workload in this course will be moderately heavy. We will have seven assignments, plus or minus one, due roughly every other week. The majority of the assignments will consist of problem sets, but some of the problems will contain small-scale implementations and simulations, especially later in the semester. These can readily be done in a language of your choice -- for example, Java is fine.

Grading:     The course grade will break down as follows:

Exams:     There will be one eighty minute in-class midterm held during the middle of the semester before spring break, probably Thursday, March 7. The cumulative final will be held during the normal two-hour final exam slot. Please make your end-of-semester travel plans accordingly. In the event of serious illness, makeup examinations will be given orally.

Attendance:     It is expected that you will attend lecture and the laboratory section for this course. Some material covered in lecture and lab will not be covered by our textbooks. I also ask that you arrive in class on time, since it is highly disruptive to have students flowing in throughout the class period. When students are at a borderline between grades, I consider attendance and class participation in making a final determination.

Late Policy:     Homework assignments will be due Thursdays at the beginning of class. During the course, you will have a total of 3 late days to turn in assignments late with no penalty. Any given assignment must be turned in no later than one day late, i.e. Friday 11AM is the cutoff. Slide late assignments into the "CS 330" drop box, around the corner from the CS department office. Fractions of late days are rounded up to the nearest whole day, so three hours late equals one late day. No additional time will be granted, nor will additional late submissions be granted. As you already know, solving challenging problems can take more time than you expect, so plan to finish a little early.

CAS Academic Conduct Code:     Academic standards and the code of academic conduct are taken very seriously by our university, the College of Arts and Sciences, and the Department of Computer Science. Course participants must adhere to the CAS Academic Conduct Code -- please take the time to review this document if you are unfamiliar with its contents.

Collaboration Policy:     The work that you submit must be your own original work and it is an act of plagiarism to represent the work of another as your own. For the problem sets, limited collaboration in planning and thinking through solutions to homework problems is allowed, but no collaboration is allowed in writing up solutions. You are allowed to work with one or two other students currently taking CS 330 in discussing, brainstorming, and verbally walking through solutions to homework problems. But when you are through talking, you must write up your solutions independently and may not check them against each other. There may be no passing of homework papers between collaborators; nor is it permissible for one person simply to tell another the answer. If you collaborate with one or two other students in the course in the planning and design of solutions to homework problems, then you must acknowledge the collaboration and supply their names on your submissions. Under no circumstances may you use solution sets to problems that may have been distributed in past years, nor the homework papers of students who have taken the course in past years, nor should you look up solution sets from other similar courses. If you are uncertain whether an action constitutes a violation of the collaboration policy, please come by to discuss the matter with me before you act.