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

# CSCI2100 Data Structures

### Breaking News

1. 19 April 2015. The last tutorial will be given at 5:30 pm, 20 April in ERB 407.
2. 15 April 2015. IMPORTANT & URGENT The schedule of make-up exam for students who did not solve any problems during programming midterm is out. It will be held between 6:30 pm - 8:00 pm, April 17, Friday, 2015 in SHB 924. We will provide three straightforward problems and you only need to solve one of your choice to pass the exam. The details are sent to your email (s11550XXXXX@mailserv.cuhk.edu.hk). If you have time conflict or other issues, please contact Mr. ZHANG Hongyi or Mr. HUANG Xin as soon as possible. We will try our best to make proper arrangement for you. Thanks.
3. 8 April 2015. 1) The deadline for HW5 is postponed to next Friday, April 17, 2015. 2) The tutorial on April 15 is canceled. The content of tutorial of next Monday will be the same as this Wed, i.e., April 8.
4. 29 March 2015. We've prepared an archive of sample code for almost all the data structures you've learnt by now. Please download it from the syllabus frame. We recommend you print it and bring it to the midterm exam. You can find the original files here. We've combined each data structure into one single file for your convenience.
5. 26 March 2015. In WA4, Problem 6.6(2), note that median of three, we take the median of first, middle and last element as the pivot, then swap the first and pivot, after this, the partition is the same as the code in the lecture notes. The code in lecture notes (Slide 65) will split the array into three parts, left part less or equal to pivot, pivot and right part larger than pivot. Please note that the goal in Slide 66 is not corresponding to the code in Slide 65, the goal should be < =p, p, >p which is corresponding to the code in Slide 65.
6. 26 March 2015. In WA4, Problem 4.14, the right answer should be for ordered list O(N^2), for unordered list O(N). The meaning is that when collision happens, we want to make the chaining list ordered or unordered. So if ordered, we need the do insertion sort in the chaining list, if unordered, we just need to insert at the front. Sorry that the tutor misunderstood the meaning of problem during the tutorial.
7. 26 March 2015. Last year's programming midterm paper is posted on the website for your reference. No answers will be provided though.
8. 25 March 2015. The grading of Written Assignment 3 has been finished. You may retrieve your homework during the tutorial session. You can fetch your homework at Rm 1024 SHB if you do not collect during the tutorial. If you find the sum of score is miscalculated or cannot find your assignment, please contact TA as soon as possible.
9. 23 March 2015. The reward vectors for Problem 1, 2 and 3 are (5,5,4,4,3,2,1), (4,4,3,3,2,2,1) and (4,4,3,3,2,2,1), respectively. You can check the ranking here.
10. 19 March 2015. IMPORTANT Please pay attention that for your ease of reading input, we've changed the input format for Problem 2 (5.12) of programming assignment #4.
11. 10 March 2015. If you want to know the details about your written midterm score, you can come the SHB1024 to check your exam paper during office hour or by appointment. Thanks for the cooperation.
12. 25 February 2015. Information for written midterm examination.
1. Date: 4 March
2. Time: 10:35 am to 12:25 pm
3. Venue:
1. SWH 2 (117) AU to KIM
2. YIA LT2 (248) LAI to ZHANG
4. One A4 sheet (2-sided) of notes allowed
5. No tutorial this week.
13. 24 February 2015. The reward vectors for Problem 1 and 2 are (3,2,2,1,1) and (6,6,5,5,4), respectively. You can check the ranking here.
14. 9 February 2015. The solutions and sample codes for PA#1,2 have been out. In addition, several FAQ have been added on the course website (keep scrolling down). Please take a look at them.
15. 9 February 2015. The grading of Written Assignment 2 has been finished. You may retrieve your homework during the tutorial session. The left will be put above the homework collection box at 10th Floor, SHB. If you find the sum of score is miscalculated or cannot find your assignment, please contact TA as soon as possible.
16. 6 February 2015. IMPORTANT Started from 9 Feb, 2015 (Mon) the venue of CSCI2100A lecture M12:30-1:15 is changed from SC L2 to ERB LT, Thank you for your attention.
17. 4 February 2015. URGENT Please re-submit your code for Problem 2. Some of the original test cases have exceed the limit of int. We've deleted all those test cases. There will be no penalty for this problem. We are sorry and thank you for understanding.
18. 1 February 2015. The reward vectors for Problem 1, 2, 3 are (6,5,4,3,2,1,0), (5,4,3,2,1,0,0) and (5,5,5,4,3,2,1), respectively. You can check the ranking here.
19. 1 February 2015. IMPORTANT For programming assignment #2, Problem 3 is exactly the same as Problem 2 except for two things: 1. the range of n; 2. the answer will be fi t in a signed 64-bit (not 32-bit) integer, which means you should use the type of long long to store it (use %lld in printf()). Please be careful on the time complexity of your algorithm.
20. 27 January 2015. Since It is the first time to use online judge as submission tool, we decide not to count penalty in your final score for Programming Assignment 1. You will get full mark for each accepted problem. Penalty will be considered from next time.
21. 26 January 2015. The grading of Written Assignment 1 has been finished. You may retrieve your homework during the tutorial session. The left will be put above the homework collection box at 10th Floor, SHB. If you find the sum of score is miscalculated or cannot find your assignment, please contact TA as soon as possible.
22. 22 January 2015. IMPORTANT Started from 26 Jan, 2015 (Mon) the venue of CSCI2100A lecture M12:30-1:15 is changed to SC L2.
23. 22 January 2015. The reward vectors for Problem 1 & 2 are (4,3,2,1,0) and (3,2,1,0,0), respectively. You can check the ranking here.
24. 21 January 2015. For those who still do not have CSE UNIX account to submit to programming assignment, you have two ways to retrieve your account info: 1. come to SHB 1024 and find TA; 2. email hyzhang AT cse.cuhk.edu.hk with your name and student ID. If you do not contact TA until tonight, we will send your account and password to your CUHK email (s11550XXXXX@cuhk.edu.hk).
25. 20 January 2015. The slides of Week 2 have been updated. Please download it again. The pdf file for Week 3 on List, Stack, and Queue (LSQ) is also available below now. You are also welcome to watch the videos on “Jill Rides Again”, “ADT”, “List”, “Stack”, and “Queue”.
26. 19 January 2015. Next time when you turn in your written assignment, if you have more than one A4 papers, please remember to staple them together so that it is easy for us to collect. Thanks.
27. 19 January 2015. We will distribute UNIX accounts for all the Non-CSE students on Wednesday (Jan 21)'s lecture. TA will keep all the remaining accounts. Do remember to collect it, otherwise you cannot submit your programming assignments.
28. 6 January 2015. The venue of Tutorial II will be ERB 404.
29. 5 January 2015. Tutorial II has been set up on every Wednesday 3:30 pm - 4:15 pm. The venue is still to be announced. The content of two tutorial sessions will be the same.
30. 1 January 2015. The website is now available!

