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

# CSCI2100B Data Structures

### Breaking News

1. 7 December 2013. The following students do not submit their written homework 3: 1155034545, 1155030854, 1155034786, 1155034836, 1155046435, 1155023707, 1155033552, 1155034567, 1155032423. If you do submit, please contact TA before next Friday.
2. 6 December 2013. Sample solution for homework #3 has been posted. Credit Mr. Dai Mengjia for his good job.
3. 3 December 2013. Clarification: for the final exam, you can bring one sheet (A4, both sides) of notes. No calculator is allowed.
4. 19 November 2013. Programming assignment #3 is ready for you to submit from tomorrow (Nov 20, 2013, Wednesday). You can click here to see the ranking page. The award vector for the only problem will be (0,4,3,2,1,0,0,0). Remember that the 0th entry has no use. Problem #0 is kept for you to test the environment, no scores will be counted for this problem.
6. 12 November 2013. Summary for HW#2. For the written part, 96 of 105 students submitted their papers. We do not receive assignments from 1155032519, 1155030854, 1155034836, 1155046456, 1155033804, 1155023707, 1155033600, 1155033552, and 1155034567. If you do submit the homework, please contact TA as soon as possible. The average score is around 81. For the programming part, please check this file for your final score.
7. 8 November 2013. The solution for programming assignment #2 has been released. Good luck for your programming midterm!
8. 6 November 2013. Since the solution for 3.18 is not right, we have updated the solution document for HW#2. Please take a look at it to make sure that you understand B-tree.
9. 4 November 2013. Reminder: For tomorrow's written midterm, you can bring one cheat sheet (A4, both sides). Calculator is not allowed. Please get prepared. Good luck!
10. 1 November 2013. The date and venue for the final exam have been confirmed. Please find the detailed information in the examination section.
11. 30 October 2013. Manual page has been set up yesterday. By now, only information about the operating system and editors is provided in this page. We will appreciate it if you can give us any suggestion to improve this page. Please send your suggestion to the lecturer or tutors by email.
12. 20 October 2013. Programming assignment #2 is ready for you to submit from tomorrow (Oct 21, 2013, Monday). You can click here to see the ranking page. The award vectors for the 3 problems will be (0,5,4,3,2,1,0,0), (0,5,5,4,3,2,1,0) and (0,6,6,5,4,3,2,1). Remember that the 0th entry has no use. Problem #0 is kept for you to test the environment, no scores will be counted for this problem.
13. 18 October 2013. Summary for HW#1. For the written part, 102 of 105 students submitted their papers. We do not receive assignments from 1155033552, 1155034567, and 1155046456. The average score is around 85. Please collect your papers in the next lecture. For the programming part, please check this file for your final score. For both parts, if you have any questions, please contact TAs asap.
14. 16 October 2013. HW#2 has been announced in the course website, please download the newest version. Solutions for HW#1 has been released as well.
16. 22 September 2013. For those who still have not received CSE account, please send your programs to TA (hyzhang@cse.cuhk.edu.hk). TA will submit for you and forward the respond to you. This is only for assignment #1 since you will receive the account by next time. Please contact TA if you have any questions.
17. 22 September 2013. Programming assignment #1 is ready for you to submit from tomorrow (Sep 23, 2013, Monday). You can click here to see the ranking page. The award vectors for both problems will be (0,3,2,1,0,0,0,0) and (0,4,3,2,1,0,0,0). Remember that the 0th entry has no use. Problem #0 is kept for you to test the environment, no scores will be counted for this problem.
18. 10 September 2013. Lab session material has been uploaded to the tutorial page.
19. 5 September 2013. For all students in this class, please swap to the new tutorial session in CUSIS during the e-add/drop next week and the TBA session would be removed later. Tutorials will start from next week.
20. 3 September 2013. Since many of you are not familiar with C programming language, we prepare a 6-week-long lab session together with other 2 data structure classes. This session will begin from next week. You can freely choose one of the 4 time slots to attend in each week. We will provide tutorials and handouts. There are no assignments for this session.
21. 2 September 2013. The website is now ready!

## Fall 2013

 Lecture I Tutorial I Tutorial II Tutorial III Lab session T2-4, 9:30 am - 12:15 pm W6, 1:30 pm - 2:15 pm W7, 2:30pm - 3:15 pm H6, 1:30pm - 2:15 pm Mon to Thu, 5:30 pm - 7:30 pm LSB LT1 BMS LT BMS LT LSB C1 SHB924

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

# 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 Tutor Tutor Tutor Irwin King Yuanming Yu Hongyi Zhang Shenglin Zhao Fei Chen king AT cse.cuhk.edu.hk ymyu AT cse.cuhk.edu.hk hyzhang AT cse.cuhk.edu.hk slzhao AT cse.cuhk.edu.hk fchen AT cse.cuhk.edu.hk SHB 908 SHB 805 SHB 1024 SHB 1024 SHB 913 3943 8398 NA 5984 1406 (inquiry for homework) 5983 2723 (inquiry for lab session) NA * M8, Monday 3:30 to 4:30 * T8, Tuesday 3:30 to 4:30 * By appointment NA * H7, Thursday 14:30 to 15:30 * H8, Thursday 15:30 to 16:30 NA

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 Topics Tutorials Homework & Events Resources
1 3/9 Introduction

