CSCI2100/ESTR2102 Data Structures

Offered by Yufei Tao, Fall 2020. Tutors: Shiyuan Deng (sydeng@link.cuhk.edu.hk), Shangqi Lu (sqlu@cse.cuhk.edu.hk), and Hao Wu (wuhao@link.cuhk.edu.hk). Quick navigation links: [Lecture Notes][Notes for ESTR2102] [Tutorials][Regular exercises][Special exercises][Quizzes, Assignment, and Exams] [Project]

Brief Description

In this course, we will study the fundamental data structures and algorithms. Such knowledge is at the core of computer science and allows us to write faster programs, especially ones 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 30 (19 Dec): Final exam stats released. News 29 (5 Dec): The final exam will take place at 9:30 am, 16 Dec. Here is the Zoom link: https://cuhk.zoom.us/j/91211307338. The exam will have 4 sessions, each 30 minutes long. Each session will be organized as follows: At the beginning, the questions will be released at a URL, which will be announced in Zoom's chatbox. In the meantime, a link will be created in Blackboard to collect your submissions. You must upload your work to Blackboard or email it to the instructor at taoyf@cse.cuhk.edu.hk within 30 minutes after the session has started. There will be a 5-minute break between two sessions. The whole exam is expected to last for 2.5 hours. For every session, you must hand-write your solutions on paper, take a picture of your solutions together with your student ID card or a Photo ID (a national ID card or the passport page), and submit the picture. The scope covers everything in Lect Notes 1-22. News 28 (1 Dec): Regular/special exercise list 13 released. News 27 (29 Nov): Quiz 2 solutions released. News 26 (16 Nov): Regular/special exercise list 12 released. News 25 (17 Nov): Quiz 2 will be held in the lecture on 24 Nov. The scope covers everything in Lect Notes 14-17. The questions will be released with an URL at the beginning of the quiz. You will need to submit a picture containing your hand-written work and student ID card within 20 minutes after the URL is released. We will collect your submission in the Blackboard system. You can submit multiple times, but only the last submission before the deadline will be graded. News 24 (19 Nov): Regular/special exercise list 11 released. News 23 (16 Nov): A link has been created in Blackboard to collect your project submissions. News 22 (12 Nov): The project has been released. Scrow down to the bottom of the page to see the description. Your submission is due at 11:59 pm, 12 Dec (one month from now). News 21 (12 Nov): Regular/special exercise list 10 released. News 20 (10 Nov): Midterm solutions released. News 19 (7 Nov): The assignment has been released. Scrow down to the bottom of the page to see the paper. Your submission is due at 11:59 pm, 15 Nov. A link has been created in Blackboard to collect your submissions. Late submissions will not be accepted. News 18 (5 Nov): Regular/special exercise lists 8 and 9 released. News 17 (24 Oct): The midterm scope covers everything from Lect notes 1-13. The midterm will take place in the lecture of Nov 2. All submissions must follow the same requirements as stated in News 12. News 16 (21 Oct): Regular/special exercise list 7 released. News 15 (14 Oct): Quiz 1 solutions released. News 14 (14 Oct): Regular/special exercise list 6 released. News 13 (10 Oct): Regular/special exercise list 4 and 5 released. News 12 (6 Oct): Quiz 1: will be held in the lecture on 13 Oct. The scope covers everything from Lect Notes 1-5. The questions will be released with an URL at the beginning of the quiz. You will need to submit a picture containing your hand-written work and student ID card within 15 minutes after the URL is released. We will collect your submission in the Blackboard system. You can submit multiple times, but only the last submission before the deadline will be graded. News 11 (5 Oct): Arrangements for quizzes, assignments, projects, exams:: There will be two quizzes, a midterm exam, one take-home assignment, a coding project, and a final exam. Quiz 1 will take place in the Tue lecture of Week 6. Midterm will take place in the Mon lecture of Week 9. Quiz 2 will take place in the Tue lecture of Week 12. The take-home assignment will be released in Week 9. The coding project will be released after we have discussed the insertion algorithm of the binary search tree. The university will release the time of the final exam. Each quiz will be 15 mins long. The questions will be released at the beginning of those 15 minutes. You need to submit your answers in the Blackboard system. The midterm has two sessions, each of which will be 20 mins long. In each session, the questions will be released at the beginning, and you need to submit your answers in the Blackboard system. All quizzes and exams will be open book. News 10 (30 Sep): Regular Exercise List 3 and Special Exercise List 3 released. News 9 (23 Sep) No exercise lists this week (List 3 will be released next week). News 8 (16 Sep): Regular Exercise List 2 and Special Exercise List 2 released. News 7 (10 Sep): (ESTR2102) Lecture of 09/10 and the whiteboard image now in the Blackboard system. News 6 (8 Sep): Regular Exercise List 1 and Special Exercise List 1 have been released. Read the "Grading Scheme" section for the style of exams. News 5 (8 Sep): Lecture of 09/08 and the whiteboard image now in the Blackboard system. News 4 (7 Sep): Lecture of 09/07 and the whiteboard image can now be found in the Blackboard system. I will do so after every lecture, provided that the video capturing mechanism does not fail. News 3 (6 Sep): No tutorials in Week 1. News 2 (5 Sep): See the "Time and Zoom Links" section for the Zoom links of the lectures/tutorials. News 1 (5 Sep): Hello, all.

Time and Zoom Links

Lectures Mon 9:30am - 10:15am, Zoom link Tue 12:30pm - 2:15pm, Zoom link (ESTR2102 only) Thu 1:30pm - 2:15pm, Zoom link Tutorials (2 sessions per week, same content) Wed 4:30pm - 5:15pm, Zoom link Thu 12:30pm - 1:15pm Zoom link

