COMP3506/7505 Algorithms and Data Structures

Offered by Yufei Tao, Semester 2, 2016.

Tutors: Junhao Gan (j.gan@uq.edu.au), Tony Gong (tony.gong@uq.net.au), Dan He (Doris, d.he@uq.edu.au), Benjamin Martin (ben.martin@uq.edu.au).

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 introduction to greedy algorithms and dynamic programming.
Announcements

News 1 (23 Jul): Hello, all.
News 2 (27 Jul): Please be reminded that tutorials will start in Week 2 (as stated in the course profile).
News 3 (28 Jul): Special exercise list 1 has been released! Scroll down the page to see them.
News 4 (6 Aug): Special exercise list 2 is released.
News 5 (7 Aug): The instructor has released two sets of "regular exercises" -- regular in the sense that their solutions will be released in full. Scroll down the page to have fun with these exercises, and thereby, test the knowledge of yourself on the course contents.
News 6 (8 Aug): This Wed (10 Aug) is a public holiday, on which there will be no lectures and tutorials. Students in (tutorial) Sessions 1-5 can either (i) go to any other sessions, or (ii) make appointments with the tutors or the instructor himself for special tutoring. The email addresses of the tutors and the instructor can be found at the top of the page.
News 7 (9 Aug): The instructor will attend tutorial Session 6 on Aug 11.
News 8 (9 Aug): A forum has been set up in blackboard for discussing the course materials. However, the instructor prefers all questions be sent to him by email (he is old school).
News 9 (15 Aug): Special exercise list 3 is released.
News 10 (15 Aug): Regular exercise list 3 is released.
News 11 (15 Aug): The first class for the "training camp" will be held from 6:15pm to 7:15pm, in Room 631 (DKE Multimedia Lab) of Building 78.
News 12 (16 Aug): The instructor will attend tutorial Session 3 this week.
News 13 (17 Aug): A new section is added for the training camp. Scroll to the bottom to find it.
News 14 (22 Aug): Quiz 1 solutions released.
News 15 (22 Aug): Special exercise list 4 released.
News 16 (22 Aug): Your Quiz 1 papers are ready for collection. Please make appointments with Tutor Junhao Gan (j.gan@uq.edu.au) for this purpose.
News 17 (22 Aug): Regular exercise list 4 released. Also, the instructor will go to tutorial Sessions 3 and 7.
News 18 (23 Aug): This week the "training camp" will still be held from 6:15pm to 7:15pm, in Room 631 (DKE Multimedia Lab) of Building 78. These will be the default time and venue unless otherwise announced.
News 19 (23 Aug): Statistics of Quiz 1 released. Scroll to the Quiz section to see it.
News 20 (24 Aug): Quiz 1 scores can now be found in Blackboard.
News 21 (26 Aug): Special/regular exercise list 5 released. The instructor will go to tutorial Session 5.
News 22 (31 Aug): Starting from this week, the training camp lecture will start at 6:05pm, namely, this will be the new default time from now on.
News 23 (31 Aug): The scope of the mid-semester exam covers everything in Lecture Notes 1-10.
News 24 (31 Aug): Special/regular exercise list 6 released.
News 25 (6 Sep): We still have one quiz paper that does not have a name. If you think it could be yours, please make an appointment with the instructor for identification.
News 26 (7 Sep): The instructor will go to tutorial Session 5.
News 27 (8 Sep): Special/regular exercise list 7 released.
News 28 (18 Sep): Special/regular exercise list 8 released.
News 29 (18 Sep): Mid-Semester exam solutions released.
News 30 (20 Sep): Your mid-semester exam papers are ready for collection. Please make appointments with Tutor Junhao Gan (j.gan@uq.edu.au) for this purpose.
News 31 (20 Sep): No training camp this week. Sorry about this -- the instructor must get himself ready for a conference trip with a departing flight at 7am on Thu morning. Please accept his apology.
News 32 (30 Sep): Special/regular exercise list 9 released.
News 33 (4 Oct): The scope of Quiz 2 overs everything in Lecture Notes 11-15.
News 35 (5 Oct): The training camp resumes tonight! The instructor will give a double-lengthed talk.
News 36 (8 Oct): All the lecture notes have now been uploaded! Notes 24 and 25 will not be examined.
News 37 (8 Oct): Special/regular exercise list 10 released.
News 38 (16 Oct): Special/regular exercise list 10 released.
News 39 (16 Oct): Quiz 2 solutions released.
News 40 (16 Oct): Your Quiz 2 papers are ready for collection. Please make appointments with Tutor Junhao Gan (j.gan@uq.edu.au) for this purpose.
News 41 (25 Oct): Special/regular exercise list 12 released.
News 42 (4 Nov): Structure of the final exam: Part I: 10 multiple-choice questions (3 marks each); Part II: (i) 7 questions from special exercises (5 marks each), and (ii) 3 new questions: 10, 13, 12 marks, respectively.
News 43 (16 Nov): Statistics of the final exam have been released.

