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
All information on this webpage is subject to change due to the development of COVID-19 and the arrangement on campus.
The lecture for how to give a clear talk is here, and this is the link to the evaluation form for your course presentation.
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 |
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.
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.
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.
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.
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.
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