This subject qualifies as a Computer Systems concentration subject.
This is a research-oriented course on algorithm engineering, which will cover both the theory and practice of algorithms and data structures. Students will learn about models of computation, algorithm design and analysis, and performance engineering of algorithm implementations. We will study the design and implementation of sequential, parallel, cache-efficient, external-memory, and write-efficient algorithms for fundamental problems in computing. Many of the principles of algorithm engineering will be illustrated in the context of parallel algorithms and graph problems. Students will read and present research papers, write paper reviews, complete assignments that involve both theory and implementation, participate in classroom discussions, and complete a semester-long research project. Class time will consist of lectures, student presentations, and group project meetings. This course is suitable for graduate students or advanced undergraduates who have taken 6.046 and 6.172. Mathematical maturity and familiarity with algorithm analysis and performance engineering will be assumed.
Lectures will consist of instructor and student presentations and will happen live on Zoom. Lecture attendance is required and participation counts toward the grade. For students in distant timezones where lecture attendance is difficult, their presentations can be prerecorded, and their participation score can be made up by completing additional assignments.
This is a graduate-level course where we will cover research in
algorithm engineering. Advanced undergraduates may enroll if they have
taken 6.046 and 6.172. The course units are 3-0-9.
Assignments will be posted and submitted on Canvas.
Lectures
For each lecture we will study several research papers; for each paper
one student will give a presentation, which will be followed by a
discussion.
Grading
The assignments consist of answering questions about papers, writing paper
reviews, completing a problem set, doing several paper presentations, class participation, and
completing an open-ended research project. The grading breakdown is as
follows.
| Grading Breakdown |
|---|
| Paper Reviews | 15% |
| Problem Set | 10% |
| Paper Presentations | 20% |
| Research Project | 45% |
| Class Participation | 10% |
You must complete all assignments to pass the class.
Paper Reviews and Problem Set
Prior to each lecture, you are
expected to read the papers under "Required Reading" in the schedule
for that lecture.
In addition, students are required to submit one paper review
before every lecture, due at 12:00pm on the day of the lecture.
The review should be on a paper
chosen from any of the starred papers (*) under "Required Reading" for
the lecture.
The review should first describe the problem the paper is trying to
solve, why it is important, the main ideas proposed, and the results
obtained. The review should then describe how the ideas are novel
compared to existing work at the time, the strengths and weaknesses of
the paper, and any ideas you may have for improving the techniques
and/or evaluation criteria, and any open problems or directions for
further work that you can think of. The length should be 3-4 paragraphs.
Finally, there will be a problem set on parallel algorithms to be released several weeks into the semester and due at 11:59pm on 4/2.
Paper Presentations
Students will give several presentations on assigned papers throughout
the semester. These presentations should be 25-30 minutes long with
slides, followed by a discussion. The presentation should discuss the
motivation for the problem being solved, any definitions needed to
understand the paper, key technical ideas in the paper, theoretical
results and proofs, experimental results, and existing work.
Theoretical proofs may be presented on the board. The presentation
should also include any relevant content from related work that would
be needed to fully understand the paper being presented. The
presenter should also present his or her own thoughts on the paper
(perceived strengths and weaknesses, directions for future work,
etc.), and pose several questions for discussion. The presenter will
be expected to lead the discussion on the paper.
Research Project
A large part of the work in this course is
in proposing and completing an open-ended research project.
The project may involve (but is not limited to) any of the following
tasks: implementation of non-trivial and theoretically-efficient
algorithms; analyzing and optimizing the performance of existing algorithm implementations; designing and implementing new algorithms that are theoretically and/or
practically efficient; applying algorithms in the context of
larger applications; and improving or designing new programming frameworks/systems for classes of algorithms. The
project may explore parallelism, cache-efficiency, I/O-efficiency, and
memory-efficiency. There should be an implementation component to the project. The project can be related to research that you
are currently doing, subject to instructor approval.
The project will be done in groups of 1-3 people and consist of a proposal,
mid-term report, final presentation, and final report.
The timeline for the
project is as follows.
| Assignment | Due Date |
|---|
| Pre-proposal Meeting | 3/18 |
| Proposal | 3/25 |
Weekly Progress Reports | 4/2, 4/9, 4/16, 4/23, 4/30, 5/7, 5/14 |
| Mid-term Report | 4/27 |
| Project Presentations | 5/20 |
| Final Report | 5/20 |
- Pre-proposal meeting: You will schedule a 15 minute meeting with the instructor on 3/18 to discuss what you would like to propose. Feedback will be given to be incorporated into the proposal.
- Proposal: The proposal should be about 2 pages long (excluding figures and references) and will describe the
project that you are proposing to work on, the main components of the
project, as well as a projected weekly schedule of what you plan to
accomplish throughout the semester. The deadline is 3/25.
- Weekly progress report: You will submit a weekly progress report due at 11:59pm on Friday, starting 4/2. This should be a few sentences (or longer) describing your progress on the project during the week, and any issues that you encountered. Each student will submit an individual progress report.
- Mid-term report: The mid-term report will talk about what you have
accomplished so far, a breakdown of the contribution among group
members so far, any obstacles you encountered, any changes to the proposed tasks, and a schedule of the
remaining work to be done. This should be about 6 pages long (excluding figures and references). The deadline is 4/27.
- Final presentation: We will have final project presentations on Tuesday 5/20 on Zoom, where you will describe your research to the instructor and classmates, and learn about other projects.
- Final report: The final report will be in the style of a research paper describing your project. It should include an abstract summarizing the project, an introduction describing and motivating the problem, a brief discussion of related work, a brief overview of any background knowledge needed to understand the paper, followed by your contributions. It should also discuss any open problems or directions for further work, and include a breakdown of work among group members. The report should be about 10 pages long (excluding figures and references). The deadline to submit the final report is 5/20.
Piazza
We will be
using
Piazza for answering questions. You may publicly
post questions about the papers or any cool ideas that you have. Discussions among students is encouraged. If possible, please use Piazza instead of emailing the course staff. You may use a private note if you want your post to be visible only to the course staff.
Collaboration Policy
You are welcome to read the papers with
other students, but all of your written work should be your own. You
should carefully acknowledge any collaborators and any outside sources
you use to complete the paper reviews, problem set, and the
project reports.
Computing Resources
We will be using Amazon Web Services.
Useful Resources
Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (CLRS)
Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice
Algorithm Design: Parallel and Sequential by Umut Acar and Guy Blelloch
Computational Geometry - Algorithms and Applications, Third Edition by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars
Networks, Crowds, and Markets by David Easley and Jon Kleinberg
A list of papers related to graph analytics