Time and Venues

Lectures
Tue 4pm - 5:50pm Room 206, Building 3
Wed 5pm - 5:50pm Room 348, Building 63

Tutorials
Session 1 Wed 8am - 8:50am Room 142, Building 67
Session 2 Wed 9am - 9:50am Room 142, Building 67
Session 3 Wed 11am - 11:50am Room 141, Building 67
Session 4 Wed 12pm - 12:50pm Room 215, Building 32
Session 5 Wed 4pm - 4:50pm Room 343, Building 67
Session 6 Thu 8am - 8:50am Room 342, Building 67
Session 7 Fri 12pm - 12:50pm Room 212, Building 35
Session 8 Fri 1pm - 1:50pm Room 212, Building 35
Session 9 Fri 2pm - 2:50pm Room 115, Building 14
Session 10 Fri 3pm - 3:50pm Room 115, Building 14
Click here for a map of the St Lucia campus.

Grading Scheme

In-Class Quiz 1: 12.5% (4pm-4:25pm, Aug 16, covering Weeks 1-3)
Mid-Semester Exam: 25% (5pm-5:50pm, Sep 14, covering Weeks 1-7)
In-Class Quiz 2: 12.5% (4pm-4:25pm, Oct 11, covering Weeks 8-10)
Final Exam: 50% (Exam period, covering the whole semester)

Style of the Exams:
During this course, the instructor will gradually generate a list of special exercises without the solutions given. In the mid-semester 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.

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 materials taught.

Lecture Notes Textbook Reading (If a Book is Owned)
1
The RAM Model (uploaded at 11:30pm, 25 July)
2
Binary Search and Worst-Case Analysis (uploaded at 6pm, 15 Aug)
Changes: Slide 16---simplified the pseudocode and corrected a typo.

Old Version 2 (uploaded at 1pm, 1 Aug)
Changes: Slide 16---modified Line 3, and added Line 16 in the pseudocode.

Old Version (uploaded at 1:30pm, 26 July)

3
Asymptotic Analysis: The Growth of Functions (uploaded at 11:55pm, 1 Aug)

Chapter 3.1 (best if you can read also Chapter 3.2)
4
Recursion: The Beginning (uploaded at 8pm, 8 Aug)
Changes: The name "bubble sort" should be "selection sort".

Old Version (uploaded at 3am, 2 Aug)

Chapters 1, 2.1, and 2.2 (you were not ready to touch the two chapters before)
5
Merge Sort (uploaded at 8pm, 8 Aug)

Chapter 2.3
6
Quick Sort (uploaded at 10pm, 16 Aug)

Chapters 7.1-7.3 (best if you can read Chapter 7.4 as well)
7
Comparison-Based Lower Bound + Counting Sort (uploaded at 1am, 23 Aug)

Chapters 8.1-8.2
8
Linked Lists, Stacks, and Queues (uploaded at 2pm, 27 Aug)
Changes: Fixed a typo on Slide 20 -- the word 'tail' in "return the elmented stored in the tail" should be 'head'.

Old Version (uploaded at 2pm, 23 Aug)

Chapters 10.1-10.2
9
Dynamic Arrays and Amortized Analysis (uploaded at 1am, 30 Aug)

Chapter 17.4 (you may as well just ignore this chapter if you find the analysis in the textbook difficult to understand. The analysis in the slides is much simpler.)
10
Hashing (uploaded at 11:30pm, 4 Sep)
Changes: Revised Slide 17 and added Slide 18.

Old Version (uploaded at 3pm, 30 Aug)

Chapters 11.1-11.3 (you may leave out the proof of Theorem 11.5 if you want.)
11
Trees: Basic Concepts and Properties (uploaded at 11:50am, 6 Sep)

--
12
Priority Queues (Binary Heaps) (uploaded at 1am, 8 Sep)
Changes: Fixed typos in Slide 8.

Old Version (uploaded at 11:50am, 6 Sep)

You may read Chapter 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).
13
Binary Heaps in Dynamic Arrays (uploaded at 1am, 8 Sep)
Changes: Fixed typos in Slide 9.

Old Version (uploaded at 1:50am, 7 Sep)

