Index Show pagesource Old revisions Digg this! Del.Icio.Us Google bookmark

# CSCI2100 Data Structures

## Discussion forum

**Here** is the link to our discussion forum.

## Merits

Congratulations again to these students who did an incredibly excellent job on this year's programming midterm!

From left to right: YIU Man Chi (2nd Runner-up), HO Kwun Ting (Most Precise Coder), LI Danli (Excellent Female Coder), CHEN Yu Zhen (Best Female Coder), WONG Ka Wing (3rd Runner-up), Prof. King, SU Jinhai (1st Runner-up), LAU Chi Yung (Champion).

## Breaking News

1. 5 May 2016. Final exam papers are now ready to check, please come to Rm1024, SHB for checking before 20 May 2016.
2. 26 April 2016. Written assignment sample solutions are out, along with some other related problems in same topics. WA#4 solution WA#5 solution
3. 17 April 2016. EMERGENCY Due to the breakdown of SPARC workstations, we temporarily postpone the submission deadline of PA#5 for one day, i.e., to 23:59:59 April 18, 2016. You can try submissions tomorrow when the server is up, hopefully before noon.
4. 12 April 2016. IMPORTANT This is a kind remainder: there is no class today and no tutorial tomorrow.
5. 11 April 2016. The Online Judge System will be open for PA #5 12p.m. this afternoon. The reward vectors for Problem 1&2&3&4 are (3,3,3,2,1,1,0), (3,3,3,1,1,0,0), (3,3,3,2,1,1,0) and (3,3,3,1,1,0,0), respectively. If you have any trouble, please feel free to propose your problems on the forum. After submitting the code, you can check your scores at the ranking page.
6. 05 April 2016. Some students asked us which head files can be used in the programming midterm. You can all std header file and string.h.
7. 05 April 2016. IMPORTANT We have sent an email to all students who will attend the early session (1:30 pm - 5:00 pm, April 8) of programming midterm. If you already made a reservation and did not receive the email, please contact TAs and Prof. King as soon as possible. There are still 5 quotas left.
8. 05 April 2016. Due to conflict with programming midterm, PA#5's submission starting date has been postponed to Monday, April 11.
9. 05 April 2016. There is a mistake in the announcement! The tutorial for the programming midterm examination is not today, but will be tomorrow, Wednesday from 5:30 pm to 6:30 pm in ERB 407.
10. 01 April 2016. PA#5 was out. The scores of Programming Assignment are released. The link is. Please check whether there are mistakes of your scores. If so, please send email to TAs. We will check the log asap.
11. 31 March 2016. Last year's programming midterm exam paper can be found here. Sample code of several data structures and functions can be downloaded here.
12. 21 March 2016. Written assignment sample solutions are out. wa1sol.pdfwa2sol.pdfwa3sol.pdf
13. 17 March 2016. The Online Judge System will be open for PA #4 12a.m. tonight. The reward vectors for Problem 1&2&3&4 are (3,3,3,2,1,1,0), (2,2,2,1,1,0,0), (3,3,3,2,1,1,0) and (2,2,2,1,1,0,0), respectively. Remember to submit each problem twice to get partial scores. After submitting the code, you can check your scores at the ranking page.
14. 14 March 2016. Announcements
15. 14 March 2016. For Exercise 5.10 of Programming Assignment 4. There will be at most 100 words in the heap, i.e. the capacity of the heap is 100. We have updated the specification of Exercise 5.10 in the problem pool.
16. 14 March 2016. The due date of WA4 has been postponed to April 1st, Friday.
17. 14 March 2016. IMPORTANT According to the feedback from your Evaluation Questionnaire, some students want to get partial marks for passing some of test cases. So, for each problem, we split the test cases into two parts, an easy one and a difficult one. You should submit the code for one question twice, e.g. for problem 4.17, you should enter the command 'submit 1 417.c' and 'submit 2 417.c'.
18. 12 March 2016. Since there were some incidents about the PA last week. The scores of Programming Assignment are released. The link is. Please check whether there are mistakes of your scores. If so, please send emails to TAs. We will check the log asap.
19. 05 March 2016. EMERGENCY The online judge system is fixed. You can continue to submit. For those who did multiple (>1) submissions for the same problem during judge was down (email with “Problem ID doesn't exist”), please report to TAs by email with exact number of extra submissions and a screenshot of email for proof if your final score is affected. We will give 5 points back for each extra submissions you made if you finally pass the corresponding problem (100 maximum). We are truly sorry for any inconvenience caused.
20. 05 March 2016. EMERGENCY The online judge system is down from about 3:00 pm today. Please stop submitting until further notice. We will try to fix the issue as soon as possible. For those who already submitted, your submission will be judged later.
21. 03 March 2016. The Online Judge System will be open for PA #3 12a.m. tonight. The reward vectors for Problem 1&2&3 are (5,5,4,3,2,1,0), (5,5,4,3,2,1,0) and (3,2,1,0,0,0,0), respectively. If you have any trouble, please feel free to propose your problems on the forum. After submitting the code, you can check your scores at the ranking page.
22. 02 March 2016. Since some students are confuse about the buildHeap algorithm, I have updated P.23 to P.27 of the tutorial notes again.
23. 29 February 2016. For tutorial notes 7, I am sorry that I have made a mistake on P.27. I have fixed it and updated the tutorial notes. I have also upload the supplementary file for the proof of running time of buildHeap algorithm.
24. 29 February 2016. FAQ for written assignment 3. For exercise 5.2, you need to write down the result of performing three Delete_Min operations in the heap of problem 1 and problem 2 of the previous exercise.
25. 29 February 2016. We have updated the schedule of the written mid-term and programming mid-term. Please check. In the week of 22 March, we will be holding a Q&A session, and we will announce the details very soon.
26. 26 February 2016. PA#3 is out.
27. 22 February 2016. WA#3 is out. For WA#2, We do not receive submissions from the following students: 1155062731, 1155064367, 1155063091, 1155067968, 1155029046, 1155063232, 1155062004, 1155068081, and 1155049971. Two of them did not write their name on the paper. If you have submitted it, please contact TAs as soon as possible.
28. 18 February 2016. The Online Judge System will be open for PA #2 12a.m. tonight. The reward vectors for Problem 1&2&3 are (5,4,3,2,2,1,0), (5,4,3,2,2,1,0) and (3,2,1,0,0,0,0), respectively. For example, if your code files for problem 2.3 is “23.c”, for problem 2.16 is “216.c” and for problem 2.19 is “219.c” , then the submit commands are “submit 1 23.c”, “submit 2 216.c” and “submit 3 219.c”, respectively. After submitting the code, you can check your scores at the ranking page.
29. 15 February 2016. The lecture video playlist on Trees is available here. Please watch them this week since I plan to have a simple quiz on these topics next Monday, 22 February.
30. 15 February 2016. Since many students are confused about exercise 1.6 of written assignment 2, we are going to relax the requirements of this question. When you are asked to give the precise f(n) with n being the input, you can answer in either one of following ways.
1. Give the value of x after the termination of the algorithm, the initial value of x is 0.
2. Give the running time of the algorithm. Each assignment operation, arithmetic operation, and comparison operation cost 1 unit of time. Reminder: when calculating the running time of a “for” statement, you need to consider all the operations it performs.

We apologize that this question is not clearly written, even one of our TAs, Ken, got confused. This question actually intends to ask students to give the final value of x.

1. 5 February 2016. We do not receive written assignments of the following student: 1155068081. If you have submitted it, please contact TAs as soon as possible.
2. 5 February 2016. Programming assignment 2 is out. There are two compulsory problems and one extra problem (very difficult) for bonus.
3. 5 February 2016. Dear students, we will still have tutorials in the week after the Lunar New Year Break. Wish you Happy Chinese New Year.
4. 5 February 2016. Don't forget to check the “Receive updates” check-box in our discussion forum, so that you will receive an email digest once a day notifying you about new, unread activity from posts you are following. If you cannot find the check-box, you can refer to the screenshot here.
5. 2 February 2016. We will be running a discussion forum in the KEEP Open Edx to encourage peer learning. To participate in the discussion forum, you need to register a KEEP account so that we can add you to the Data Structure course in KEEP Open Edx. The following are the instructions.
3. Visit https://account.keep.edu.hk/account/profile, click “My Institution” and then associate your CUHK identity to the KEEP account.
4. Visit https://edx.keep.edu.hk/courses/course-v1:cuhk+csci2100a+2015_2/about, click the “Enrol” button, then you will be enrolled into the course.
5. Click “Discussion” to enter the discussion forum.
6. 1 February 2016. FAQ for written assignment 2. For problem 1.6 (1), (3), and (5), some students asked us what is meant by write down the f(n) and the big-O notation for each “expression”. It means that you need to write down the f(n) and the big-O notation for each “question”. For problem 1.8 (3), some students asked us what is the difference between “for-next loop set-up” and “each loop”. The difference is that, in “for-next loop set-up”, we need to initialise the variable i, while in “each loop”, we don't need to initialise i anymore.
7. 29 January 2016. Written assignment 2 is out. The deadline is 5:00 pm, Feb 19, 2016.
8. 29 January 2016. The Online Judge System is open for PA #1. After submitting the code, you can check your scores at the ranking page.
9. 26 January 2016. Corrections to WA #1 1.3(3): Since this problem seems a little bit difficult, we want to simplify it by defining a=2, b=1 and c=2. If you need more time to finish the homework, you can turn it in before 5:00 pm, Mon, Feb 1, 2016.
10. 26 January 2016. The assignment box for written assignment is located on the 10th floor of SHB. You can refer to the precise location here.
11. 25 January 2016. As for the score of Asg#0, some students submitted correct code and also received “Accepted” email but still had 0 mark on the ranking page. This is because the score system of assignment 0 has expired. But you can test the system by submitting Assign 0 throughout the whole semester. Asg#0 is only for you to test the judge system. The score of Asg#0 is not concluded in the final grade.
12. 22 January 2016. The first Programming Assignment has been released. You can submit the code to online judge system from 6:00 pm, Friday, Jan 29, 2016 to 6:00 pm, Friday, Feb 5, 2016. The reward vectors for Problem 1 & 2 are (4,3,3,2,2,1,0) and (4,3,3,2,2,1,0), respectively. For example, if your code files for problem 1.21 is “121.c” and for problem 1.22 is “122.c”, then the submit commands are “submit 1 121.c” and “submit 2 122.c”, respectively.
13. 20 January 2016. Video instructions for CSE UNIX server have been updated. You can get the links from our tutorial page.
14. 18 January 2016. Tutorial 2 has been modified in the tutorial page. Written Assignment 1 only contains 1.1 (4), (6), and (12); 1.3 (3) and (9); 1.4 (1), (3) and (5) of the problem pool. The whole problem pool is for your reference to exercise. Programming Assignment 1 will be released this Friday. Please make sure you are familiar with the CSE UNIX environment.
15. 11 January 2016. The website is now available!

## Spring 2015-2016 Term 2

 Lecture I Lecture II Tutorial I Tutorial II M5, 12:30 pm - 1:15 pm T5-6, 12:30 pm - 2:15 pm M7 2:30 pm - 3:15pm W10 5:30 pm - 6:15 pm LSK LT3 LSK LT3 LSK LT3 ERB 407

The Golden Rule of CSCI2100: No member of the CSCI2100 community shall take unfair advantage of any other member of the CSCI2100 community.

The Student/Faculty Expectations on Teaching and Learning document is available [here].

# Pre-requisite and Enrollment policy

Pre-requisite: CSCI1110 or 1120 or 1130 or 1510 or 1520 or 1530 or 1540 or ENGG1110 or ESTR1100 or ESTR1102 or ESTR1002 or its equivalent. For senior-year entrants, the prerequisite will be waived. Students are also expected to have basic knowledge in Linux command line.

If you have not used Linux command line interface before, you can consider the following online course from Udacity.

# Course Description

The concept of abstract data types and the advantages of data abstraction are introduced. Various commonly used abstract data types including vector, list, stack, queue, tree, and set and their implementations using different data structures (array, pointer based structures, linked list, 2-3 tree, B-tree, etc.) will be discussed. Sample applications such as searching, sorting, etc. will also be used to illustrate the use of data abstraction in computer programming. Analysis of the performance of searching and sorting algorithms. Application of data structure principles.

## Learning Objectives

1. To understand the concepts and operations of various data structures and their applications
2. To understand the concept of abstract data types
3. To have basic knowledge of algorithms and complexity of algorithms

## Learning Outcomes

1. To be able to implement the following data structures as abstract data types in a high level programming lanauge: stack, queue, hash table, list, binary search tree (including AVL tree, red black tree and splay tree), B-tree, trie, disjoint set, graph (including minimum spanning tree and shortest path).
2. To be able to use appropriate data structures in different applications.
3. To be able to implement abstract data types.
4. To be able to analyse the complexity of simple algorithms (such as searching and sorting).

## Learning Activities

1. Lectures
2. Tutorials
3. Web resources
4. Assignments
5. Examinations

# Personnel

 Lecturer Tutor 1 Tutor 2 Tutor 3 Tutor 4 Irwin King Jiani Zhang Ken Chan Tong Zhao Hongyi Zhang king AT cse.cuhk.edu.hk jnzhang AT cse.cuhk.edu.hk hpchan AT cse.cuhk.edu.hk tzhao AT cse.cuhk.edu.hk hyzhang AT cse.cuhk.edu.hk SHB 908 SHB 1024 SHB 1024 SHB1024 SHB 1024 3943 8398 * By appointment Friday 1:00 pm - 2:00 pm Tuesday 11:00 am - 12:00 pm Thursday 3:00 pm - 4:00 pm Thursday 3:00 pm - 4:00 pm

Note: This class will be taught in English. Homework assignments and examinations will be conducted in English.

# Syllabus

The pdf files are created in Acrobat XI. Please obtain the correct version of the Acrobat Reader from Adobe.

Week Date Lecture Topics
and Notes
Tutorial Topics Homework Assignments
and Events
Resources
1 11/1 Introduction

Introduction
KEEPAttendance
Introduction of C * WA #1 hw_1.19.pdf
Due on or before 5:00 pm, Mon, Feb 1, 2016
* 1.1 (4), (6), and (12); 1.3 (3) and (9); 1.4 (1), (3) and (5)
* Chapter 1 of Weiss'97
* Chapter 1 of Cormen et al.'90
2 18/1 Algorithm Analysis

Analysis (updated)
Online Judge System * PA #1 hw_1.21.pdf
From 6:00 pm, Friday, Jan 29, 2016 to 6:00 pm, Friday, Feb 5, 2016
* 1.21(Problem 1);1.22(Problem 2)
* Chapter 2 of Weiss'97
3 25/1 1. Algorithm Analysis
2. Lists, Stacks and Queues

LSQ
I\O issues * WA #2 hw_1.21.pdf
Due on or before 5:00 pm, Fri, Feb 19, 2016
* 1.6 (1), (3), and (5); 1.8 (3); 1.9 (2) and (4)
* Chapter 2 of Weiss'97
* Chapter 3 of Weiss'97
4 1/2 1. Lists, Stacks and Queues
2. Tree Data Structures and Algorithms

Trees
Lists, Stacks and Queues in C * PA #2 hw_1.22.pdf
From 12:00 am, Friday, Feb 19, 2016 to 23:59 pm, Thursday, Feb 25, 2016
* 2.3(Problem 1);2.16(Problem 2);2.19(Problem 3 Bonus)
* Chapter 3 of Weiss'97
5 8/2 Lunar New Year Break
6 15/2 Tree Data Structures and Algorithms

The lecture video playlist is available here.
Linux commands and vim * WA #3 hw_1.22.pdf
Due on or before 5:00 pm, Fri, March 04, 2016
* 3.3 (2) (3); 3.10; 3.11; 3.18; 5.1; 5.2; 5.4
* Chapter 4 of Weiss'97
7 22/2 1. Tree Data Structures and Algorithms
2. Heaps

Heaps
Binary and AVL Trees in C * PA #3 hw_1.23.pdf
From 12:00 am, Friday, March 4, 2016 to 23:59 pm, Thursday, March 10, 2016
* 3.24(Problem 1) ;3.32(Problem 2);3.36(Problem 3 Bonus)
* Chapter 4 of Weiss'97
8 29/2 1. Heaps
2. Hash Functions

Hashing
Heap in C * WA #4 hw_1.23.pdf
Due on or before 5:00 pm, Fri, April 1, 2016
* 4.1; 4.14; 6.1; 6.2; 6.6(2)
* Chapter 6 of Weiss'97
* Chapter 5 of Weiss'97
9 7/3 1. Hash Functions
2. Sorting Algorithm

Sorting
Hashing in C * PA #4 hw_1.24.pdf
From 12:00 am, Friday, Mar 18, 2016 to 23:59 pm, Thursday, Mar 24, 2016
* 4.17(Problem 1 easy testcases);4.17(Problem 2 tough testcases);5.10(Problem 3 easy testcases);5.10(Problem 4 tough testcases)
* Chapter 5 of Weiss'97
10 14/3 Sorting Algorithms

Announcements
Quicksort Demo
Pointers in C No assignment * Chapter 7 of Weiss'97
11 21/3 Open Forum

Written Midterm Exam
No Tutorials No assignment * Chapter 7 of Weiss'97
12 28/3 1. Easter Break

2. Sorting Algorithms
3. Graph Data Structures and Algorithms

Graphs
Announcements
Programming Exam Preview * PA #5 hw_1.24.pdf
From 12:00 am, Monday, Apr 11, 2016 to 23:59 pm, Sunday, Apr 17, 2016
* 1.19(Problem 1 easy testcases);1.19(Problem 2 tough testcases);6.11(Problem 3 easy testcases);6.11(Problem 4 tough testcases)
13 4/4 1. Ching Ming Festival

2. Graph Data Structures and Algorithms
3. Programming Midterm Exam
Programming Exam Preview * WA #5 hw_1.24.pdf
Due on or before 5:00 pm, Fri, April 22, 2016
* 7.1; 7.3; 7.4; 7.5 (1)
14 11/4 Discussions on Programming Midterm
No Tutorial Midterm Summary * Chapter 9 of Weiss'97
15 18/4 1. Graph Data Structures and Algorithms
2. Course Summary

Final
Mergesort and Quicksort in C * Chapter 9 of Weiss'97

Tutorial Page

• For detailed tutorial and lab session information, please go to Tutorial Page.

Manual Page

• For supplementary material on various topics related with this course, please go to Manual Page. Enjoy your Exploration.

# Examination Matters

## Examination Schedule

 Time Venue Notes March 22, 12:30 pm - 2:15 pm LSK LT5 One cheat sheet (A4, both sides) of notes. No calculator. April 8, 6:00 pm - 9:00 pm SHB924 Printed out materials only. April 28, 9:30 am - 11:30 an Multi-purpose Hall, Pommerenke Stud Ctr One cheat sheet (A4, both sides) of notes. No calculator.

## Programming Midterm Matters

1. The programming midterm is an open-book and open-notes examination. You may bring what you can carry on printed (hard copy) materials. You MUST not take anything that can record program code electronically to the examination venue. You will not need a calculator for any calculation.
2. The operation system will be Ubuntu. And the computer configuration will have these basic editors:
1. vi/vim
2. emacs
3. gedit
4. nano
3. You can use all the functions provided by standard C library as long as you include the header file.
4. This system includes GDB for debugging. You need to work on Terminal in order to use it.
5. If you would like to have other editors, you MUST send an email to the instructor and TAs no later than 2 weeks before the examination date and it will be subject to approval to be included on the computer system.
6. You should arrive to the venue 30 minutes before the starting time on the day of the examination to receive your account information and check the system.
7. The examination will begin when the Chief TA starts the clock and will end when the Chief TA stops the clock, which is usually three hours after the starting time including any missing time due to technical and other difficulties.
8. You should work on Problem #1 first and then others afterwards. They are in increasing difficulties as judged by the instructor.
9. You MUST complete one problem in order not to fail the course.
10. Anyone who attempts to spam the server either through excessive submissions, allocating large amount of unnecessary memory, etc. will be penalized severely.
11. If you leave early from the examination without informing TA, you will not be able to come back to the examination.

## Written Midterm Matters

1. The midterm will test your knowledge of the materials up to Homework #3, that will be to include Heaps.
2. Answer all questions using the answer booklet. There will be more available at the venue if needed.
3. You can bring one sheet (A4, both sides) of notes. Calculator is not required. No electronics are allowed.
4. Write legibly. Anything we cannot decipher will be considered incorrect.

Final Examination
(Written)
Midterm Examination
(Written Part)
Midterm Examination
(Programming Part)
Assignments & Quizzes
50% 10% 20% 20%
1. Assignments (20%)
1. Written assignment
2. Programming assignment
3. Optional quizs
4. Late penalty: 10% for each day (no later than 3 days, only applicable for written assignment)
2. Midterms (30%)
1. Written (10%)
2. Programming (20%)
3. Final Examination (50%)
4. Extra Credit (There is no penalty for not doing the extra credit problems. Extra credit will only help you in borderline cases.)

Note: One must solve at least one problem in the programming examination to pass the course.

# Required Background

1. Pre-requisites
1. - CSCI 1110 or 1130 or its equivalent. (Not for students who have taken CSCI 2520).

# Reference Books

1. failed to fetch data: ```Could not connect to ecs.amazonaws.com:80 Connection timed out (110)```

[1997, book | www]
Mark Weiss, Data Structures and Algorithm Analysis in C, Addison Wesley, 1997.

2. failed to fetch data: ```Could not connect to ecs.amazonaws.com:80 Connection timed out (110)```

[1999, book | www]
Mark Weiss, Data Structures and Algorithm Analysis in C++, Addison Wesley, 1999.

3. failed to fetch data: ```Could not connect to ecs.amazonaws.com:80 Connection timed out (110)```

[1990, book | www]
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, The MIT Press, 1990.

# Other Books

1. Data Structures and Algorithms, Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Addison Wesley, 1983.
2. Data Structures and Their Algorithms, Harry R. Lewis and Larry Denenberg, HarperCollins Publisher, 1991.
3. Data Structures Using C and C++, Aaron M. Tenenbaum, Yedidyah Langsam, and Moshe J. Augenstein, Prentice Hall, 1995.

# FAQ

1. Q: What is departmental guideline for plagiarism?
A: If a student is found plagiarizing, his/her case will be reported to the Department Discipline Committee. If the case is proven after deliberation, the student will automatically fail the course in which he/she committed plagiarism. The definition of plagiarism includes copying of the whole or parts of written assignments, programming exercises, reports, quiz papers, mid-term examinations. The penalty will apply to both the one who copies the work and the one whose work is being copied, unless the latter can prove his/her work has been copied unwittingly. Furthermore, inclusion of others' works or results without citation in assignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caught plagiarizing during tests or examinations will be reported to the Faculty Office and appropriate disciplinary authorities for further action, in addition to failing the course.
2. Q: What is ACM ICPC?
A: Association of Computer Machinery International Collegiate Programming Contest. Teams from CUHK have done quite well in the previous years. More information on the CSE's programming team can be found at http://www.cse.cuhk.edu.hk/~acmprog.
3. Q: What are some of the common mistakes made in online and real-time contest?