## Spring 2014-2015 Term 2

 Lecture I Lecture II Tutorial I Tutorial II M5, 12:30 pm - 1:15 pm W3-4, 10:30 am - 12:15 pm M10 5:30 pm - 6:15pm W8 3:30 pm - 4:15 pm ERB LT LSK LT5, LSK LT3 ERB 407 ERB 404

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].

# 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 Chen Cheng (Robbie) Xin Huang Zhengwei Yang Hongyi Zhang king AT cse.cuhk.edu.hk ccheng AT cse.cuhk.edu.hk xhuang AT cse.cuhk.edu.hk zwyang AT cse.cuhk.edu.hk hyzhang AT cse.cuhk.edu.hk SHB 908 SHB 1024 SHB 117 SHB1023 SHB 1024 3943 8398 * M8, Monday 3:30 to 4:30 * T8, Tuesday 3:30 to 4:30 * By appointment Wednesday 3:30 to 4:30 Friday 9:30 to 10:30 Monday 9:30 to 10:30 Thursday 3:30 to 4:30

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 5/1 Introduction

01-Introduction.pdf
Introduction of C * Reading assignment: Chapter 1 of Weiss'97 and Chapter 1 of Cormen et al.'90

* WA #1 Version 1.19
Due on or before 5:00 pm, Friday, Jan 16, 2015
* 1.1 (5), (8), and (13); 1.3 (5) and (8); 1.4 (3) and (5)
TBA
2 12/1 Algorithm Analysis

02-Analysis.pdf
I/O Issues in C * Reading assignment: Chapter 2 of Weiss'97

* Introduction of Online Judge System
3 19/1 1. Algorithm Analysis
2. Lists, Stacks and Queues

