CSCI2100/ESTR2102 Data Structures

Offered by Yufei Tao, Fall 2021. Tutors: Shiyuan Deng (sydeng@link.cuhk.edu.hk), Ru Wang (rwang21@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 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 12 (17 Nov): Quiz 3 will take place in the lecture of 23 Nov. The quiz will be 20 minutes long and its scope covers everything from Lect Notes 15-17. News 11 (14 Nov): Project released. Please find the description at the bottom of the page. News 10 (2 Nov): Quiz 2 will take place in the lecture of 9 Nov. The quiz will be 20 minutes long and its scope covers everything from Lect Notes 11-13. News 9 (18 Oct): The midterm exam will take place in the lecture of Oct 25 (Mon, Week 8). The exam will be 40 minutes long and its scope covers everything from Lect Notes 1-10. News 8 (24 Sep): Test schedule of the course: Quiz 1: 5 Oct (Tue), Midterm: 25 Oct (Mon), Quiz 2: 9 Nov (Tue), Quiz 3: 23 Nov (Tue). Sick Leave Policy: If you want to be absent from a quiz/exam by citing health reasons, you must email the instructor your application at least one hour before the test and follow up with a doctor's letter. News 7 (24 Sep): Quiz 1 will take place in the lecture of Oct 5 (Tue, Week 5). The quiz will be 20 minutes long and its scope covers everything from Lect Notes 1-5. IMPORTANT: You must to take the quiz in the classroom, unless you have obtained prior approval from the instructor to take the test online. In general, approval will be given only to students with genuine travel restrictions that prevent them from coming to the campus. To apply for an approval, email the instructor and provide evidence on your restrictions. Once an approval is given, it will be effective throughout the semester, as long as your restrictions do not change. News 6 (21 Sep): Starting from the next week, the venue for Wed tutorials will be changed back SC L4 (i.e., the venue listed in CUSIS). News 5 (14 Sep): The Zoom link of this week's tutorial has been released (find the tutorial slides and the link is just below them). Tutorial Zoom links are not persistent and will be released each week in the same manner. News 4 (13 Sep): To find the video links, search for the word "video" on this page. News 3 (1 Sep): The tutorial of Sep 15 will take place in Chen Kou Bun Building LT3. The original venue, SC L4 will be under maintenance during the first two weeks. We expect to move back to SC L4 probably in Week 3. News 2 (1 Sep): There will be no tutorials in the first week. News 1 (1 Sep): Hello, all.

Time, Venues, and Zoom Links

Lectures Mon, 9:30am - 10:15am, Basic Med Sci Bldg G18 Zoom Link Tue, 12:30pm - 2:15pm, Basic Med Sci Bldg G18 Zoom Link (ESTR2102 only) Thu 1:30pm - 2:15pm, Basic Med Sci Bldg Rm2 Zoom Link Tutorials (2 sessions per week, same content) Wed 4:30pm - 5:15pm, Science Center L4 Thu 12:30pm - 1:15pm Fung King Hey Bldg Swire Hall1 Click here for a campus map.

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. 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 Video -- 2 Binary Search and Worst-Case Analysis Video -- 3 Asymptotic Analysis: Growth of Functions Video 1, Video 2 Sections 3.1 and 3.2 4 Recursion (the Beginning) Video Chapter 1, and Sections 2.1, 2.2 5 Merge Sort Video Section 2.3 6 Two Methods for Solving Recurrences Video1, Video2 Sections 4.3 and 4.5 7 RAM Model with Randomization Video 1, Video 2 Video from my previous offering -- 8 k-Selection Video Section 9.2 (the textbook's algorithm requires a more tedious analysis, as will be discussed in a regular exercise) 9 Quick Sort (for video, see counting sort) Sections 7.1-7.4 10 Counting Sort Video Section 8.2 (the textbook's algorithm solves a slightly more general problem, as will be discussed in the tutorial) 11 Linked Lists, Stacks, and Queues Video Sections 10.1-10.2 12 Dynamic Arrays and Amortized Analysis Video Section 17.4.1 13 Hashing Video Sections 11.1-11.3 14 [Discrete Math Review] Basic Definitions and Properties of Trees -- 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 1, Video 2, Video 3 -- 18 [Discrete Math Review] Basic Concepts of Graphs Section 22.1 19 Breadth First Search (for video, see DFS) Section 22.2 20 Depth First Search Video 1, Video 2 Section 22.3 21 Topological Sort Video Section 22.4 22 Single Source Shortest Paths with Positive Weights Video 1, Video 2 Sections 24.2 and 24.3

Tutorial Material

Week 2 Slides 1: Cost of Your Programs Slides 2: Exercises for Discussion Zoom Link (Presented by Shiyuan Deng) Week 3 Predecessor Search, Big-O, and More Zoom Link (Presented by Ru Wang) Week 4 Recursion and More Zoom Link (Presented by Hao Wu) Week 5 The tutorial will discuss Problems 3 and 6 in Regular Exercise List 3. Zoom Link (Presented by Shiyuan Deng) Week 6 Randomization and Multiset Sorting Zoom Link (Presented by Ru Wang) Video Week 7 Counting Sort and Counting Inversions Zoom Link (Presented by Hao Wu) Video Week 8 Dynamic Arrays and Stacks Zoom Link (Presented by Shiyuan Deng) Video Week 9 Hashing Zoom Link (Presented by Hao Wu) Video Week 10 Priority Queues Zoom Link (Presented by Ru Wang) Video (unfortunately, the audio quality is not very good) Week 11 BSTs Zoom Link (Presented by Shiyuan Deng) Video Week 12 BFS, DFS, and the Proof of the White Path Theorem Zoom Link (Presented by Hao Wu) Video Week 13 Connected Components and Dijkstra Zoom Link (Presented by Ru Wang) Video

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 k-Selection (Deterministic) Section 9.3 5 Random Binary Search -- 6 Expected Cost of Quick Sort (see the CSCI2100 notes about quick sort) Section 5.4.1 7 Charging Arguments -- 8 Proof of Universality (slides in Lect Notes 13) Section 11.3 9 Linear Time Sorting in Polynomial Domains Section 8.3 10 Perfect Hashing Section 11.5

Regular Exercises

The instructor has prepared the following exercises which he believes are useful for students to consolidate their understandings 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. [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*. [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.

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). 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 = 75, standard deviation = 22 (combining CSCI2100 and ESTR2102, same below). Midterm: Solutions Average = 53, standard deviation = 20, top-15 scores. Quiz 2: Solutions Average = 76.4, standard deviation = 16.1. Quiz 3: Solutions Average = 79.47 standard deviation = 20.1. Final exam: Average = 62, standard deviation = 16.7, top 15 scores.

Project

Description. Deadline: 11:59pm, 20 Dec, 2021. 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.