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

# CSC2100B Data Structures

#### Breaking News

1 February 2008. Due to a prior commitment of the instructor, lectures on Monday (4 February 2008) and Tuesday (5 February 2008) will be CANCELLED. The homework assignment deadlines remain the same. The TAs will be available to assist you next week as usual.

## Spring 2008

 Lecture I Lecture II Tutorial I Tutorial II Tutorial III M7-8, 2:30 pm - 4:15 pm T2, 9:30 am - 10:15 am T9, 4:30 pm - 5:15 pm W5, 12:30 pm - 1:15 pm H9, 4:30 pm - 5:15 pm SC L2 ERB LT SC LG23 CKB 706C ERB 404

The Golden Rule of CSC2100B: No member of the CSC2100B community shall take unfair advantage of any other member of the CSC2100B 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).

# Personnel

 Lecturer Tutor Tutor Tutor Tutor Tutor Irwin King Chi Kong Chan Ling Ding Wai Shing Fung Li Zhao Rong Xiaobing Wu king AT cse.cuhk.edu.hk chanck AT cse.cuhk.edu.hk lding AT cse.cuhk.edu.hk wsfung AT cse.cuhk.edu.hk zrli AT cse.cuhk.edu.hk xbwu AT cse.cuhk.edu.hk Rm 908 Rm 1026 Rm 121A Rm 115 Rm 1026 Rm 121A 2609 8398 26098438 31634264 TBD 26098438 31634264 * M2, Monday 9:30 to 10:30 * T3, Tuesday 10:30 to 11:30 Tuesday 12:30 to 13:30 Wednesday 10:30 to 11:30 Tuesday 11:30 to 12:30 Wednesday 11:00 to 12:00 Wednesday 10:30 to 11: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 6.0. Please obtain the correct version of the Acrobat Reader from Adobe.

Week Date Topics Tutorials Homework & Events Resources
1 7/1, 8/1 Introduction

1. 01_intro_notes.pdf
No Tutorial TBD 1. podcast 1 (42:40)
2 14/1, 15/1 1. Algorithm Analysis
2. Recurrence

1. 02_Analysis_notes.pdf
2. 02.1_Recurrence_notes.pdf
Online Judge Guide and Introduction to C Read Chapter 1 and 2 1. podcast 1 (1:22:09)
2. podcast 2 (46:34)
3 21/1, 22/1 List, Stacks, and Queues

1. 03_LSQ_notes.pdf
List and Stacks * Read Chapter 3

* HW #1 (version 1.04)
* Written Assignment (Due on or before 6:00 pm, Tuesday, February 5, 2008)
* 1.1 (1), (3), and (8); 1.2 (2) and (3); 1.3 (2) and (5); 1.4; 1.5 (5) and (7), 1.8.

* Programming Assignment (Due on or before 11:59 pm, Tuesday February 5, 2008)
* 1.10 and 1.11.
Please check the announcement in tutorial page
1. podcast 1 (1:25:28)
2. podcast 2 (43:47)
4 28/1, 29/1 List, Stacks, and Queues

Tree Data Structures and Algorithms

1. 04_Tree_notes.pdf
TBD TBD 1. podcast 1 (1:18:51)
2. podcast 2 (45:35)
5 4/2, 5/2 CLASSES CANCELLED NO TUTORIALS TBD TBD
6 11/2, 12/2 CHINESE NEW YEAR HOLIDAY NO TUTORIALS TBD TBD
7 18/2, 19/2 Tree Data Structures and Algorithms TBD * Read Chapter 4

* HW #2 (version 1.04)
* Written Assignment (Due on or before 6:00 pm, Tuesday, March 4, 2008)
* 3.1 (2); 3.2 (2); 3.3 (2), 3.4; 3.6 (2); 3.7; 3.10; 3.11.

* Programming Assignment (Due on or before 11:59 pm, Tuesday, March 4 Friday, March 7, 2008) NEW!
* 2.4 and 3.22.
Please check the announcement in tutorial page
Due to some technical difficulties, this week's two podcasts are unavailable.
8 25/2, 26/2 Hash Functions

1. 05_Hashing_notes.pdf
TBD TBD 1. podcast 1 (1:24:02)
2. podcast 2 (40:06)
9 3/3, 4/3 Hash Functions TBD * Read Chapter 5

* HW #3 (version 1.05) NEW!
* Written Assignment (Due on or before 6:00 pm, Thursday, March 20, 2008)
* 3.12 (4), 3.13 (4), 3.14 (4), and 3.15.

* Programming Assignment (Due on or before 11:59 pm, Thursday March 20 Monday March 24, 2008) NEW!
* 2.7 and 3.32.
Please check the announcement in tutorial page
1. podcast 1 (45:44)
2. podcast 2 (43:25)
10 10/3, 11/3 1. Heaps
2. Sorting Algorithms

1. 06_Heaps_notes.pdf
2. 07_Sorting_notes.pdf
TBD TBD 1. podcast 1 (58:03)
11 17/3, 18/3 Sorting Algorithms TBD TBD 1. podcast 1 (1:16:11)
2. podcast 2 (43:02)
12 24/3, 25/3 EASTER HOLIDAY
Sorting Algorithms
TBD TBD TBD
13 31/3, 1/4 MIDTERM EXAMINATION
Graph Data Structures and Algorithms
TBD TBD TBD
14 7/4, 8/4 Graph Data Structures and Algorithms

1. 09_Graphs_notes.pdf
TBD * HW #4 (version 1.05)
* Written Assignment (Due on or before 6:00 pm, Friday, April 18, 2008)
* 4.1, 4.2, 5.1, 5.2, 5.7, 6.1, 6.2.1, 6.2.2, 6.6.3, 7.1, 7.3, 7.5
Please check the announcement in tutorial page
1. podcast 1 (1:26:16)
15 14/4, 15/4 1. Graph Data Structures and Algorithms
2. Course summary and final examination pointers
TBD TBD 1. podcast 1 (1:09:52)
2. podcast 2 (40:46)

<note> For detailed tutorial information, please go to Tutorial Page. </note>

# Examination Matters

## Examination Schedule

 Time Venue Notes Monday, 31 March 2008 TBD TBD 9:30 am, Saturday, 29 March 2008 Room 924 TBD 9:30 am, Thursday, 8 May 2008 Thomas H C Cheung Gym, UC The final examination covers all materials presented in the class but emphasizes more on the materials after the midterm.
```  Course     Scheduled                          Week                    No. of
Code/Title with                     Exam Date Day  Time Venue        Candidate
---------- ----                     --------- ---  ---- -----        ---------
CSC2100B                            08/05/08  THU  09:30 A.M.-11:30 A.M.   111
DATA STRUCTURES                     Thomas H C Cheung Gymnasium,UC
```

## 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 computer configuration will have these basic editors:
1. VI
2. Visual Studio
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 9:30 am 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 upto Assignment #3, that will be to include Trees.
2. You will be assigned the venue according to your last name.
3. Answer all questions using the answer booklet. There will be more available at the venue if needed.
4. Write legibly. Anything we cannot decipher will be considered incorrect.

Final Examination
(Written)
Midterm Examination
(Written Part)
Midterm Examination
(Programming Part)
Essays Presentation Lab reports Assignments
50% 10% 15% % % % 25%
1. Assignments (25%)
1. Written assignment
2. Programming assignment
3. Optional quizs
2. Midterms (10 + 15 = 25%)
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 problems in either of the midterms to pass the course.

# Required Background

1. Pre-requisites
1. - CSC 1110 or 1130 or its equivalent. (Not for students who have taken CSC 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.

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