CSCI 5020 External Memory Data Structures Offered by Yufei Tao, Fall 2014. TA: Xiaocheng Hu.

Brief description

In this course, we will study worst-case efficient algorithms for solving a set of fundamental problems of computer science in the external memory model. In this model, the space complexity is measured in the number of disk blocks occupied, while the time complexity is measured in the number of I/Os performed (each transferring a block of data between the memory and the disk). Techniques that are crucial for designing and analyzing I/O-efficient data structures will be discussed in detail.

Announcements

News 23 (3 Dec): The venue of the FINAL EXAM will be ERB 408. Each student is allowed to bring in and consult a one-sided A4-sized "cheat sheet" (which can contain any materials deemed useful by the student). News 22 (30 Nov): The FINAL EXAM will be held from 7:30pm to 9:30pm on 17 Dec. The venue will be announced later. News 21 (30 Nov): Exercise List 5 released. News 20 (25 Nov): A make-up lecture will be given during 3:30pm-5:15pm on 26 Nov (Wed). The classroom is ERB408. News 19 (25 Nov): A 1-hour make-up lecture arranged today. News 18 (13 Nov): Assignment 2 released. News 17 (12 Nov): Exercise List 4 released. News 16 (12 Nov): No lecture on Nov 17 and 18. Make-up lectures will be arranged later. News 15 (11 Nov): A 1-hour make-up lecture arranged today. News 14 (4 Nov): A 1-hour make-up lecture arranged today. News 13 (29 Oct): Exercise List 3 released. News 12 (29 Oct): A 1-hour make-up lecture arranged today. News 11 (14 Oct): Assignment 1 released. News 10 (14 Oct): No lecture on Oct 20 and 21. The instructor will be on conference leave. Make-up lectures will be arranged later. News 9 (14 Oct): A 1-hour make-up lecture arranged today. News 8 (12 Oct): Exercise List 2 released. News 7 (6 Oct): A 1-hour make-up lecture arranged today. News 6 (30 Sep): A 1-hour make-up lecture arranged today. News 5 (29 Sep): Exercise List 1 released. News 4 (23 Sep): A 1-hour make-up lecture arranged today. News 3 (16 Sep): The lecture today is canceled due to typhoon. A make-up lecture will be arranged later. News 2 (4 Sep): The lecture of next Mon (Sep 8) is canceled. A make-up lecture will be arranged later. News 1 (1 Sep): Hello, all.

Time and venues

Mon 9:30am - 11:15am YC Liang Hall 101 Tue 11:30am - 12:15pm Lee Shau Kee Bldg 306

Grading scheme

Assignments: 50% Final: 50% (see below) Style of the final exam: During this course, the instructor will gradually generate a list of exercises without the solutions given. In the final exam, 60% of the marks will come from problems taken directly from that list. The rest 40%, however, will be from new problems.

Lecture notes

The instructor will make the lecture notes available before each lecture. Keep in mind, however, that these notes are supplementary. Lecture attendance is vital to grasp the materials taught. Notes Lecture 1 Computation Model and Sorting (uploaded at 3am, 1 Sep) Lecture 2 Permutation and Indivisibility (uploaded at 6:15pm, 14 Sep) Lecture 3 Comparison-Based Lower Bounds (updated at 4:10pm, 30 Sep) Lecture 4 Distribution Sweeping (uploaded at 12:20am, 6 Oct) Lecture 5 Weight-Balanced B-Tree (updated at 2:50pm, 14 Oct) Lecture 6 Partially Persistent B-Tree (updated at 1:40am, 29 Oct) Lecture 7 External Interval Tree (uploaded at 6:30pm, 2 Nov) Lecture 8 External Priority Search Tree (uploaded at 1:20am, 10 Nov) Lecture 9 External Range Tree (uploaded at 5:40pm, 23 Nov) Lecture 10 Linear Space Range Searching (updated at 7:10pm, 25 Nov) Lecture 11 Range Counting (uploaded at 5:40pm, 23 Nov)

Exercises

As mentioned earlier, some final exam problems will be taken directly from the exercise lists below. No solution to any exercise will be given. You, however, are very welcome to present your solutions to the instructor, who will tell you whether the solutions are correct (if a solution is incorrect, the instructor will explain why). List 1 List 2 List 3 List 4 List 5 The following document contains hints to the exercises. You may want to think twice before opening it as it may take away the fun of finding your own way out. The document will grow with time. Spoilers

Assignment

Assignment 1: Download the description here. Due day Oct 29, 2014 (submit a pdf to the TA at xchu@cse.cuhk.edu.hk). You are welcome to discuss with your friends, the TA, and the instructor himself. But your solutions must be described in your own words. If you believe you need some hints, click here. Assignment 2: Download the description here. Due day Nov 27, 2014 (submit a pdf to the TA at xchu@cse.cuhk.edu.hk). You are welcome to discuss with your friends, the TA, and the instructor himself. But your solutions must be described in your own words. If you believe you need some hints, click here.