CSCI2100/ESTR2102 Data Structures

Offered by Yufei TAO, Fall 2018.

Tutors: Shangqi LU (sqlu@cse) and Jianwen ZHAO (jwzhao@cse).

Quick navigation links:
[Lecture Notes][Tutorials][Regular Exercises][Special Exercises][Notes for ESTR2102][Quizzes 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 15 (3 Dec): Stats of Quiz 3 released.

News 14 (28 Nov): Scope of the Final Exam: (i) for CSCI2100, Lec Notes 1-22; (ii) for ESTR2102, Lec Notes 1-22 plus Elite Lec Notes 1-6, 8-9, 11-12.

News 13 (14 Nov): Quiz 3 will take place in the lecture of 27 Nov. It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lecture Notes 14-17. You are free to bring in the notes and textbook.

New 12 (13 Nov): Project released. See the bottom of the page.

New 11 (8 Nov): Stats of Quiz 2 released.

News 10 (1 Nov): The final exam will be from 12:30pm to 2:30pm, on 19 Dec. For the venue, pay attention to the university's announcements.

News 9 (13 Oct): Quiz 2 will take place in the lecture of 30 Oct. It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lecture Notes 6-13 (Notes 11-13 will be taught in the next two weeks). You are free to bring in the notes and textbook.

News 8 (13 Oct): Midterm will take place in the lecture of 22 Oct. It will start at 9:30am and will be 45 minutes long. The scope covers everything in Lecture Notes 1-10. You are free to bring in the notes and textbook.

For CSCI2100: 35% of the questions will come from Special Ex Lists 1-5.

News 7 (10 Oct): Stats of Quiz 1 released -- see the bottom of the page.

News 6 (9 Oct): Regular and special exercise lists 4 and 5 released. There will be no more annoucements about exercise releases. Check the webpage after the lectures each week for this purpose.

News 5 (24 Sep): Quiz 1 will take place in the lecture of 2 Oct. It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lecture Notes 1-5. You are free to bring in the notes and textbook.

News 4 (24 Sep): Regular and special exercise list 3 released.

News 3 (12 Sep): Released regular exercise lists 1 and 2, and special exercise lists 1 and 2.

News 2 (3 Sep): There will be no tutorials in the first week.

News 1 (2 Sep): Hello, all.

Time and Venues

Lectures
Mon 9:30am - 10:15am Institute of Chinese Studies L1
Tue 12:30pm - 2:15pm Institute of Chinese Studies L1

Tutorials
Session 1 Wed 4:30pm - 5:15pm William M W Mong Eng Bldg 803
Session 2 Thu 12:30pm - 1:15pm William M W Mong Eng Bldg 803

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: 20%
Coding project: 15%
Final Exam: 50%

Style of Exams for CSCI2100:
During this course, the instructor will gradually generate a list of special exercises without the 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 final exam, you will be allowed to bring in a single-sided, A4-sized, note-sheet on which you can print/write anything you deem useful. The midterm will be open book.

Style of Exams for ESTR2102:
All problems may be new.

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 (uploaded at 9:30pm, 3 Sep)

 --
2
Binary Search and Worst-Case Analysis (uploaded at 5pm, 9 Sep)

--
3
Asymptotic Analysis: The Growth of Functions (uploaded at 5pm, 9 Sep)

Sections 3.1 and 3.2
4
Recursion: The Beginning (uploaded at 5pm, 9 Sep)

Chapter 1, and Sections 2.1, 2.2
5
Merge Sort (uploaded at 3pm, 16 Sep)

Section 2.3
6
Two Methods for Solving Recurrences (uploaded at 8pm, 23 Sep)

Sections 4.3 and 4.5
7
RAM Model with Randomization (uploaded at 11pm, 1 Oct)

--
8
k-Selection (uploaded at 11:30pm, 1 Oct)

Section 9.2 (the textbook's algorithm requires a more tedious analysis, as is also discussed in a regular exercise).
9
Quick Sort (uploaded at 11pm, 7 Oct)

Sections 7.1-7.4
10
Sorting Lower Bound and Counting Sort (uploaded at 11pm, 7 Oct)

Sections 8.1-8.2
11
Linked Lists, Stacks, and Queues (uploaded at 6pm, 13 Oct)

Sections 10.1-10.2
12
Dynamic Arrays and Amortized Analysis (uploaded at 11am, 5 Nov)
Changes: typo corrections in the last slide.

Old version (uploaded at 6pm, 13 Oct)

Section 17.4 (you may as well just ignore this section if you find the analysis in the textbook difficult to understand. The analysis in the slides is much simpler).
13
Hashing (uploaded at 11pm, 23 Oct)
Changes: Slide 18.

Old version (uploaded at 9am, 23 Oct)

Sections 11.1-11.3
14
Basic Definitions and Properties of Trees (uploaded at 6:30pm, 28 Oct)

--
15
Priority Queues (Binary Heaps) (uploaded at 6:30pm, 28 Oct)

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) (uploaded at 9pm, 29 Oct)

Sections 12.1-12.2.
17
Binary Search Trees (Dynamic Version) (uploaded at 9pm, 29 Oct)

--
18
Basic Concepts and Representation Methods of Graphs (uploaded at 10am, 13 Nov)

Section 22.1
19
Breadth First Search (uploaded at 10am, 13 Nov)

Section 22.2
20
Depth First Search (uploaded at 10pm, 18 Nov)

Section 22.3
21
Topological Sort (uploaded at 9am, 19 Nov)

Section 22.4
22
Single Source Shortest Paths with Positive Weights (uploaded at 11pm, 25 Nov)

Sections 24.2 and 24.3
23 (Bonus)
Finding Minimum Spanning Trees (uploaded at 11am, 27 Nov)

Chapter 23 (you may leave out Kruskal's algorithm)

Tutorial Material


Week 2
Slides 1: Cost of your programs (uploaded at 9pm, 11 Sep)
Slides 2: More on binary search (uploaded at 9pm, 11 Sep)

Week 3
Slides 1: More on big-O (uploaded at 11pm, 17 Sep)
Slides 2: Examples of proving big-O (uploaded at 11pm, 17 Sep)

Week 4
Slides 1: Memory allocation of merge sort (uploaded at 8:30pm, 25 Sep)
Slides 2: More on merge sort and binary search (uploaded at 8:30pm, 25 Sep)

Week 5
Random permutation (uploaded at 5pm, 2 Oct)
Week 6
Slides 1: Quick sort implementation details (uploaded at 3pm, 9 Oct)
Slides 2: More on k-selection (uploaded at 3pm, 9 Oct)
Week 7
More on sorting (updated at 4pm, 30 Oct)
Corrected typos in Slide 10.

Week 8
More on dynamic arrays (uploaded at 9:30am, 23 Oct)
Week 9
More on hashing (uploaded at 9:30am, 23 Oct)
Week 10
More on binary heaps (uploaded at 7pm, 5 Nov)
Week 11
More on BSTs (uploaded at 5pm, 12 Nov)
Week 12
More on dynamic BSTs (uploaded at 7pm, 19 Nov)
Week 13
More on DFS (uploaded at 5:30pm, 26 Nov)

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
(uploaded at 10:30am, 12 Sep)

--
2
More on Recursion
Tower of Honoi and GCD algorithms
(uploaded at 6:30pm, 16 Sep)

 Section 31.2
3
k-Selection (Deterministic)
(uploaded at 9:30pm, 25 Sep)

 Section 9.3
4
Random Binary Search
(uploaded at 6:30pm, 2 Oct)

 --
5
Part 1: Expected cost of quick sort (slides in Lec Notes 9).
Part 2: The Birthday Paradox
(uploaded at 8:30pm, 9 Oct)

 Section 5.4.1
6
Linear Time Sorting in Polynomial Domains
(uploaded at 1pm, 17 Oct)

 Section 8.3
7
Proof of Universality (slides in Lec Notes 13)

 Section 11.3
8
Perfect Hashing
(uploaded at 10am, 31 Oct).

 Section 11.5
9
The Skip List
(uploaded at 9:30am, 7 Nov).

 --
10
The van Emde Boas Structure
(uploaded at 10am, 14 Nov).

 Chapter 20 (the textbook's description proves only a weaker version of the results in the lecture notes)
11
The kd-tree
(uploaded at 6:15pm, 21 Nov).

 --
12
Making the kd-tree Dynamic
(uploaded at 2:30pm, 28 Nov).

 --

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).
There will be no more regular exercises.

Additional Exercises If a Textbook Is Owned
[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 midterm and final exams 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 (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. You will need to comprehend the solutions to make sure you can answer them correctly in the exams. 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.
There will be no more special exercises.

Quizzes and Exams

Quiz 1 Stats:
CSCI2100: max = 100, average = 72.1, standard deviation = 22.5. Top 20 scores (class size = 78)
ESTR2102: max = 100, average = 92, standard deviation = 4.1 (class size = 7).

Midterm Stats:
CSCI2100: max = 100, average = 60.9, standard deviation = 23.2. Top 20 scores
ESTR2102 (different paper): max = 99, average = 66.7, standard Deviation = 24.2.

Quiz 2 Stats:
CSCI2100: max = 100, average = 74.9, standard deviation = 22.2. Top 20 scores
ESTR2102: max = 100, average = 73.9, standard deviation = 24.2.

Quiz 3 Stats:
CSCI2100: max = 100, average = 70.6, standard deviation = 26.7. Top 20 scores
ESTR2102: max = 100, average = 79.7, standard deviation = 27.6.

Project

Description (released at 7pm, 13 Nov).

Deadline: 11:59pm, 16 Dec, 2018.
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 the NotePad that comes with Windows.

An assessment item has been created in the Blackboard system. Please follow the instructions there to submit your project.