Grading Scheme

In-Class Quiz 1 or Assignment 1: 5% In-Class Quiz 2 or Assignment 2: 5% In-Class Quiz 3 or Assignment 3: 5% Midterm Exam: 20% Coding project: 15% Final Exam: 50% Style of the Final Exam for CSCI2100: During this course, the instructor will gradually generate a list of special exercises without the solutions given. In the final exam, 20% of the marks will come from problems taken almost directly (only with minor changes) from that list. The rest 80%, however, will be from new problems. Style of the Final Exam for ESTR2102: All problems may be new. Style of the Midterm Exam for CSCI2100/ESTR2102: All problems may be new. Cheat-Sheet for CSCI2100/ESTR2102: In the midterm/final exam, you will be allowed to consult a single-sided, A4-sized, note-sheet on which you can print/write anything useful. All quiizes and exams will be open-book.

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 -- 2 Binary Search and Worst-Case Analysis -- 3 Asymptotic Analysis: Growth of Functions Sections 3.1 and 3.2 4 Recursion (the Beginning) Chapter 1, and Sections 2.1, 2.2 5 Merge Sort Section 2.3 6 Two Methods for Solving Recurrences Sections 4.3 and 4.5 7 RAM Model with Randomization -- 8 Quick Sort Sections 7.1-7.4 9 Counting Sort Section 8.2 (the textbook's algorithm solves a slightly more general problem, as will be discussed in the tutorial) 10 k-Selection Section 9.2 (the textbook's algorithm requires a more tedious analysis, as will be discussed in a regular exercise) 11 Linked Lists, Stacks, and Queues Sections 10.1-10.2 12 Dynamic Arrays and Amortized Analysis Section 17.4.1. 13 Hashing Sections 11.1-11.3 14 Basic Definitions and Properties of Trees -- 15 Priority Queues (Binary Heaps) 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) Sections 12.1-12.2. 17 Binary Search Trees (Dynamic Version) -- 18 Basic Concepts of Graphs Section 22.1 19 Breadth First Search Section 22.2 20 Depth First Search Section 22.3 21 Topological Sort Section 22.4 22 Single Source Shortest Paths with Positive Weights Sections 24.2 and 24.3 23 (Bonus) Minimum Spanning Trees (will not be tested in the final exam) Chapter 23 (you may leave out Kruskal's algorithm)

Tutorial Material

Week 2 Slides 1: Cost of your programs Slides 2: More on binary search Week 3 Slides 1: More on big-O Slides 2: Examples of proving big-O Week 4 More on merge sort and binary search Week 5 The tutorial will discuss Problems 3 and 6 in Regular Exercise List 3. Week 6 Sorting multisets Week 7 Counting sort, linked lists, and dynamic arrays Week 8 More on hashing Week 9 Storing and traversing a tree Week 10 Applications of binary heaps Week 11 BST contruction, count BSTs, and others Week 12 BFS, DFS, and the proof of the white path theorem Week 13 More on Dijkstra's Algorithm (examples and correctness proof)

Notes for ESTR2102

Students of CSCI2100 are not required to understand the following material. Lecture Notes Textbook Reading (If a Book is Owned) 1 More on Computation Models "RAM2", comparison-based model, and a lower bound for dictionary search -- 2 Recursion Tower of Honoi and GCD algorithms Section 31.2 3 Lower Bound of Comparison-Based Sorting Section 8.1 4 Random Binary Search -- 5 Expected cost of quick sort (slides in Lect Notes 8) Section 5.4.1 6 Charging Arguments -- 7 Linear Time Sorting in Polynomial Domains Section 8.3 8 k-Selection (Deterministic) Section 9.3 9 Proof of Universality (slides in Lect Notes 13) Section 11.3

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). 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. [k-Selection] Exercises 9.3-6, 9.3-9, Problem 9-2. [Sorting] Exercises 8.1-3*, 8.1-4*, 8.2-4, 8-5*. [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*. [BFS] Exercises 22.2-5, 22.2-7, 22.2-8. [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. [Fundamental Graph Challenges] Problems 22-2(e-h), 22-3, 22-4. [SSSP] Exercises 24.3-6*, 24.3-7. [MST] Exercises 23.1-3, 23.1-5, 23.1-8, 23.1-9, 23.1-10, 23.1-11. Problems 23-1, 23-4*.

Special Exercises

As mentioned earlier, some problems in the final exam of CSCI2100 will be taken almost directly (only with minor changes) 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 (e.g., you may discuss them with your friends, the tutors, or even the instructor himself). Remember: during the final exam, you will be allowed to consult only one piece of single-sided A4-sized paper. Special exercises in general are easier than regular exercises. 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.

Quizzes, Assignments, and Exams

Quiz 1: Solutions Average = 72 (combining CSCI2100 and ESTR2102). Top 20 scores (combining CSCI2100 and ESTR2102) Assignment: Download the questions here Deadline: Nov 15, 11:59 pm. Midterm paper 1: Solutions Midterm paper 2: Solutions Average = 46 (combining CSCI2100 and ESTR2102). Top 20 scores (combining CSCI2100 and ESTR2102) Quiz 2: Solutions Average = 73 (combining CSCI2100 and ESTR2102). Top 20 scores (combining CSCI2100 and ESTR2102) Final exam: Average = 48 (combining CSCI2100 and ESTR2102). Top 20 scores (combining CSCI2100 and ESTR2102)

Project

Description. Deadline: 11:59pm, 12 Dec, 2020. Click here to download half of the operation dataset (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 collection link will be created in Blackboard on Nov 16.