Data Structures

CSCI2100B Data Structures

Offered by Yufei Tao, Spring 2025.

Tutors: Hao Chen (hchen22@link.cuhk.edu.hk), Xingyu Cui (xycui24@cse), and Zeju Li (lizeju@link.cuhk.edu.hk).

Offices and Consultation Hours:

Yufei Tao: 4pm-5pm Tue, SHB 1011
Hao Chen: 3:30pm-4:30pm Wed, RM 404 Academic Building No. 1
Zeju Li: 4pm-5pm Thu, SHB 1013
Xingyu Cui: 2pm-3pm Fri, SHB 913

Quick navigation links:
[Lecture Notes][Tutorials][Regular Exercises][Special Exercises][Quizzes and Exams][Project]

Brief Description

In this course, we will study fundamental data structures and algorithms. Such knowledge is at the core of computer science and allows us to write faster programs, especially programs whose running time has attractive worst-case bounds. Techniques for analyzing the performance of algorithms will also be discussed in detail. Tentative topics to be covered include searching in ordered lists, hashing, sorting, priority queues, binary search trees, fundamental graph algorithms, and so on.

Announcements

News 21 (7 May): The final exam scores have been released on Blackboard. The solutions and statistics can be found in the "Quizzes and Exams" section of this page.

You may come to check your papers on 9 May from 2:30pm to 6:30pm. The venue is Room 1011, Ho Sin-Hang Engineering Building. Please obey the following rules:

You cannot take your paper away. We are required to archive all the final exam papers.
You are not allowed to take pictures of the question paper or the answer book.
You may check the papers of your friends, provided that you can provide evidence of their consent.

No additional paper-checking sessions will be arranged. However, you may submit a grade appeal after the grade release in accordance with university guidelines.

News 20 (5 May): Your project scores have been released on Blackboard.

News 19 (16 Apr): Quiz 3 scores have been posted on Blackboard. The solutions and statistics can be found at the bottom of the page. You may now collect your Quiz 3 papers following the rules described in News 11.

News 18 (7 Apr): Quiz 3 will take place in the lecture of next Mon (14 Apr). The scope covers everything in Lectures 17-20. The quiz will be open book.

News 17 (6 Apr): The midterm scores have been released on Blackboard. The solutions and statistics can be found in the "Quizzes and Exams" section of this page. You may now collect your exam papers from the TAs assigned to your IDs (see News 11). To do so, visit their offices during the designated consultation periods.

News 17 (18 Mar): The lecture of 25 Mar is canceled because the instructor will be on conference leave on that day.

News 16 (13 Mar): The scope of the midterm covers Lectures 1-16. Please read about the exam style in the "Grading Scheme" section.

News 15 (10 Mar): New Video Release Policy: The instructor has noticed a growing trend among students who prefer watching lecture videos instead of attending the lectures in person. This undermines the purpose of releasing videos and significantly impacts the classroom teaching atmosphere. Therefore, from now on, lecture videos will be released based on two conditions: (i) successful capture of the video via Zoom, and (ii) attendance of at least 30 students (i.e., 1/3 of the class) during the lecture. The new policy will be enforced starting from 11 Mar.

News 14 (1 Mar): The project has been released. The deadline is 27 Apr 2025. Please submit your work in Blackboard.

News 13 (27 Feb): Quiz 2 scores have been posted on Blackboard. The solutions and statistics can be found at the bottom of the page. You may now collect your Quiz 2 papers following the rules described in News 11.

News 12 (18 Feb): Quiz 2 will take place in the lecture of next Mon (Feb 24). The scope covers everything in Lectures 7-12. The quiz will be open book.

News 11 (14 Feb): Quiz 1 scores have been posted on Blackboard. The solutions and statistics can be found at the bottom of the page.

You may now collect your Quiz 1 papers. To do so, please locate the TA assigned to your ID from the list below. Then, visit their offices during the designated consultation periods. If needed, you may also consider reaching out to the TA via email to request a special appointment. Please note that it is at the TA's discretion to decide whether to grant your request.

Hao Chen: 1155144568 - 1155210958
Xingyu Cui: 1155210983 - 1155212489
Zeju Li: 1155212561 - 1155240479

News 10 (11 Feb): The instructor will be on conference leave on Mar 24 and 25. To avoid canceling the lecture of Mar 24, we will hold the midterm exam in that lecture. For that purpose, we will swap the dates of Quiz 2 and the midterm exam. After the swap, Quiz 2 will take place in the lecture of Feb 24 (Mon, Week 7), and the midterm exam in the lecture of Mar 24 (Mon, Week 10). The test schedule in News 3 has been updated accordingly.

The lecture on Mar 25, however, will be canceled.

News 9 (21 Jan): The scope of Quiz 1 covers everything in Lectures 1-6.

News 8 (9 Jan): Given that 27 Jan is very close to the Lunar New Year, Quiz 1 will be rescheduled to the lecture on 4 Feb (Tue, Week 4).