Maximum Subsequence Sum Problem.pdf
03-LSQ.pdf
Introduction to VIM * Reading assignment: Chapter 3 of Weiss'97

* WA #2 Version 1.19
Due on or before 5:00 pm, Friday, Jan 30, 2015
* 1.6 (2), (4), and (6); 1.8 (3); 1.9 (3) and (4)

* PA #1
From 12:00 am, Thursday, Jan 22, 2015 to 11:59 pm, Monday, Jan 26, 2015
1.15 (Problem 1), 1.19 (Problem 2)
Video List:
Jill Rides Again
Lists
Stacks
Queues
4 26/1 1. Lists, Stacks and Queues
2. Tree Data Structures and Algorithms

04-Trees.pdf
Lists, Stacks and Queues in C * Reading assignment: Chapter 3 of Weiss'97

* PA #2
From 12:00 am, Monday, Feb 2, 2015 to 11:59 pm, Sunday, Feb 8, 2015
2.16 (Problem 1), 2.18 (Problem 2, a small one, n< =1,000), 2.18 (Problem 3, a large one, n< =1,000,000, use “long long” and ”%lld”, see announcement for details)
TBA
5 2/2 Tree Data Structures and Algorithms Queues and Trees in C * Reading assignment: Chapter 4 of Weiss'97

* WA #3 Version 1.19
Due on or before 5:00 pm, Tuesday, Feb 17, 2015
* 3.3 (2); 3.9; 3.10; 3.11; 3.18; 5.1; 5.2;
TBA
6 9/2 1. Tree Data Structures and Algorithms
2. Heaps

06-Heaps.pdf
Binary and AVL Tree in C * Reading assignment: Chapter 6 of Weiss'97

* PA #3
From 12:00 am, Wednesday, Feb 25, 2015 to 11:59 pm, Sunday, Mar 1, 2015
3.24 (Problem 1), 3.35 (Problem 2)
7 16/2 Heaps
Public Holiday (Wednesday)
Heaps in C TBA TBA
8 23/2 Public Holiday (Monday)
Hash Functions

05-Hash.pdf
Heaps in C * Reading assignment: Chapter 5 of Weiss'97

TBA
9 2/3 Midterm Written Exam No Tutorials TBA TBA
10 9/3 Sorting Algorithms

07-Sorting.pdf

* WA #4 Version 1.19
Due on or before 5:00 pm, Friday, Mar 20, 2015
* 4.1; 4.14; 6.1; 6.2; 6.6(2)
11 16/3 Sorting Algorithms Hash * PA #4 TBA
12 23/3 Graph Data Structures and Algorithms

08-Graphs.pdf
Quicksort and Mergesort Programming Midterm Tips
Programming midterm paper 2013 Term 1 }
13 30/3 Graph Data Structures and Algorithms

Programming Midterm
No Tutorials * WA #5 Version 1.20
Due on or before 5:00 pm, Friday, April 17, 2015
* 7.1; 7.3; 7.4; 7.5 (1);
14 6/4 Public Holiday (Monday)
Graph Data Structures and Algorithms
TBA TBA TBA
2. Course Summary

Courser Summary.pdf
TBA TBA

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 Wednesday, 4 March 2015 10:30 AM to 12:30 PM SWH 2 (117) AU to KIM YIA LT2 (248) LAI to ZHANG One sheet of notes Thursday, 2 April 2015 6:30 pm to 9:30 pm SHB 924 Printed out materials only. Thursday, 23 April 2015 3:30 pm to 5:30 pm Thomas H C Cheung Gymnasium, UC One sheet of notes

## 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 45 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.

# Book Sources

1. Academic & Professional Book Centre, 1H Cheong Ming Bldg., 80-86 Argyle St., Kowloon, 2398-2191, 2391-7430 (fax)
2. Caves Books (H. K.), 4B Ferry St., G/F., Yaumatei, Kowloon, 2780-0987, 2771-2298
3. Man Yuen Book Company, 45 Parkes street, Jordan Road, Kowloon, Hong Kong, 2366-0594. Not very large, Asian edition books, fair price, wide range, some 10% discount.
4. Swindon Book Co. Ltd, 13-15 Lock Road, Tsim Sha Tsiu, Kowloon, 2366-8001. One of the largest book stores in Hong Kong, exchange rate is not favorable.
5. Hongkong Book Centre, 522-7064. A branch of the Swindon book shop.

# 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?