| CSCI5610 Advanced Data Structures |
|
Offered by Yufei TAO, Spring 2020. TA: Pengguang Chen (1155113944@link.cuhk.edu.hk) Quick navigation links: [Lecture Notes][Exercises][Assignments/Quizzes/Exams] |
| Brief Description |
|
This course introduces advanced techniques for designing data structures with strong theoretical guarantees. Topics to be covered include (i) generic methods such as logarithmic rebuilding, weight balancing, partial persistence, tabulation, doubling dimension, locality sensitive hashing, etc., and (ii) specific structures such as the interval tree, the priority search tree, cuckoo hashing, the Euler-tour tree, the van Emde Boas structure, the suffix tree, etc. |
| Announcements |
|
News 25 (5 May): Final exam released. Deadline May 17. News 24 (27 Apr): Videos of Week 13 and Exercise list 13 released. News 23 (24 Mar): Assignment 3 released. Deadline May 3. News 22 (20 Apr): Videos of Week 12 and Exercise list 12 released. News 21 (8 Apr): Videos of Week 11 and Exercise list 11 released. News 20 (1 Apr): Videos of Week 10 and Exercise list 10 released. News 19 (30 Mar): Assignment 2 released. Deadline Apr 5. News 18 (25 Mar): Videos of Week 9 and Exercise list 9 released. News 17 (18 Mar): Videos of Week 8 and Exercise list 8 released. News 16 (13 Mar): Midterm released. Please scroll to the bottom to see it. News 15 (10 Mar): Videos of Week 7 and Exercise list 7 released. News 14 (3 Mar): Videos of Week 6 uploaded. Exercise list 6 released. News 13 (25 Feb): Exercise list 5 released. News 12 (25 Feb): Videos of Week 5 uploaded. News 10 (18 Feb): Assignment 1 released. Deadline Feb 27. News 9 (18 Feb): Exercise list 4 released. News 8 (17 Feb): Videos of Week 4 uploaded. News 7 (12 Feb): There will be no more classroom teaching until further notice. Videos will be uploaded each week. News 6 (12 Feb): The grading scheme has changed due to the virus. Check it out in the section below. News 5 (20 Jan): Exercise list 3 released. News 4 (19 Jan): The classroom for our Tue's lectures has been changed to L3, Science Centre for the rest of the semester. News 3 (14 Jan): Exercise list 2 released. News 2 (7 Jan): Exercise list 1 released. News 1 (3 Jan): Hello, all. |
| Time and Venues |
|
Lectures Mon: 10:30am - 12:15pm Room 712, William M W Mong Eng Bldg Tue: 10:30pm - 11:15pm L3, Science Centre Click here for a map of the campus. |
| Grading Scheme |
|
In-Class Quiz 1: 5% In-Class Quiz 2: 5% In-Class Quiz 3: 5% Midterm Exam: 35% Final Exam: 50% Update on Feb 12: Due to the coronavirus, each quiz/exam will be turned into a take-home assignment if classroom teaching has not resumed at the time of the quiz/exam. Style of Exams: During this course, the instructor will gradually generate a list of exercises without the solutions given. In the midterm and final exams, at least 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 |
|
The instructor will write up the lecture notes and make them available here: Download The above document will grow as the semester progresses. The following is the revision history: (Apr 27): Lect 18 is complete. (Apr 19): Lect 17 is complete. (Apr 18): Lect 16 is complete. (Apr 6): Lect 15 is complete. (Apr 5): Lect 14 is complete. (Mar 29): Lect 13 is complete. (Mar 24): Revised Sec 11.2, 11.4.1. (Mar 18): Revised Sec 10.3. (Mar 17): Lect 12 is complete. (Mar 16): Lect 11 is complete. (Mar 10): Revised Sec 9.2. (Mar 9): Lect 10 is complete. (Mar 2): Lect 9 is complete. (Feb 25): Lect 8 is complete. (Feb 25): Lect 1 (computation models) is expanded. (Feb 15): Lect 7 is complete. (Feb 13): Lect 6 is complete. (Jan 20): Lect 5 is complete. (Jan 19): Added Sec 5.1, 5.2. (Jan 18): Lect 4 is complete. (Jan 11): Added Sec 4.1, 4.2. (Jan 11): Lect 3 is complete. (Jan 7): Lect 2 is now complete. (Jan 6): Added Sec 2.2.1, 2.2.2. (Jan 6): Added Sec 2.1. (Jan 5): Added Lect 1. Lecture Schedule Lect 1 (week 1): Overview and computation models Lect 2 (week 1-2): BST and 2-3 tree. Remark: For a coverage of BSTs, see this and that. For a coverage of 2-3 trees, see this. Lect 3 (week 2-3): [Intervals] Interval tree and segment tree Lect 4 (week 3): [Points] kd-tree, bootstrapping, priority search tree, and range tree Lect 5 (week 3-4): [Dynamization/amortization] Logarithmic rebuilding and global rebuilding Video on global rebuilding Lect 6 (week 4): [Dynamization/amortization] Weight balancing Video Lect 7 (week 5): [Temporal/amortization] Partial persistence Video on potential Video on persistence Lect 8 (week 6): [Randomization/expectation] Dynamic perfect hashing Video on random graphs Video on cuckoo hashing (error in video: at 51:38, "4e^3/n" should be "4e^3/n^2") Lect 9 (week 7): [Graphs] Binomial and Fibonacci heaps Video on binomial heaps Video on Fibonacci heaps (error in video: at 11:52, the tree is not an order-2 relaxed binomial tree -- it would be if the right child of the root had only 2 children, as opposed to 7) (error at 13:15: same issue) Lect 10 (week 8): [Graphs] Union-find structure Video on structure, algorithms, and O(log*(n)) bound Video on O(α(n)) bound Lect 11 (week 9): [Graphs] Euler-tour structure Video on the "plain" ETS (error at 17:48 (corrected at 1:03:22): node G should be a child of node A) (error at 14:45: in the 2-3 tree, the last two leaf nodes should contain "CHC" and "AGA", resp.) (note about 54:54: ignore the line "CABACDCECFCHCGC") Video on the "augmented" ETS Lect 12 (week 9-10): [Graphs] Dynamic connectivity Video on edge leveling Video on the algorithms Lect 13 (week 10): [Tabulation] Range min queries Video Lect 14 (week 11): [Predecessor] van Emde Boas Structure Video Remark: see this for the substitution method Lect 15 (week 11): [Word length = Ω(log n)] 2D orthogonal range counting Video Lect 16 (week 12): [Nearest neighbor search] Doubling dimension Video Lect 17 (week 13): [Nearest neighbor search] Locality sensitive hashing Video Lect 18 (week 13): [Strings] The suffix tree Video There will be no more lectures. |
| Exercises |
|
As mentioned earlier, some problems in the midterm and final exams will be taken directly from the 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 exams, you will be allowed to consult only one piece of single-sided A4-sized paper. In other words, it is unrealisic to hope that you can write down all the solutions on that paper. List 1: Prob 1-4 in the exercise section of Lect 2 (see the lect notes). List 2: Prob 1-4 (in the exercises) of Lect 3, and Prob 1-4 of Lect 4. List 3: Prob 7, 9, 10, 12 of Lect 4. List 4: Prob 1-4 of Lect 5, and Prob 1-5 of Lect 6. List 5: Prob 1-5 of Lect 7. List 6: Prob 1-6 of Lect 8. List 7: Prob 3-9 of Lect 9. List 8: Prob 1-4, 6, 7 of Lect 10. List 9: Prob 4-8 of Lect 11. List 10: Prob 4-6 of Lect 12, Prob 1-6, 9, 10 of Lect 13. List 11: Prob 1-4 of Lect 14, Prob 1-4 of Lect 15. List 12: Prob 1-6 of Lect 16. List 13: Prob 1-5 of Lect 17, and Prob 1-5 of Lect 18. There will be no more exercise lists. |
| Assignments, Quizzes and Exams |
|
Assignment 1 (replacing Quiz 1): Prob 4 of Lect 3, and Probs 10, 11 of Lect 4 Each student should email the instructor the solutions in a pdf typeset in Latex or Word by 11:59pm, Feb 27. No late submissions will be accepted. Midterm exam: Prob 6 of Lect 7 (40%), Prob 1 of Lect 8 (30%), and Prob 5 of Lect 9 (30%)
|
|
|