Chapters 6.1-6.4.
14
Binary Search Tree (Static Version) (uploaded at 3:40am, 13 Sep)

Chapters 12.1-12.2.
15
Binary Search Tree (Dynamic Version -- AVL-Tree) (uploaded at 8:40pm, 10 Oct)
Changes: Corrected the pseudocode on Slide 13.

Old Version 2 (uploaded at 4:40pm, 2 Oct)
Changes: Corrected an error in the example on Slide 24.

Old Version (uploaded at 3:40am, 13 Sep)

--
16
(2,3)-Tree (uploaded at 11pm, 19 Sep)

--
17
Graphs: Basic Concepts (uploaded at 6pm, 4 Oct)
Changes: Correct typos on Slides 7 and 9.

Old Version (uploaded at 4am, 4 Oct)

Chapter 22.1
18
Breadth First Search (uploaded at 4am, 4 Oct)

Chapter 22.2
19
Depth First Search (uploaded at 4am, 4 Oct)

Chapter 22.3
20
Topological Sort (uploaded at 4am, 4 Oct)

Chapter 22.4
21
Finding Strongly Connected Components (uploaded at 4am, 4 Oct)

Chapter 22.5
22
Single Source Shortest Paths (uploaded at 2am, 6 Oct)

Chapters 24.2 and 24.3
23
Finding Minimum Spanning Trees (uploaded at 1am, 7 Oct)