News 7 (7 Jan): Regular exercise 1 and Special exercise 1 have been released. Please find them at the bottom of the page. There will be no more reminders for exercise releases. Please check this page periodically.

News 6 (7 Jan): Tutorials will start from Week 2 (no tutorials on Jan 8 and 9).

News 5 (7 Jan): The video for Tue's lecture is now available. In general, lecture videos will be released as long as they are captured successfully. Remember: videos are supplemental and cannot be guaranteed. There will be no more announcements regarding video releases. Please check this page periodically.

News 4 (5 Jan): Sick Leave Policy for Tests
In the unfortunate event that you are seriously ill on the day of a quiz or an exam, you can be absent from the test provided that the following conditions are satisfied.

You must email the instructor at least 4 hours before the start time of the lecture in which the test is administered.
You must provide a doctor's certificate within 12 hours after the test's end time. The certificate must state your illness clearly. The instructor generally accepts certificates indicating illnesses that are highly contagious, involve high fever, hamper movements, or require hospitalization, but rejects certificates for common illnesses such as cold, headaches, diarrhea, bronchitis, rashes, or gastroenteritis. You may be required to attend an interview with the instructor if deemed necessary.

Real emergency cases will be handled separately.

News 3 (5 Jan): Please note the test schedule for this course:

Quiz 1 (20 minutes) is to be held in the lecture of ~~27 Jan (Mon, Week 4)~~ 4 Feb (Tue, Week 4);
~~Midterm Exam (90 minutes)~~ Quiz 2 (20 minutes) is to be held in the lecture of 24 Feb (Mon, Week 7);
~~Quiz 2 (20 minutes)~~ Midterm Exam (90 minutes) in the lecture of 24 Mar (Mon, Week 10);
Quiz 3 (20 minutes) in the lecture of 14 Apr (Mon, Wed 13).

News 2 (5 Jan): Tutorial Session T03 has been merged into T01. Previously, T03 was scheduled to take place in Y.C. Liang Hall 103 every Wed from 5:30pm to 6:15pm. The new location will be Science Centre LG23, and the time remains unchanged.

News 1 (5 Jan): Hello, all.

Time, Venues, and Zoom Links

Lectures

Mon, 4:30pm - 6:15pm, Science Center L1, Zoom Link
Tue, 2:30pm - 3:15pm, Mong Man Wai Bldg LT1, Zoom Link

Tutorials (2 sessions per week, same content)

Wed (Session T01), 5:30pm - 6:15pm, Science Centre LG23
Thu (Session T02), 5:30pm - 6:15pm, Science Centre LG23
Note: Tutorial Session T03 has been merged into T01.

Click here for a campus map.

Grading Scheme

In-Class Quiz 1: 5%
In-Class Quiz 2: 5%
In-Class Quiz 3: 5%
Midterm Exam: 20%
Coding Project: 15%
Final Exam: 50%

Exam Style:
During this course, the instructor will gradually generate a list of special exercises with no solutions given. In the midterm and final exams, 35% of the marks will come from problems taken directly from that list. The rest 65%, however, will be from new problems. In the midterm and the final exams, you will be allowed to bring in a single-sided, A4-sized, note sheet on which you can print/write anything you deem useful.

Lecture Notes and Textbook

The instructor recommends the following textbook:
Introduction to Algorithms, 3rd Edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Ownership of the book is not compulsory. The instructor will make lecture notes available before each lecture. His notes will be self-contained, namely, containing all the details required in this course.

Lecture attendance is vital to grasp the material taught.

	Lecture Notes	Textbook Reading (If a Book is Owned)
