Boston University - CAS CS 330 - Summer 2023
Syllabus - Introduction to Analysis of Algorithms

Instructors and Course Staff

Name	Office Hours	Office
Prof. Tiago Januario	CDS 801, Mon/Thu, 4-5pm	CDS 911
Teaching Fellow: Islam Faisal	CDS 801, Tue/Wed, 4-5pm	CDS 1015

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/summer2023/cascs330

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 discussion (Mon, Wed) each week as well as make-up lectures/labs noted below. Attendance in lectures and discussion is mandatory and will be tracked through TopHat participation. The lectures will be taught by Prof. Tiago, and discussions by TF Islam Faisal.

Lectures
The purpose of the lectures is to introduce concepts, computational and algorithm design principles, analysis.

• CDS264, Mondays, 9:00 am - 11:30 am
• CDS264, Wednesdays, 9:00 am - 11:30 am
• CDS264, Thursdays, 10:00 am - 12:30 pm

Make-up classes on two Fridays:

• CDS264, Friday, June 2, 10:00 am - 12:30 am
• CDS264, Friday, June 23, 10:00 am - 12:30 am

Discussion Labs
Discussion 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 discussions 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 discussion labs conclude.

• CDS264, Mondays, 11:30 am - 12:30 am
• CDS264, Wednesdays, 11:30 am - 12:30 am

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.

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	Handouts/Homework
1	Wed, May 24	Introduction, Pseudocode Slides with notes	KT 1.1	Collaboration and Honesty Policy Lab0 - HW0
2	Thu, May 25	Asymptotics Slides with notes	KT 2.2	HW1 out HW0 due
--	Mon, May 29	Holiday (Memorial Day) classes suspended	--	--
3	Wed, May 31	Graph Theory Slides with notes	KT 3.1 Video	Lab 1 - Lectures 2 and 3
4	Thu, June 1	Graph Traversal: BFS and DFS Slides with notes	KT 3.2 Video	HW1 due Online visualisation
5	Fri, June 2 Monday Schedule	Directed Acyclic Graphs Topological Order Slides with notes	KT 4.1	Lab 2 - Lectures 4 and 5 HW2 out
6	Mon, June 5	Greedy algorithms Slides with notes	KT 4.4	Lab 3 - Lecture 6 Practice midterm problems out
7	Wed, June 7	Dijsktra algorithm Divide and conquer Slides with notes	KT 4.5	Lab 4 - Lecture 7
8	Thu, June 8	Recurrences Slides with notes	CLRS 4	HW3 out HW2 due
9	Mon, June 12	Dynamic programming I Slides with notes	KT 5	Lab 5 - Lectures 8 and 9 Practice midterm solutions out
10	Wed, June 14	Dynamic programming II Slides with notes	KT 6.1, 6.2	Lab 6 - Lectures 10
--	Thu, June 15	Midterm - SHA110	KT 6.6	HW4 out HW3 due
--	Mon, June 19	Holiday (Juneteenth) classes suspended	--	--
11	Wed, June 21	Dynamic programming III Slides with notes	KT 7.1	Lab 7 - Lectures 10 and 11 Practice final problems out
12	Thu, June 22	Maximum flows Ford-Fulkerson algorithm Slides with notes	KT 7.2 Video	HW4 due The Plumber Game Trains: on-time-every-time
13	Fri, June 23 Monday Schedule	Bipartite matchings Min-cut max-flow theorem Slides with notes	KT 7.5	Lab 8 - Lectures 12 and 13
14	Mon, June 26	Reductions and NP P, NP, and hardness Slides with notes	KT 8.1, 8.5	Lab 9 - Lecture 14 Video
15	Wed, June 28	Review course evaluation Slides with notes		Lab 10 - Review Video
--	Thu, June 29	Final Exam at CAS224		Last day of class

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. Students from a wide range of backgrounds and with a diverse set of perspectives are welcome. We ask that students treat each other with thoughtfulness and respect, and do their part to make all their peers feel welcome. 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 or student groups.

Accommodations
All are welcome in the course. If you require particular accommodations for exams or coursework, please contact the instructor (and forward any relevant documentation from Disability and Access Services) in a timely manner. If you are facing unusual circumstances during the semester, please reach out to us early on so that we can find a good arrangement.

Personal difficulties Unfortunately, it may happen that you find yourself under circumstances that are affecting your ability to perform well in this class. We are here to support you and find the best way to help you in this course. Please reach out, so that we can help.

Attendance and participation

Your participation grade depends on answering TopHat questions, which requires your presence in class. 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. Some material covered in lecture and lab may not be in our textbooks. You are in all cases responsible to be up to date on the material. Class participation and questions are very much encouraged. Please ask as many questions in class, discussion labs and on Piazza as you need. Chances are that your question and answer will be as helpful to your classmates as to you.

