# Algorithm Engineering (aka. How to Write Fast Code)

Instructor: Yan Gu

Email: ygu AT cs DOT ucr DOT edu

MWF 4:00-4:50

Office: WCH335

Office hours: 1:30-2:30pm Tuesday

## Overall Policy

All information on this webpage is subject to change due to the development of COVID-19 and the arrangement on campus.

• Paper Review - 15%. On the course website, there is a list of related papers for each topic. The students need to submit paper reviews for two papers.
• Course Presentation - 20%. This is a seminar course. Each student should present one of the two reviewed papers.
• Quiz - 10%. By the end of Week 4, we have a small quiz to guarantee you understand the basic knowledge, which will be helpful for your final project.
• Midterm Project - 20%. In the midterm project, each student will implement one of the three algorithms taught in the first two weeks.
• Final Project - 35%. Every student should pick a problem that can be related to one's research and try to implement it in an efficient way.
• Class Participation - 10% bonus. Students are encouraged to participate in discussing the course material and ask questions during the lectures and office hours.

The lecture for how to give a clear talk is here, and this is the link to the evaluation form for your course presentation.

## Syllabus

The following syllabus is tentative and subject to changes.

 Date Content Slides Video Week 1: March 30 (M) Course introduction and policy L1.pdf L1.mp4 Assignment 0 (warmup) out Week 1: April 1 (W) Matrix multiplication as an example L2.pdf L2.mp4 Week 1: April 3 (F) Parallelism: theory and practice L3.pdf L3.mp4 Week 2: April 6 (M) Parallelism: implementation details L4.pdf L4.mp4 Week 2: April 8 (W) I/O efficiency: basic concepts L5.pdf L5.mp4 Week 2: April 10 (F) Sampling, and I/O efficiency: sample sort L6.pdf L6.mp4 Assignment 0 due Week 3: April 13 (M) I/O efficiency: semisort, seq algorithms, and project L7.pdf L7.mp4 Week 3: April 15 (W) (Midterm project Q&A) Week 3: April 17 (F) Randomized work-stealing scheduler L8.pdf L8.mp4 Paper reading: decision due Week 4: April 20 (M) Overview of modern computer architecture L9.pdf L9.mp4 Week 4: April 22 (W) (Quiz and midterm project Q&A) Race.pdf Race.mp4 Week 4: April 24 (F) Quiz Week 5: April 27 (M) Sequence Algorithms (by students) Week 5: April 29 (W) (no class) Midterm project due Week 5: May 1 (F) (no class, pre-proposal meeting) Week 6: May 4 (M) Graph processing systems: overview L10.pdf L10.mp4 Final project proposal Week 6: May 6 (W) Graph processing systems (by students) Week 6: May 8 (F) (no class) Week 7: May 11 (M) New Bentley rules for modern programming L11.pdf L11.mp4 Week 7: May 13 (W) Geometry processing: overview L12.pdf L12.mp4 Week 7: May 15 (F) (no class) Paper review due Week 8: May 18 (M) Geometry: NN search and clustering (by students) Week 8: May 20 (W) Geometry: range search and triangulation (by students) Week 8: May 22 (F) Final project milestone Final project milestone Week 9: May 25 (M) (no class, work for final project) Week 9: May 27 (W) (no class, work for final project) Week 9: May 29 (F) (no class, work for final project) Week 10: June 1 (M) Final project presentation Week 10: June 3 (W) Final project presentation Week 10: June 5 (F) Final project presentation Final project due the next Monday

## Paper Review and Course Presentation

This is a graduate seminar course, and the goal is to not only learn new knowledge, but also work on toy problems that prepare you for future research work. A significant component in this course is paper review and course presentation, which contributes to 35% (15%+20%) of the final score.

A list of about 30 papers are here, categorized in sequence algorithms, graph processing systems and geometry processing. Each student should read two papers in the same category, and every student should read different papers. A spreadsheet containing the paper list for you to reserve will be available soon, as long as the roster of this course is decided.

Each paper 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 of each review should be no less than 1000 words and no more than 3000 words.

Then for the two papers each student reviews, s/he should select one paper to present during the class. 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, and pose several questions for discussion. The presenter should send this paper review and a draft version of the slides to Yan at least two days before the presentation, and Yan will provide feedback. Also, you are welcome to talk to Yan at any time. The other paper review is due on May 20.

## Quiz

There will be a small quiz by the end of Week 4, when we basically finished the first part of the course. It is a simple quiz and only takes 10% of the final score. The goal of this quiz is to guarantee you understanding the basic knowledge, which will be helpful for your final project.

## Midterm Project

The goal of the midterm project is to warm up with the basic knowledge taught in the first four weeks, so each student can have an end-to-end practice of engineering an algorithm, as well as experience in using the course server. Each student should pick one of the three problems: matrix multiplication, sample sort, or semisort, which are taught in April 1 and 13. More information will be given in the slides of the first lecture.

## Final Project

The final project is in proposing and completing an open-ended problem. The project can be any of the following tasks: implementation of non-trivial and theoretically-efficient algorithms discussed during the course; analyzing and optimizing the performance of existing algorithm implementations; designing and implementing new algorithms that are theoretically and/or practically efficient; and applying algorithms in the context of larger applications. The project may explore parallelism, and cache or 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 should be done for each student individually. It is possible to work for groups of 2 students, but it requires the instructor's permission and a clear plan on how to distribute the work to both of the group members. The final project consists of a proposal, a milestone, and a final report, which will be due on May 4, 22 and June 8. Each group also needs to submit weekly progress report on May 13 and 29.

## Collaboration Policy

Basically there is no much collaboration applicable in this course. The only possible part might be paper reading, although different papers will be assigned to each of you. You are welcome to read the papers together, but all of your written work should be your own. In the programming projects, if you seek assistance from anyone not in your group, you should carefully acknowledge that.

## Useful Resources

This course is inspired and uses many materials from the two following courses at MIT. The instructor appreciates Prof. Leiserson and Prof. Shun for sharing many useful resources. The students can also use the following links to find additional resources.

6.172 Performance Engineering of Software Systems, originally by Charles E. Leiserson

6.886 Algorithm Engineering, originally by Julian Shun