This is an old revision of the document!
CSCI2100 Data Structures
Discussion forum
**Here** is the link to our discussion forum.
Breaking News
Spring 20172018 Term 2
Lecture I  Lecture II  Tutorial I  Tutorial II  

Time  M5, 12:30 pm  1:15 pm  T56, 12:30 pm  2:15 pm  M10 5:30 pm  6:15pm  W10 5:30 pm  6:15 pm 
Venue  LSK LT3  LSK LT3  LHC 104  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].
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, 23 tree, Btree, 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.
本科介紹抽象數據類型之概念及數據抽象化的優點。並討論多種常用的抽象數據類型，包括向量、表格、堆棧、隊列、樹形；集(合)和利用不同的數據結構(例如：陣列、指示字為基的結構、連接表、23樹形、B樹形等)作出的實踐。更以實例(例如：檢索、排序等)來說明數據抽象化在計算機程序設計上的應用。並討論檢索與排序算法及數據結構之應用。
Prerequisite and Enrollment policy
Prerequisite: 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 senioryear 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.
Learning Objectives
 To understand the concepts and operations of various data structures and their applications
 To understand the concept of abstract data types
 To have basic knowledge of algorithms and complexity of algorithms
Learning Outcomes
 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), Btree, trie, disjoint set, graph (including minimum spanning tree and shortest path).
 To be able to use appropriate data structures in different applications.
 To be able to implement abstract data types.
 To be able to analyse the complexity of simple algorithms (such as searching and sorting).
Learning Activities
 Lectures
 Tutorials
 Web resources
 Assignments
 Examinations
Personnel
Lecturer  Tutor 1  Tutor 2  Tutor 3  

Name  Irwin King  Wang Chen  Shuyue Hu  Jiani Zhang 
king AT cse.cuhk.edu.hk  wchen AT cse.cuhk.edu.hk  syhu AT cse.cuhk.edu.hk  jnzhang AT cse.cuhk.edu.hk  
Office  SHB 908  SHB 1024  SHB 1005  SHB 1024 
Telephone  3943 8398  
Office Hour(s)  * By appointment  Friday 11:00 am  12:00 am  Thursday 4:00 pm  5:00 pm  Wednesday 4:00 pm  5: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  9/1  Introduction Introduction First Lecture KEEPAttendance  Introduction to C C programming tutorial 1 C programming tutorial 2  * WA #1 hw_1.19.pdf Due on or before 5:00 pm, Thursday, Jan 26, 2017 * 1.1 (1), (9), and (13); 1.3 (4) and (8); 1.4 (2) and (6) WA1 solution  * Chapter 1 of Weiss'97 * Chapter 1 of Cormen et al.'90 
2  16/1  Algorithm Analysis Analysis (updated)  Online Judge System  * PA #1 hw_1.25.pdf From 00:00 am, Monday, Feb 06, 2017 to 11:59 pm, Sunday, Feb 12, 2017 * 1.23(Problem 1);1.24(Problem 2) 1.23 solution 1.24 solution  * Chapter 2 of Weiss'97 
3  23/1  1. Algorithm Analysis 2. Lists, Stacks and Queues Recurrence LSQ  Linux commands and vim  * WA #2 hw_1.25.pdf Due on or before 5:00 pm, Friday, Feb 10, 2017 * 1.6 (1), (2), and (6); 1.8 (3); 1.9 (2) and (3) WA2 solution  * Chapter 2 of Weiss'97 * Chapter 3 of Weiss'97 
4  30/1  Chinese New Year Holiday  
5  6/2  1.Lists, Stacks and Queues 2.Tree Data Structures and Algorithms Trees  I/O issues in C  * PA #2 hw_1.26.pdf From 00:00 am, Friday, Feb 17, 2017 to 11:59 pm, Thursday, Feb 23, 2017 * 2.20(Problem 1);2.21(Problem 2) 2.20 solution 2.21 solution  * Chapter 3 of Weiss'97 
6  13/2  Tree Data Structures and Algorithms  Lists, Stacks,Queues  * WA #3 hw_1.26.pdf Due on or before 5:00 pm, Friday, Mar 3, 2017 * 3.3 (3); 3.9; 3.11; 3.18; 5.1; 5.2; 5.6 WA3 solution  * Chapter 4 of Weiss'97 
7  20/2  1. Tree Data Structures and Algorithms 2. Heaps Trie Heap  Binary and AVL Trees in C  * PA #3 hw_1.27.pdf From 00:00 am, Friday, March 03, 2017 to 11:59 pm, Thursday, March 09, 2017 * 3.32(Problem 1);3.35(Problem 2);3.37(Problem 3) <choose 2> 3.32 solution 3.35 solution 3.37 solution  * Chapter 4 of Weiss'97 
8  27/2  1. Heaps 2. Hash Functions Hash  Heaps in C  * WA #4 hw_1.27.pdf Due on or before 5:00 pm, Friday, Mar 17, 2017 * 4.1; 4.15; 6.1; 6.4; 6.6 (1) WA4 solution  * Chapter 6 of Weiss'97 * Chapter 5 of Weiss'97 
9  6/3  1. Hash Functions 2. Sorting Algorithm Btree Sorting  Hashing in C  * PA #4 hw_1.28.pdf From 00:00 am, Friday, March 17, 2017 to 11:59 pm, Thursday, March 23, 2017 * 4.18(Problem 1);5.12(Problem 2) 4.18 solution 5.12 solution  * Chapter 5 of Weiss'97 
10  13/3  Sorting Algorithms  Pointer in C  No assignment  * Chapter 7 of Weiss'97 
11  20/3  1. Sorting Algorithms 2. Graphs Graphs  Programming Midterm Preview  No assignment  * Chapter 7 of Weiss'97 
12  27/3  1. Graph Data Structures and Algorithms 28/3 Midterm Written Exam 31/3 Midterm Programming Exam  No Tutorial  Sample Code  
13  3/4  3/4 No class 4/4 Ching Ming Festival  * Chapter 9 of Weiss'97 