Chapter 23 (you may leave out Kruskal's algorithm)
24*
Introduction to Greedy: Huffman Codes (uploaded at 3:30am, 8 Oct)

Chapter 16.3
25*
Introduction to Dynamic Programming: Edit Distances (uploaded at 3:30am, 8 Oct)

Chapter 15.4 (the chapter discusses a different problem called "longest common subsequence", which is less intuitive than the edit distance problem in the instructor's opinion; however, essentially the same algorithm solves both problems)
Lecture notes 24 and 25 will not be examined.

Tutorial Materials


Week 2
Fusion of Theory and Practice: Cost of Your Programs (uploaded at 11:55pm, 27 July)

Extra Tutorial Slides (Prepared by Tony Gong) (uploaded at 3am, 2 Aug)

Week 3
A Graphical View of Big-O (uploaded at 11:55pm, 7 Aug)

Extra Tutorial Slides (by Junhao Gan) (uploaded at 3am, 2 Aug)

Week 4
More on Recurrences (and the Master Theorem) (uploaded at 7:40pm, 15 Aug)
Week 5
Fusion of Theory and Practice: Memory Management of Merge Sort (uploaded at 1am, 22 Aug)

Extra Tutorial Slides (by Junhao Gan) (uploaded at 10:45pm, 23 Aug)
Week 6
Fusion of Theory and Practice: Implementation of the Linked List (uploaded at 1am, 29 Aug)

Extra Tutorial Slides (by Tony Gong) (uploaded at 1am, 29 Aug)
Week 7
Tutorial Slides (by Dan He) (uploaded at 2pm, 6 Sep)
Week 8
Fusion of Theory and Practice: Implementation of the Binary Heap (uploaded at 12:30am, 12 Sep)

Extra Tutorial Slides (by Tony Gong) (uploaded at 12:30am, 12 Sep)
Week 9
Tutorial Slides (by Junhao Gan) (uploaded at 9pm, 18 Sep)
Week 10
Fusion of Theory and Practice: Implementation of the AVL-Tree (by Tony Gong) (uploaded at 1am, 5 Oct)

Tutorial Slides (by Tony Gong) (uploaded at 2am, 5 Oct)
Week 11
Tutorial Slides (by Dan He) (uploaded at 5pm, 9 Oct)
Week 12
Tutorial Slides (by Tony Gong) (uploaded at 1:30am, 17 Oct)

Maze Fun: Use DFS to solve mazes (by Benjamin Martin) (uploaded at 10:45pm, 17 Oct)

Week 13
Tutorial Slides (by Dan He and Junhao Gan) (uploaded at 3:50am, 24 Oct)

Regular Exercises

The instructor has prepared the following exercises which he believes are useful for students to consolidate their understanding of the course materials. Unlike the "special" exercises (as will be explained in the next section of this page), solutions to these "regular" exercises are provided in full.

Exercises carrying a "*" may be difficult.

List 1 (uploaded at 2:30am, 7 Aug). Solutions (uploaded at 6pm, 8 Aug).
List 2 (updated at 9:30pm, 8 Aug). Solutions (updated at 9:30pm, 13 Aug).
List 3 (uploaded at 5:30pm, 15 Aug). Solutions (uploaded at 10:30pm, 17 Aug).
List 4 (uploaded at 11pm, 22 Aug). Solutions (uploaded at 11pm, 22 Aug).
List 5 (uploaded at 1:20am, 26 Aug). Solutions (uploaded at 1:30pm, 27 Aug).
List 6 (uploaded at 11:50pm, 31 Aug). Solutions (uploaded at 3am, 1 Sep).
List 7 (updated at 1:30am, 9 Sep). Solutions (uploaded at 1:30am, 9 Sep).
List 8 (uploaded at 11pm, 18 Sep). Solutions (uploaded at 11pm, 18 Sep).
List 9 (uploaded at 8pm, 30 Sep). Solutions (uploaded at 11am, 1 Oct).
List 10 (uploaded at 6:30pm, 8 Oct). Solutions (uploaded at 6:30pm, 8 Oct).
List 11 (uploaded at 1:40am, 16 Oct). Solutions (uploaded at 1:40am, 16 Oct).
List 12 (uploaded at 3:40am, 24 Oct). Solutions (uploaded at 3:40am, 24 Oct).
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.
[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.
[SCC] Exercises 22.5-1, 22.5-3, 22.5-5, 22.5-6.
[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 mid-semester exam and the final exam 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.

List 1 (uploaded at 2:30pm, 28 Jul)
List 2 (uploaded at 5:30pm, 6 Aug)
List 3 (updated at 4pm, 15 Aug)
List 4 (uploaded at 8:45pm, 22 Aug)
List 5 (updated at 3:15pm, 30 Aug)
List 6 (uploaded at 11:50pm, 31 Aug)
List 7 (uploaded at 1am, 8 Sep)
List 8 (uploaded at 6pm, 16 Sep)
List 9 (uploaded at 11am, 1 Oct)
List 10 (uploaded at 7pm, 8 Oct)
List 11 (uploaded at 2am, 16 Oct)
List 12 (uploaded at 1am, 25 Oct)
There will be no more special exercises.

Notes for the Training Camp

Starting from Week 4, the instructor will organize a one-hour "bonus" lecture every week to a group of students that wants to explore more advanced computer science than what is taught in the class. The group will be referred to as the "training camp". The materials covered in the camp will not be tested in quizzes and exams. Nonetheless, they are released below for any one, inside and outside the camp, to access.

Lecture Notes Textbook Reading (If a Book is Owned)
1
The k-Selection Problem (Randomized) (uploaded at 1:50pm, 17 Aug)

 Chapter 9.2 (remark: the textbook's algorithm requires a more complicated analysis than the one in the lecture notes)
2
The k-Selection Problem (Deterministic) (uploaded at 1:22pm, 24 Aug)

 Chapter 9.3
3
The Substitution Method (uploaded at 1:22pm, 24 Aug)

 Chapter 4.3
4
Running Time of Quicksort (uploaded at 11:30pm, 30 Aug)

 Chapter 7.4
5
Linear Time Sorting in a Polynomial Domain (uploaded at 10pm, 31 Aug)

 Chapter 8.3
6
Proof of Univerality in Hashing (uploaded at 3pm, 7 Sep)

 Chapter 11.3.3
7
Perfect Hashing (uploaded at 2:40am, 14 Sep)

 Chapter 11.5
8
Skip Lists (uploaded at 12:40am, 5 Oct)

 --
9
The van Emde Boas Structure (uploaded at 12:40am, 5 Oct)

 Chapter 20 (the textbook's description proves only a weaker version of the results in the lecture notes)
10
The kd-Tree (uploaded at 9pm, 11 Oct)

 --
11
Dynamic kd-Trees (uploaded at 9pm, 11 Oct)

 --
12
Tries, Patricia Tries, and Suffix Trees (uploaded at 1:20am, 26 Oct)

 --

Quizzes and Exams

Quiz 1 (Solutions).
COMP3506 Stats: Average = 67.87, Max = 100
COMP7505 Stats: Average = 72.09, Max = 100

Mid-Semester Exam (Solutions).
COMP3506 Stats: Average = 57.3, Max = 100, the top 25 scores
COMP7505 Stats: Average = 61.5, Max = 85, the top 5 scores

Quiz 2 (Solutions).
COMP3506 Stats: Average = 78.69, Max = 100
COMP7505 Stats: Average = 83.92, Max = 100

Final Exam
COMP3506 Stats: Average = 57.48, Max = 100, the top 25 scores
COMP7505 Stats: Average = 55.97, Max = 100, the top 5 scores