Introduction.pdf
No Tutorials TBA TBA
2 10/9 Algorithm Analysis

Analysis.pdf
Introduction on C TBA TBA
3 17/9 1.Recurrence Relations
2. List, Stacks, and Queues

Recurrence.pdf
LSQ.pdf
Online Judge System * HW #1 (Version 1.16)
* Written Assignment (Due on or before 5:00 pm, Friday, Sep 27, 2013)
* 1.1 (6), (8), (12) and (13); 1.2 (3); 1.3 (1) and (5); 1.4 (5) and (6); 1.6 (1), (3), and (5); 1.8 (3); 1.9 (2) and (4)

* Programming Assignment (From 12:00 am, Monday, Sep 23, 2013 to 11:59 pm, Sunday, Sep 29, 2013)
* 1.17 (Problem 1) and 1.20 (Problem 2)
TBA
4 24/9 Tree Data Structures and Algorithms

Tree.pdf
I/O Issues in C TBA TBA
5 1/10 Public Holiday List, Stacks, and Queues in C TBA TBA
6 8/10 Tree Data Structures and Algorithms Trees in C TBA TBA
7 15/10 Hash Functions

Hash.pdf
Hash in C *HW #2 (Version 1.17)
* Written Assignment (Due on or before 5:00 pm, Monday, Oct 28, 2013)
* 3.2 (2); 3.3 (2); 3.5; 3.9 (please zoom in); 3.10; 3.11; 3.12 (2); 3.18; 4.1 (1) and (2); 4.4; 4.15; 5.1; 5.2

* Programming Assignment (From 12:00 am, Monday, Oct 21, 2013 to 11:59 pm, Sunday, Oct 27, 2013)
* 2.17 (Problem 1), 3.35 (Problem 2), and 4.17 (Problem 3)
TBA
8 22/10 1. Heaps
2. Sorting Algorithms

Heaps.pdf
Sort.pdf
Heaps in C Solutions for HW#1 TBA
9 29/10 Sorting Algorithms HW #2 Solution Solutions for HW#2 (Written part) Programming Midterm Paper 12-13 Term 2
10 5/11 Midterm Written Exam

Midterm Programming Exam
PC2 Tutorial for Midterm Solution for HW#2 (Programming part) TBA
11 12/11 Sorting Algorithms Written Midterm Solution TBA TBA
12 19/11 Graph Data Structures and Algorithms

Graphs.pdf
Quicksort and Mergesort in C * HW #3 (Version 1.18)
* Written Assignment (Due on or before 5:00 pm, Thursday, Nov 28, 2013)
* 6.2 (3); 6.3; 6.4; 6.6 (2); 6.7; 6.9 (name two stable ones and two unstable ones); 7.1; 7.3 (1); 7.4; 7.5 (1);

* Programming Assignment (From 12:00 am, Wednesday, Nov 20, 2013 to 11:59 pm, Tuesday, Nov 26, 2013)
* 6.10 (Problem 1)
TBA
13 26/11 1. Graph Data Structures and Algorithms

2. Course Summary

Final.pdf
Graph Revisited Solutions for HW#3 (Written part) 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 9:30 am - 11:30 am, Nov 5, 2013 LSB LT1 The scope is all materials up to heaps (including heaps). You can bring one cheat sheet (A4, both sides) of notes. Calculator is not required. 6:00 pm - 9:30 pm, Nov 8, 2013 SHB 924 The scope is all materials up to heaps (including heaps). You can bring print outs of previous programming homework assignments. 3:30 pm - 5:30 pm, Dec 9, 2013 Multi-purpose Hall, Pommerenke Student Centre The final examination covers all materials presented in the class, but emphasizes more on the materials after the midterm. You can bring one cheat sheet (A4, both sides) of notes. Calculator is not allowed.

## 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 to room 924. 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. If you would like to have other editors, you MUST send an email to the instructor and TAs no later than 7 days before the examination date and it will be subject to approval to be included on the computer system.
4. You should arrive to the venue before 5:30 pm on the day of the examination to receive your information and check the system.
5. 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.
6. You should work on Problem #1 first and then others afterwards. They are in increasing difficulties as judged by the instructor.
7. You MUST complete one problem in order not to fail the course.
8. Anyone who attempts to spam the server either through excessive submissions, allocating large amount of unnecessary memory, etc. will be penalized severely.
9. If you leave early from the examination, 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 #2, 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
50% 10% 20% 20%
1. Assignments (20%)
1. Written assignment
2. Programming assignment
3. Optional quizs
4. Late penalty: 10% for each day (no late than 4 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 examination.

# 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. Introduction to Algorithms, Thoas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press, 1990.
3. Data Structures and Their Algorithms, Harry R. Lewis and Larry Denenberg, HarperCollins Publisher, 1991.
4. 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?