TopHat
TopHat is a web-based platform for interactive questions during class. Our goal in using it is to make lectures more interactive, get you thinking actively about the material, and get some feedback on what you are learning. TopHat questions are generally multiple choice. Most of the points (80%) are for participation. The remaining 20% is for correctness. You will get the full 5% of the course grade if you get at least 80% of the possible TopHat points for the semester. There is a per-semester fee for a TopHat account. If you do not have an account and the fee represents a financial hardship, please let me (the instructor) know via a private Piazza post.

Course TopHat page: Tophat.com Join Code: 677208

Homework

The homework is probably the most useful learning tool in the course—take it seriously, allow yourself time to do it, and have fun! Alumni often describe this course’s homework as critical to their success in job interviews. Limited collaboration on homework is permitted; see below. There will be weekly homework assignments. Problems will be posted Fridays and due the following Thursday evening. Homework problem sets will consist of written problems. They will allow you to practice:

• solving problems using the ideas from class, often in a new way,
• to assess and analyze the correctness of your solution and
• communicate your ideas using technical language (precise descriptions, pseudocode, formal claims, proofs).

Be aware that this latter is just as important as the two former. The lowest grade on your homework assignments will be dropped.

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

Gradescope
https://www.gradescope.com/courses/541943

Workload
CS 330 is a substantial amount of work. There is a problem set every week as well as two exams to study for. As you likely already know, assignments requiring substantial creativity can take more time than you expect, so plan to finish a day early.

Late Policy
Late assignments will not be accepted as we intend to post solutions the next morning. Be mindful that sometimes it’s ok to submit partial results if you weren’t able to 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. The midterm will be during class time and takes 75 minutes. The final is during the University-assigned final exam slot. The content of the final is cumulative. No collaboration whatsoever is permitted on exams, any violations will be reported to the College.

Grading

The course grade will break down as follows:

• 5% class participation, Top Hat, lectures, discussions, Piazza
• 30% weekly homework assignments
• 30% in-class midterm exam
• 35% in-class final exam

Students must pass both exams with at least 40% of the grade to pass the course. Students must attend at least 75% of both lectures and discussion labs to pass the course. 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.

Withdraw and Incompletes

Incompletes for this class will be granted based on CAS Policy.

• Last day to drop without a “W”: Tuesday, May 30, 2023.
• Last day to drop with a “W”: Thursday, June 15, 2023.

Regrade Policy
If, after reviewing the solutions and your answer, you still believe a portion of your homework was graded in error, you may request a regrade, via Gradescope, *NOT* through email. One of the staff will consider your request and adjust your grade if appropriate. Note that when we regrade a problem, your score may go up or down. Regrade requests can be submitted up to one week (7 days) after grades for a given assignment have been posted.

Collaboration, Citation, and Academic Honesty

Citation policy
You can reference anything from the textbook, lecture and discussion notes, information given by the course staff without having to cite it. However, if you make use of any other information, you have to include proper citation. If you omit to do this you are committing plagiarism. You are allowed and encouraged to further your knowledge by finding related material online or in books, but you have to cite it. Your citation may be a url, the title and chapter of a book, or a paper reference. Searching explicitly for answers to problems on the Web or from persons not enrolled in the class this current semester is strictly forbidden. (This includes students who took the course in previous semesters, posted solutions, Chegg, GitHub, etc. )

Collaboration Policy Collaboration on homework is permitted and even encouraged. If you choose to collaborate on some problems, you are allowed to discuss each problem with at most 3 other students currently enrolled in the class. Before working with others on a problem, you should think about it by yourself for at least 45 minutes. You must write up each problem solution by yourself (using your own words) without assistance, even if you collaborate with others to solve the problem. Identical worded answers, including identical pseudocode, will receive no grade. You must also identify your collaborators clearly on the first page of your assignment. If you did not work with anyone, you should write ``Collaborators: none.'' It is a violation of this policy to submit a problem solution that you cannot orally explain to the instructors. You may get help on Piazza or in office hours from the instructors for the class for specific problems. You don’t need to list them as collaborators.

No collaboration whatsoever is permitted on exams!

Collaboration strategies
If you do collaborate, use it as an opportunity to practice group work skills: give everyone a chance to speak, listen carefully, acknowledge good suggestions. If you have a tendency to be shy, speak up! If you have the tendency to dominate conversations, make sure to give others the floor. We strongly encourage you to find a small group of classmates that you regularly discuss and review material with. Feel free to post on Piazza to find a study mate.

Academic Conduct

Academic standards and the code of academic conduct are taken very seriously by the 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. If in doubt, our department has an extensive compilation of examples with regard to Academic Conduct and permissible collaboration. Violations of this policy are handled according to University regulations.

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: