| CSCI2100B Data Structures | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Offered by Yufei Tao, Spring 2023. Tutors: Shiyuan Deng (sydeng@link.cuhk.edu.hk), Ru Wang (rwang21@cse.cuhk.edu.hk), and Hao Wu (wuhao@link.cuhk.edu.hk).
[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 13 (11 Apr): Quiz 3 is canceled. News 12 (4 Apr): The project has been released. The deadline is 11:59pm, 4 May. News 11 (23 Mar): The instructor will be on conference leave next week. Here are the arrangements for the lectures on Mar 29 and 30.
News 10 (7 Mar): Your midterm scores have been released in Blackboard. You can now collect your papers from the TA responsible for your ID - see News 7. News 9 (1 Mar): The instructor will be on conference leave during the week of Mar 27. The lecture on Mar 29 will be delivered on Zoom. Quiz 2, which was scheduled on Mar 29, will now take place in the lecture of Mar 30 and will be administered by TAs. News 8 (16 Feb): The scope of the midterm exam covers everything in Lect Notes 1-10. News 7 (15 Feb): Your Quiz 1 scores have been released in Blackboard. You can now collect your Quiz 1 papers from the TAs. Each TA handles a specific range of student IDs:
News 6 (3 Feb): The scope of Quiz 1 covers everything in Lect Notes 1-5. News 5 (26 Jan): Please note the test schedule for this course:
News 3 (11 Jan): The video of today's lecture has been released. There will be no more reminders for video releases. Please check this page periodically. Note that the instructor is not required - nor does he promise - to release lecture videos. But he plans to do so as long as a lecture has been successfully recorded by Zoom. News 2 (9 Jan): No tutorials in Week 1. News 1 (9 Jan): Hello, all. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Time, Venues, and Zoom Links | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Lectures Wed, 2:30pm - 4:15pm, Science Center L1, Zoom Link Thu, 10:30am - 11:15am, T.Y.Wong Hall LT, Zoom Link Tutorials (2 sessions per week, same content) Wed, 5:30pm - 6:15pm, Lady Shaw Bldg LT5, Zoom Link Thu, 5:30pm - 6:15pm, Lady Shaw Bldg LT2, Zoom Link 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.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Tutorial Material | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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) - Updated at 11pm, 15 Feb. List 4 (Solutions). List 5 (Solutions). List 6 (Solutions) - Updated at 10pm, 24 March. List 7 (Solutions). List 8 (Solutions). List 9 (Solutions). List 10 (Solutions). List 11 (Solutions). List 12 (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. [BFS] Exercises 22.2-5, 22.2-7, 22.2-8. [Topological Sort] Exercises 22.4-2, 22.4-3, 22.4-5. [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. There will be no more special exercises. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Quizzes and Exams | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Quiz 1: Solutions Average = 73, standard deviation = 22. Midterm: Solutions Average = 63, standard deviation = 23, top-20 scores. Quiz 2: Solutions Average = 66.2, standard deviation = 19.0. Final exam: Average = 57, standard deviation = 16.8, top-20 scores. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Project | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Description. Deadline: 11:59pm, 4 May, 2023. Click here to download half of the data and query files (the other half is hidden from you, as explained in the description). Note: Use a "good" text editor to open the file. Do not use Windows NotePad. A link has been created in Blackboard to collect your submissions. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|