CS 330 Introduction to Algorithms

Fall 2018

Official Course Description

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

Prerequisites: The class assumes working knowledge of CS 112 and CS 131 (or MA 293) as a prerequisite. CS majors typically complete their Group B coursework (any two of CS 132, CS 235 and CS 237) before taking CS 330, and that is recommended. If you don’t have the prerequisites, please talk to an instructor before deciding to continue with this class.

Instructors and Teaching Fellows

Prof. Lorenzo Orecchia
Office Hours:  Tues 3 - 4PM (by prior appointment) and Wed 1-3PM in MCS 135D.

Prof. Dora Erdos
Email:    edori at bu . edu
Office Hours Wed 9:30-10:30AM (by prior appointment) Thur 12:30-2:30PM in MCS288.

Hannah Catabia (TF)
Email:    catabia at bu . edu
Office Hours T-Th 4-5.30PM in EMA 302.

Xin Lu (TF)
Email:    xl at bu . edu
Office Hours T-Th 5.30-7PM in EMA 302. .

The class will be co-taught by Professors Orecchia and Erdos. On any given lecture date, one of the two instructors will deliver the lecture for both the A1 and B1 sections. The TFs will lead the discussion sessions. The objective is to reinforce the concepts covered in the lectures through problem-solving, and to provide clarifications and guidance on the homework assignments.

The purpose of the office hours of the Instructors and Teaching Fellows is to answer specific questions or clarify specific issues. Your fastest route to get an answer to most questions is via Piazza. Office hours are not to be used to fill you in on a class you skipped or to re-explain entire topics. Office hours are scheduled at times to provide the most help to students who start the homework before the last minute.

Lectures

Lecture A1: Tues/Thurs 9:30 - 10:45 AM, CAS B18.
Lecture B1: Tues/Thurs 11:00AM - 12:30, CAS B18.

We expect students to come to class, and to come on time. While the class is large, class participation and questions will be encouraged. Also, while our textbook will be very helpful, it is an imperfect substitute for in-class learning, which is the fastest (and easiest) way to learn the material. If you miss a class, please get the notes and work through the material with a fellow student.

Discussion Labs

Lab A2: Mon 9:05 - 9:55AM in MCS B23.
Lab A3: Mon 10:10 - 11:00AM in EPC 208.
Lab A4: Mon 12:20 - 1:10PM in CAS B06B.
Lab B2: Mon 11.15AM - 12.05PM in CAS 214.
Lab B3: Mon 1:25 - 2:15PM in CAS 222.
Lab B4: Mon 4:40 - 5:30PM in MCS B23.

Labs will be an invaluable part of the course involving interactive problem-solving sessions, tips on homework questions, and supplemental material not covered in lecure. We will post labs on Piazza in advance – please read before coming to lab. Attendance is mandatory and will be taken. Lab solutions will be posted Monday 5PM, after all labs conclude.

Textbook

Algorithm Design, by Kleinberg and Tardos. ISBN 0-321-29535-8.

Communications

This webpage will not update during the course. All communications and course administration will be managed through the two following websites:

  • We will use Piazza for class discussion and questions. The system is highly catered to getting you answers to your questions fast and efficiently from classmates and the course staff. Please do not email questions to the course staff, post your questions on Piazza instead. We also encourage you to post answers to student questions there (but obviously, not answers to problems on the current homework). We will also use Piazza to post announcements and all handouts, including homework assignments and solutions.
  • We will use Gradescope for submitting, grading and returning assignments. All assignments will be submitted electronically via Gradescope as a PDF.

Grading and Attendance

The course grade will break down as follows:

  • 35% homework assignments,
  • 5% attendance and participation in lecture, lab, and on Piazza.
  • 25% in-class midterm exam (in-class, planned for Tuesday, October 16).
  • 35% comprehensive final, in the normal exam slot for classes in our respective time blocks.

Important Dates: Last day to drop without a W: October 9. With a W: November 9. Incompletes for this class will not be granted.

Workload: Be forewarned – the workload in this course will be moderately heavy. We will have seven homework assignments, plus or minus one, due roughly every other week. The majority of the problems on the homeworks will require written (preferably typeset) solutions, but some of the problems will contain small-scale implementations and simulations. These can readily be done in a language of your choice – for example, either Java or Python is fine. As you likely already know, assignments requiring substantial creativity can take more time than you expect, so plan to finish a day early.

Exams: There will be one in-class midterm held during the middle of the semester, on Tuesday, October 16. The cumulative final will be held during the normal two-hour final exam slot. Please make your end-of-semester travel plans accordingly.

Homework Submission: Assignments will typically be due Thursdays by 11:59PM, electronically via Gradescope.

Late Policy: During the course, you will have 2 chances to electronically submit assignments on Gradescope up to 24 hours late with no penalty, but Friday 11:59PM is a hard deadline. Any assignment arriving between Thursday 11:59PM and Friday 11:59PM is considered late. Please do not send emails to the staff about late submissions (not necessary) or requesting additional time.

Regrading Procedure: If, after reviewing the posted solutions, you still believe a portion of your homework was graded in error, you may request a regrade via Gradescope, NOT through email. Note that when we regrade a problem, your score may go up or down.

Attendance: It is expected that you will attend lecture and the laboratory section for this course. Attendance will be taken in labs. Some material covered in lecture and lab will not be covered by our textbooks. We ask that you please arrive in class on time, since it is disruptive to have students flowing in throughout the class period. Moreover, when students are at a borderline between grades, we will factor in attendance before making a final determination.

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.

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

    Academic standards and the code of academic conduct are taken very seriously by our university, by the College of Arts and Sciences, and by 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.

    Prohibited behaviors include:

    • copying all or part of someone else’s work, even if you subsequently modify it; this includes cases in which someone tells you what you should write for your solution
    • viewing all or part of someone else’s work
    • showing all or part of your work to another student
    • consulting solutions from past semesters, or those found online or in books
    • posting your work where others can view it (e.g., online).

    Incidents of academic misconduct will be reported to the Academic Conduct Committee (ACC).

    Collaboration Policy

    The collaboration policy for this class is as follows.

    • You are encouraged to collaborate with one another in studying the textbook and lecture material.

    • As long as it satisfies the following conditions, collaboration on the homework assignments is permitted and will not reduce your grade:

      • Before discussing each homework problem with anyone else, you must give it an honest half-hour of serious thought.
      • You may discuss ideas and approaches with other students in the class, but not share any written solutions. In other words, the writeups you submit must be entirely your own work. You must also acknowledge clearly in the appropriate portion of your solutions (e.g., at the top of your writeups) people with whom you discussed ideas for that portion.
      • You may get help from TFs and undergrad assistants for the class for specific problems. Don’t expect them to do it for you, however.
      • You may not work with people outside this class (but come and talk to us if you have a tutor), seek on-line solutions, get someone else to do it for you, etc.
      • You are not permitted to collaborate on exams.

    The last point is particularly important: if you don’t make an honest effort on the homework but always get ideas from others, your exam scores (accounting for the majority of your grade) will reflect it.