Boston University - CAS CS 330S - Summer 2024
Syllabus - Introduction to Analysis of Algorithms
Instructors and Course Staff
| Name |
Office Hours |
| Prof. Tiago Januario |
CDS 911, Tuesdays, 2-4pm |
| Teaching Fellow: Islam Faisal |
Alcove next to CDS 911, 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
HW6 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)
|
HW5 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 Piazza polls 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 Piazza polls
- 5% participation with Vjudge assignments
- 20% weekly homework assignments
- 30% in-class midterm exam
- 40% in-class final exam. Don't make any travel plans before the final date is released
-
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.
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:
