Boston University - Summer 2024
CAS CS 330S - Introduction to Analysis of Algorithms

Instructors and Course Staff

Name	Office Hours
Prof. Tiago Januario	CDS 1001, Tuesdays, 2-4pm
Teaching Fellow: Islam Faisal	CDS 801, Tuesdays, 4-6pm

Communication

We will use Piazza for all class discussions. Post questions about lectures, homework, or course logistics there. Avoid sending emails to the course staff. Your questions and answers will benefit other students. Please respond to questions and the staff will monitor and provide assistance as necessary. Feel free to ask homework-related questions, but avoid posting solutions. For sensitive or specific questions, use private posts.

Piazza
Q&A, discussion, as well as distribution of lecture notes, homework, additional material, course logistics info:
https://piazza.com/bu/summer2024/cascs330s

Email
Please do not contact us by email. Post a private message to instructors on Piazza instead.

Prerequisites

The class assumes CS 112 and CS 131 (or MA 293). CS majors need to complete at least one of their Group B coursework (any two of CS 132/MA242, CS235/MA294 and CS237/MA581) before taking CS 330.

Structure

The class consists of three 150 minutes lectures (Mon, Wed, Thu) and two 60 minute labs (Mon, Wed) each week as well as make-up lectures/labs noted below. Attendance in lectures and labs is mandatory and will be tracked.

Labs will be an invaluable part of the course involving interactive problem-solving sessions, tips on homework questions, and supplemental material not covered in lecture. The objective of the labs is to reinforce the concepts covered in the lecture through problem-solving. The problems discussed are often closely related to that week’s homework assignment. We will post lab notes on Piazza in advance -- please read before coming to lab. Lab solutions will be posted after all labs conclude.

Additionally, every member of the course staff will hold office hours. The purpose of the office hours is to answer questions on any aspect of the course material and lab or homework problems.

Lectures will be taught by Prof. Tiago, and labs by TF Islam Faisal. See the course schedule below.

Syllabus

Examines the basic principles of algorithm design and analysis; asymptotic analysis; graph algorithms; greedy algorithms; dynamic programming; network flows; polynomial- time reductions; NP-hard and NP-complete problems; This course fulfills a single unit in each of the following BU Hub areas: Quantitative Reasoning II, Critical Thinking.

Topics
We will mostly follow the order and content in the textbook. Topics are subject to change.

• Asymptotics, data structures, how to describe an algorithm (pseudocode)
• Graphs – data structures, graph traversals, connectivity, DAGs
• Greedy algorithms – scheduling, shortest paths, minimum spanning trees
• Divide-and-conquer – variations on sorting and searching, integer multiplication, closest pair of points
• Dynamic programming – interval scheduling, subsetSum, knapsack, sequence alignment
• Network flow – Ford-Fulkerson, MFMC theorem, applications
• Polynomial time reductions, NP, NP-Complete

Schedule

This schedule is subject, and likely, to change as we progress through the semester. Reading chapters are from the first textbook (KT) or from the second textbook (CLRS), referred to by the acronyms of the author names.

Lec.	Date	(Tentative) Topics	Reading	Note
1	Wed, May 22	Introduction, Pseudocode	KT 1.1	Collaboration and Honesty Policy Lab 1 - How to write your own rubrics HW1 out
Thu, May 23		Classes suspended - ICPC North America Championship
Mon, May 27		Classes suspended - Memorial Day
2	Wed, May 29	Asymptotics	KT 2.2	Lab 2 - Lectures 1 and 2 HW2 out
3	Thu, May 30	Graph Theory	KT 3.1	Video Last day to drop without a ‘W’ grade (all charges remain after this date)
4	Fri, May 31	Graph Traversal: BFS and DFS	KT 3.2	Lab 3 - Lectures 3 and 4 Video Online visualisation
5	Mon, June 3	Directed Acyclic Graphs Topological Order	KT 4.1	Lab 4 - Lecture 5
6	Wed, June 5	Greedy algorithms	KT 4.4	Lab 5 - Lecture 6 Midterm practice problems out HW3 out
7	Thu, June 6	Dijsktra algorithm Divide and conquer	KT 4.5	\o/ ||
8	Fri, June 7	Recurrences	CLRS 4	/ \
9	Mon, June 10	Dynamic programming I	KT 5	Lab 6 - Lectures 7 and 8
Wed, June 12		In class midterm exam		HW4 out
10	Thu, June 13	Dynamic programming II	KT 6.1, 6.2, 6.6	Last day to drop with a ‘W’ grade HW5 out
11	Mon, June 17	Dynamic programming III	KT 7.1	Lab 7 - Lectures 9, 10, and 11
Wed, June 19		Classes suspended - Holiday (Juneteenth)		HW6 out Final exam practice problems out
12	Thu, June 20	Maximum flows Ford-Fulkerson algorithm	KT 7.2 Video	The Plumber Game Trains: on-time-every-time
13	Mon, June 24	Bipartite matchings Min-cut max-flow theorem	KT 7.5	Lab 8 - Lectures 12 and 13
14	Wed, June 26	Reductions and NP P, NP, and hardness	KT 8.1, 8.5	Lab 9 - Lecture 14 course evaluation Video , Video
Thu, June 27		In class final exam		Enjoy your summer!

Textbook

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

Useful additional resources:

• (CLRS) Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3rd ed. MIT Press.
• J. Erickson. Algorithms, 2019. Available from http://algorithms.wtf/ See also the extensive exercises on the website.
• Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer. (Useful background on discrete mathematics.)

Course atmosphere, diversity and inclusion

• We intend to provide a positive and inclusive atmosphere in classes and on the associated virtual platforms.
• If you require special accommodations for exams or coursework, please send a Faculty Accommodation Letter (FAL) privided by the Disability and Access Services office to the instructors.
• Course staff are not qualified to determine what accommodations are appropriate. Without an FAL, we can't decide on accommodations for any student.

Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students.

Participation

• Participation will be tracked with quizes and Vjudges assignments.
• You will get the full participation points if you answer at least 75% of the possible participation points.
• If you end up geting x% of the points, where x < 75, you will get x/75 of the points.
• Most of the material covered in lectures and labs can be found in our textbooks. Read them!
• 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.
• In all cases, you are responsible for being up to date on the material.

Homework

• Weekly homework assignments will be posted on Wednesdays.
• Assignments will be due on Tuesdays by 09:00 p.m. ET, electronically via Gradescope.
• Gradescope will remain open for a 3-hour grace period after the posted deadline.
• Late assignments will not be accepted after the grace period as we intend to post solutions the following day.
• You can use up to 3 grace periods without penalty, after that, you will receive a 10% penalty on each future late submission.
• Students who used no more than 1 grace period will receive a 5% extra credit towards their overall homework score.
• You are responsible for submitting high-quality images of your solutions. Illegible submissions will receive a 0 grade
• We highly recommend Gradescope Mobile App. You can also use your favorite app from iPhone or Android.
• Select the right pages on Gradescope for each problem (solved or not) to avoid 5% penalty for each non-selected problem.
• Submissions with identically worded answers, including identical pseudocodes, are considered serious offence and will be reported to Dean's Office.
• Any use of ChatGPT or similar AI functionality to help solve homework problems violates the Collaboration & Honesty Policy.

Sometimes it's ok to submit partial results if you couldn't fully finish your assignment, don't miss the due date because of last-minute work.

Exams

• Both exams will consist of problem-solving and short questions about the material.
• Each exam duration and their locations are given in the course schedule.
• The content of the final is cumulative.
• No collaboration whatsoever is permitted on exams, any violation will be reported to the College.

Regrade Policy

• Regrade requests can be submitted up to one week (7 days) after grades for a given assignment have been posted (except the final exam).
• You must request a regrade via Gradescope, *NOT* through email .
• When we regrade a problem, your score may go up or down.

Grading

The course grade will break down as follows:

• 5% participation with quizes and Vjudge assignments
• 25% weekly homework assignments
• 35% in-class midterm exam
• 35% in-class final exam. Don't make any travel plans before the final date is released

Students must pass both exams with at least 40% of the grade to pass the course.


• Incompletes for this class will be granted based on CAS Policy.
• Once the final letter grades are published, asking a professor to boost your grade violates the academic conduct code because it compromises the fairness, integrity, and credibility of the academic system.
  • To be more precise, it violates the Section III. Violations of this Code,
    item Q. "Attempting improperly to influence the award of any credit, grade, or honor".

Participating in lectures, discussions, and on Piazza, bonus participation points will be awarded to students who get the most “good questions” and “good answers” on Piazza. Only good questions on the course material (not logistics) will be counted.

Citation policy

• You can refer to anything from the textbook, lecture and discussion notes, and information given by the course staff without having to cite it.
• If you use any other information, you must include a proper citation. If you omit to do this, you are committing plagiarism.
• Searching explicitly for answers to problems on the Web or from persons not enrolled in the class this current semester is strictly forbidden.

Collaboration & Honesty Policy

• The Collaboration & Honesty Policy specifies the rules of collaboration in the course and penalties for cheating.
• We require that each student read, sign, and submit this document to Gradescope.
• Even if you get help on Piazza or during office hours from the instructors for the class for specific problems, list them as collaborators.

Miscellaneous

Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.

LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a tex editor for Windows; Overleaf is a web-based latex system (allows you to avoid latex installation on your machine). Not so short intro to latex; a latex tutorial.

Homework template files: tex, pdf, jpg.

This document was last modified: