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
Prerequisite knowledge in the book that will not be taught in this course: Plaese make sure you understand Sections 6, 10-13, and 22.1-22.3 in the book.

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).
>>>>>>>>>