CS142 Algorithm Engineering (aka. How to Write Faster Code)

Monday & Wednesday   5:00 – 6:20 PM    Online (via Zoom)
Discussion:    Tuesday    11:00 - 11:50 AM

Instructor: Yan Gu          Office Hour:    1:00 - 2:00 PM   Friday
TA: Xiaojun Dong          Office Hour:    4:00 - 5:00 PM    Tuesday

Course Information


This course provides comprehensive training for designing, analyzing, implementing, and reasoning efficient algorithms. Designing efficient algorithms is one of the most useful skills in computer science, but only taking basic algorithm courses is usually insufficient for developing this skill.

CS 142 Algorithm engineering will cover this training in two aspects. First, the students will receive a list of problems with real-world background, and solve them using the algorithmic knowledge from previous courses. Skills including problem formalization, algorithm design, optimization and implementation, and debugging will be exercised. Second, we will cover useful knowledge for parallelism, I/O-efficiency, and other system and architecture features to accelerate algorithms. At the end of the course, students will be equipped with knowledge in designing efficient algorithms in practice.

Lecture: 3 hours.    Discussion: 1 hour.
Prerequisite(s): CS 141 with a grade of “B-” or better.

Other Useful Tools

You could post your questions or problems you want to discuss on Piazza.
All homework solutions should be submitted via Gradescope.

Calendar:

Reading Materials


Name Author Publisher Link
Introduction to algorithms (CLRS). Third Edition Cormen, Leiserson, Rivest, and Stein MIT Press UCR library
Prerequisite knowledge in the book that will not be taught in this course: please make sure you have taken CS 141.

Course Schedule


Dates Topic Attachment Homework
Mon 1/4 Introduction Slides Training 1 out
Wed 1/6 Parallelism Slides
Mon 1/11 Parallelism Slides Homework 1 out
Wed 1/13 Instructor out of town
Mon 1/18 Martin Luther King Day Training 2 out
Wed 1/20 Parallelism Slides
Mon 1/25 Computer Architecture Slides Homework 2 out
Wed 1/27 Computer Architecture Slides
Mon 2/1 Computer Architecture and I/O efficiency Slides Training 3 out
Wed 2/3 I/O efficiency and Quiz Slides
Mon 2/8 Matrix Multiply Slides Homework 3 out
Wed 2/10 Dynamic programming Slides
Mon 2/15 Presidents Day Training 4 out
Wed 2/17 Geometric algorithms Slides
Mon 2/22 Graph algorithms Slides Project proposal due
Wed 2/24 Road ahead Slides
Mon 3/1 Training problems analysis (by students)
Wed 3/3 Training problems analysis (by students)
Mon 3/8 Project presentation 1
Wed 3/10 Project presentation 2

Discussions


Week Slides Video Handout
2 Slides Video Handout

Homework Assignments

Here you can find sample code for writng solutions using LaTeX.

Release Date Due Date Assignment Template
Mon 1/11 Wed 1/20 11:59pm Assignment 1 Solution Template
Mon 1/25 Wed 2/3 11:59pm Assignment 2 Solution Template
Mon 2/8 Wed 2/17 11:59pm Assignment 3 Solution Template

Training Assignments


Release Date Due Date Assignment
Mon 1/4 Wed 1/13 11:59pm Training 1
Mon 1/18 Wed 1/27 11:59pm Training 2
Mon 2/1 Wed 2/10 11:59pm Training 3
Mon 2/1 Wed 2/10 11:59pm Training 4

Policy

Grading

Problem-solving training: 20%
Homework assignments: 30%
Quiz: 5%
Exam: 25%
Final Project: 20%
Class Participation: 10% bonus

Late Policy

You have 2 grace days to use across the quarter. This means that for each assignment, you have at most 48 hours after the deadline.

Plagiarism Warning


Cheating or plagiarism will NOT be tolerated!!!

Check UCR academic integrity for additional information.

For homework assignments: "Clean Board Policy": it okay to talk to other students, but when you work together, you come with nothing (your code, your written solutions, etc.) and discuss at a whiteboard on which you collaborate. Once your discussion is over, wipe the board clean. Each student must walk away with the results of the discussion only in his/her head; do not copy anything down. When you are writing down your homework answers, do so alone and individually, reproducing your own understanding on paper.
You can get help from the instructors, TAs, textbooks (or relevant books), the Internet, but when you write down your solution, it MUST be close-book.

Other Suggestions


  • You need basic knowledge about algorithms, data structures, and discrete math. You must take CS141 as a prerequisite. If you don't have such basic knowledge and you still want to take the course, you need my permission and have to be aware that you need to spend more time on the course.
  • Reading slides and the textbook before each lecture could be very helpful. All course material will be available online before class.
  • You could participate in the discussions on Piazza. Paying attention to other students' questions can also be helpful for yourself.
  • Start working on homework assignments as early as possible. You have about 2 weeks for each of the homework assignment. However, don't start working on it on the last day. The homework problems can be hard and take a lot of time to finish. Also, the course server will be busy when the deadline is close.
  • Please don't underestimate the time you will need to spend on this course. You should expect to spend the following approximate amount of time:
    • 3 hours/week in lecture
    • 1 hour/week discussion
    • 6 to 10 hours/week doing individual study (readings, homework, programming, preparation for lectures, etc).
    • Computer Science and Engineering are challenging disciplines requiring extensive time to master.
>>>>>>>>>