TA: Yiqiu Wang

Schedule: Tuesdays and Thursdays 2:30-4pm in room 1-150

Office hours: By appointment

Email: jshun AT mit.edu, yiqiuw AT mit.edu

Piazza

Units: 3-0-9

Prerequisites: 6.046, 6.172

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.

Skip to Course Policy

- Please see Piazza for updates regarding lectures and assignments given the recent update from MIT regarding COVID-19.

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.

Grading Breakdown | |
---|---|

Paper Reviews | 10% |

Paper Questions and Problem Set | 15% |

Paper Presentations | 20% |

Research Project | 50% |

Class Participation | 5% |

In addition, students are required to submit one paper review every week, due 11:59pm on Mondays. The review should be on a paper chosen from any of the starred papers (*) under "Required Reading" for the two lectures the week (i.e., the Tuesday and Thursday immediately after the due date).

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.

The paper reviews will be submitted on Learning Modules. The paper reviews will be made visible after each submission deadline, and you are encouraged to read other reviews to improve your understanding and to prepare for the class discussion.

Finally, there will be a problem set on parallel algorithms to be released several weeks into the semester and due on 3/20.

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/10 |

Proposal | 3/31 |

Weekly Progress Reports | 4/3, 4/10, 4/24, 5/1, 5/8 |

Mid-term Report | 4/21 |

Project Presentations | 5/12 |

Final Report | 5/12 |

- Pre-proposal meeting: You will schedule a 15 minute meeting with the instructors on 3/10 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/31.
- Weekly progress report: You will submit a weekly progress report due at 11:59 on Friday, starting 3/20. 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/21.
- Final presentation: We will have final project presentations on Tuesday 5/12 (time and location TBD), 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/12.

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