1	The RAM Model (the video of this lecture was not captured successfully)	--
2	Binary Search and Worst-Case Analysis (video)	--
3	Asymptotic Analysis: Growth of Functions (video)	Sections 3.1 and 3.2
4	Recursion (video)	Chapter 1, and Sections 2.1, 2.2
5	Merge Sort (video)	Section 2.3
6	Two Methods for Solving Recurrences (video, 52:00-end) (video, start-28:00)	Sections 4.3 and 4.5
7	RAM Model with Randomization (video, 28:00-end) (video, start-01:08:00)	--
8	k-Selection (video, 01:08:00-end)	Section 9.2 (the textbook's algorithm requires a more tedious analysis, as will be discussed in a regular exercise and a tutorial)
9	Quick Sort (video) Lower Bound of Comparison-Based Sorting (not testable)	Sections 7.1-7.4
10	Counting Sort (video, start-00:51:00) Linear Time Sorting in Polynomial Domains (not testable)	Section 8.2 (the textbook's algorithm solves a slightly more general problem, as will be discussed in a tutorial)
11	Linked Lists, Stacks, and Queues (video, 01:10:00-end) (video, start-00:24:05)	Sections 10.1-10.2
12	Dynamic Arrays and Amortized Analysis (video, 00:24:05-end) (video, start-00:50:00)	Section 17.4.1
13	Hashing (video, 00:50:00-end) (video) Perfect Hashing (not testable)	Sections 11.1-11.3
14	[Discrete Math Review] (Undirected) Graphs and Trees (updated at 6:50pm, 24 Feb) (video)	--
15	Priority Queues (Binary Heaps) (video)	You may read Section 6.5 but keep in mind that the textbook's algorithm does not really guarantee O(log(n)) worst-case time (due to the need of array expansion/shrinking).
16	Binary Search Trees (Static Version) (video)	Sections 12.1-12.2.
17	Binary Search Trees (Dynamic Version) (video) (video)	--
18	Graph Storage: Adjacency Lists	Section 22.1
19	DFS 1: Cycle Detection (video) (video)	Section 22.2
20	DFS 2: Topological Sort (video)	Section 22.4
21	BFS: SSSP with Unit Weights (video)	Section 22.3
22	Dijkstra: SSSP with Positive Weights (video, 00:48:00-end) (video)	Sections 24.2 and 24.3
23 (Bonus)	Minimum Spanning Trees (not testable) (video)	Chapter 23 (you may leave out Kruskal's algorithm)

Tutorial Material

Week 2	Slides 1: Cost of Your Programs Slides 2: Exercises for Discussion (video, by Hao Chen)
Week 3	Binary Search and Big-O (video, by Hao Chen)
Week 4	Recursion and Exercises (video, by Hao Chen)
Week 5	Slides 1: Another k-Selection Algorithm Slides 2: An In-Place Implementaion of Quick Sort (video, by Hao Chen)
Week 6	Sorting Key-Value Pairs (video, by Xingyu Cui)
Week 7	Slides 1: More on Linked Lists Slides 2: More on Dynamic Arrays (video, by Zeju Li)
Week 8	More on Hashing (video, by Xingyu Cui)
Week 9	A Dynamic-Array Implementation of the Binary Heap (video, by Zeju Li)
Week 10	More on BSTs (video, by Xingyu Cui)
Week 11	More on DFS (video, by Zeju Li)
Week 12	Connected Components and Correctness of BFS in SSSP (video, by Xingyu Cui)
Week 13	More on Dijkstra's (video, by Zeju Li)

Regular Exercises

The instructor has prepared the following exercises which he believes are useful for students to consolidate their understanding of the course material. Unlike the "special" exercises (see the next section), solutions to these "regular" exercises are provided in full.

Exercises carrying one or more stars ("*") may be difficult. The more stars, the more difficult.

List 1 (Solutions).
List 2 (Solutions).
List 3 (Solutions).
List 4 (Solutions).
List 5 (Solutions).
List 6 (Solutions).
List 7 (Solutions).
List 8 (Solutions).
List 9 (Solutions).
List 10 (Solutions).
List 11 (Solutions).
List 12 (Solutions).
List 13 (Solutions).
There will be no more regular exercises.

Additional exercises in the textbook
[Growth of Functions] Exercises 2.2-1, 3.1-2, 3.1-3, 3.1-4, 3.2-4, 3.2-8.
[Sorting] Exercises 8.1-3*, 8.1-4*, 8.2-4, 8-5*.
[k-Selection] Exercises 9.3-6, 9.3-9, Problem 9-2.
[Linked List] Exercises 10.2-6.
[Hashing] Exercises 11.2-5, 11.3-5*, Problem 11-2.
[Priority Queue] Exercises 6.1-4, 6.5-9, Problem 6-3.
[AVL-Tree] Exercises 12.1-3, 12.1-5, 12.2-5, 12.2-6, Problems 12-2, 13-1.
[Graph Basics] Exercises 22.1-5, 22.1-6*.
[DFS] Exercises 22.3-4, 22.3-7, 22.3-8, 22.3-10.
[Topological Sort] Exercises 22.4-2, 22.4-3, 22.4-5.
[BFS] Exercises 22.2-5, 22.2-7, 22.2-8.
[Fundamental Graph Challenges] Problems 22-2(e-h), 22-3, 22-4.
[SSSP] Exercises 24.3-6*, 24.3-7.

Special Exercises

As mentioned earlier, some problems in the final exam of CSCI2100 will be taken directly from the special exercise lists below. No solutions to these exercises will be given. You are free to look for the solutions in any way.

List 1.
List 2.
List 3.
List 4.
List 5.
List 6.
List 7.
List 8.
List 9.
List 10.
List 11.
List 12.
List 13.
There will be no more special exercises.

Quizzes and Exams

Quiz 1: Solutions
Average = 63.8, standard deviation = 21.3.

Quiz 2: Solutions
Average = 74.6, standard deviation = 23.9.

Midterm: Solutions
Average = 59.1, standard deviation = 22.8. Top 25 scores.

Quiz 3: Solutions
Average = 75.2, standard deviation = 28.2.

Final: Solutions
Average = 55.3, standard deviation = 12.9. Top 25 scores.

Project

Description (updated on 26 Mar).

Deadline: 11:59pm, 27 APR 2025.

A link has been created in Blackboard to collect your submissions. Please submit a single Zip file containing all the deliverables required.