14  10/4  Graph Data Structures and Algorithms  * WA #5 hw_1.28.pdf Due on or before 5:00 pm, Friday, April 28, 2017 * 7.1; 7.3; 7.4; 7.5 (1) WA5 solution  * Chapter 9 of Weiss'97 

15  17/4  17/4 Easter 1. Graph Data Structures and Algorithms 2. Course Summary Final Summary  * PA #5 hw_1.29.pdf From 00:00 am, Monday, April 24, 2017 to 11:59 pm, Sunday, April 30, 2017 * 6.12(Problem 1);7.8(Problem 2) 6.12 solution 7.8 solution 
Tutorial Page
 For detailed tutorial and lab session information, please go to Tutorial Page.
Manual Page
 For supplementary material on various topics related to this course, please go to Manual Page. Enjoy your Exploration.
Examination Matters
Examination Schedule
Time  Venue  Notes  

Midterm Examination Written  12:30 pm  14:15 pm 3/28  LSK LT3 & LT7  TBA 
Midterm Examination Programming  17:30 pm  21:00 pm 3/31  SHB 924 & 904  TBA 
Final Examination  9:30 am  11:30 am 5/10  University Gymnasium  TBA 
Programming Midterm Matters
 The programming midterm is an openbook and opennotes 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.
 The operation system will be Ubuntu. And the computer configuration will have these basic editors:
 vi/vim
 emacs
 gedit
 nano
 You can use all the functions provided by standard C library as long as you include the header file.
 This system includes GDB for debugging. You need to work on Terminal in order to use it.
 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.
 You should arrive at the venue 30 minutes before the starting time on the day of the examination to receive your account information and check the system.
 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.
 You should work on Problem #1 first and then others afterward. They are in increasing difficulties as judged by the instructor.
 You MUST complete one problem in order not to fail the course.
 Anyone who attempts to spam the server either through excessive submissions, allocating a large amount of unnecessary memory, etc. will be penalized severely.
 If you leave early from the examination without informing TA, you will not be able to come back to the examination.