## CS141 Intermediate Data Structures and Algorithms

Tuesday & Thursday 6:30 – 7:50 PM Online (via Zoom)

Instructor: **Yihan Sun** -
Email : yihans@cs.ucr.edu Office Hour: 4-5pm Thursday

**Yan Gu** -
Email : ygu@cs.ucr.edu Office Hour: 3-4pm Monday

TA: Irem Ergun - Email: iergu001@ucr.edu Office Hour: Tuesday 3-4pm

Sakib Md Bin Malek - Email: sakib.binmalek@email.ucr.edu Office Hour: Monday 1-2pm

### Course Information

The course explores basic algorithm analysis using asymptotic notations, summation and recurrence relations, and algorithms and data structures for discrete structures including trees, strings, and graphs. The topics cover general algorithm design techniques including analysis of algorithms, divide-and-conquer, the greedy method, dynamic programming, graph algorithms and basic parallel algorithms. It integrates knowledge of data structures, algorithms, and programming.

Lecture: 3 hours. Discussion: 1 hour.

Prerequisite(s): CS 014 with a grade of “C-” or better; CS 111; MATH 009C or MATH 09HC; proficiency in C++.

#### Other Useful Tools

You could post your questions or problems you want to discuss on Piazza.

All written homework solutions should be submitted via Gradescope.

All programming assignments should be submitted via CodeForces.

#### Calendar:

### Reading Materials

Name | Author | Publisher | Link |
---|---|---|---|

Introduction to algorithms (CLRS). Third Edition | Cormen, Leiserson, Rivest, and Stein | MIT Press | UCR library |

### Course Schedule

Dates | Topic | Reading | Attachment | Homework |
---|---|---|---|---|

Thu 10/1 | Introduction | § 1, 2 | Slides | Video (Yan) | Video (Yihan) | Homework 1 Out |

Tue 10/6 | Analysis | § 2, 3 | Slides | Video | |

Thu 10/8 | Divide-and-conquer algorithms | § 4.1-4.4 | Slides | Video | |

Tue 10/13 | Master Theorem | § 4.3-4.5 | Slides | Video | Homework 2 Out |

Thu 10/15 | Average analysis | § 5 | Slides | Video | |

Tue 10/20 | Greedy algorithms I | § 16 | Slides | Video | |

Thu 10/22 | Greedy algorithms II | § 16 | Slides | Video | |

Tue 10/27 | Dynamic programming I | § 15 | Slides | Video | |

Thu 10/29 | Midterm I | Homework 3 Out | ||

Tue 11/3 | Midterm 1 Review | Slides | Video | ||

Thu 11/5 | Dynamic programming II | § 15 | Slides | Video | |

Tue 11/10 | Dynamic programming III | § 15 | Slides | Video | |

Thu 11/12 | Graph algorithms I | § 22.1-22.3, 23 | Slides | Video | Homework 4 Out |

Tue 11/17 | Graph algorithms II | § 23, 24.1, 24.2 | Slides | Video | |

Thu 11/19 | Graph algorithms III | § 24.1, 24.2 | Slides | Slides (midterm2) | Video | Video (Bellman-Ford) | |

Tue 11/24 | Midterm II | Homework 5 Out | ||

Thu 11/26 | Happy Thanksgiving! | |||

Tue 12/1 | Parallel algorithms | § 27 | Slides | Video | |

Thu 12/3 | Parallel algorithms | § 27 | Slides | Video | |

Tue 12/8 | Road ahead | |||

Thu 12/10 | Review Session | Slides | Video |

### Discussions

### Assignments

#### Written Assignments

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

Release Date | Due Date | Assignment | Template | Solution |
---|---|---|---|---|

Thu 10/01 | Tue 10/13 11:59pm | Assignment 1 | Solution Template | Solution 1 |

Tue 10/13 | Mon 10/26 11:59pm | Assignment 2 | Solution Template | Solution 2 |

Tue 10/29 | Fri 11/13 11:59pm | Assignment 3 | Solution Template | Solution 3 |

Tue 11/10 | Mon 11/23 11:59pm | Assignment 4 | Solution Template | Solution 4 |

Tue 11/24 | Mon 12/07 11:59pm | Assignment 5 | Solution Template | Solution 5 |

#### Programming Assignments

Here you can find readme file for submitting solutions on CodeForces.

Release Date | Due Date | Problem | Template | Sample Tests |
---|---|---|---|---|

Thu 10/01 | Sun 10/18 11:59pm | Problem 1 | C++ | Java | Tests |

Tue 10/13 | Sun 11/01 11:59pm | Problem 2 | C++ | Java | Tests |

Tue 10/27 | Sun 11/15 | Problem 3 | C++ | Java | Tests |

Tue 11/10 | Sun 11/29 | Problem 4 | C++ | Java | Tests |

Tue 11/24 | Mon 12/07 | Problem 5 | C++ | Java | Tests |

### Policy

#### Grading

Class Participation: 5% bonus

Assignments: 30% (written assignments) + 5% bonus (programming assignments)

Midterm: 20%+20%

Final exam: 30%

#### Late Policy

You have 4 late days and 2 grace days to use across the quarter. However, for each homework assignment, you can use no more than two (late_days+grace_days). This means that for each assignment, you have at most 48 hours after the deadline.

You will lose 20% of your score for each late day you use for one homework
assignment. If you use grace days, you don't lose points. If you use any of the grace days, please indicate it at the beginning of your solution.

For example, if you don't use any grace day:

* If you submit it within 24 hours after deadline, you get 80% of the points you earn.

* If you submit it within 48 hours after deadline, you get 60% of the points you earn.

* If you submit it later than 48 hours after the deadline, you don’t get any points for this homework.

If you use one grace day:

* If you submit it within 24 hours after deadline, you get 100% of the points you earn.

* If you submit it within 48 hours after deadline, you get 80% of the points you earn.

* If you submit it later than 48 hours after the deadline, you don’t get any points for this homework.

If you use two grace days:

* If you submit it within 24 hours after deadline, you get 100% of the points you earn.

* If you submit it within 48 hours after deadline, you get 100% of the points you earn.

* If you submit it later than 48 hours after the deadline, you don’t get any points for this homework.

#### Plagiarism Warning

#### Cheating or plagiarism will NOT be tolerated!!!

Check UCR academic integrity for additional information.

**For homework assignments:**

You **CAN** get help from the instructors, TAs, textbooks (or relevant books), the Internet, but **NOT** your classmates. You **CANNOT** copy anything from the book or the Internet. When you write down your solution, it **MUST** be close-book.

### Other Suggestions

**You need basic knowledge about algorithms, data structures, and discrete math.**Courses such as CS14 is helpful. If you don't have some basic background in algorithms, you should take these courses first. If you don't have such basic knowledge and you still want to take the course, you 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 in 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.**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).
- These are real time amounts spent by average successful past students. Computer Science and Engineering are challenging disciplines requiring extensive time to master. (Numbers from Prof. Lonardi's website for previous CS141).