Table of Contents

CSCI2100 Data Structures

Discussion forum

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

KEEP Paid Internship

Breaking News

  1. 3 May 2017 The solutions of WA5 have been released.
  2. 2 May 2017 Please check your scores of all the WAs and PAs. If there is any mistake, please contact TA as soon as possible. And you can come to SHB1024 to take back your WA1-WA5.
  3. 2 May 2017 The solutions of PA4 and PA5 have been released.
  4. 18 April 2017. PA5 was released. The reward vectors for Problem 1 & 2 are (5,4,4,3,2,1,0) and (5,4,4,3,2,1,0), respectively.
  5. 11 April 2017. You can come to SHB 1024 to check your midterm examination paper if needed.
  6. 30 March 2017. Please check your score of PA4. If there is any mistake, please contact TA as soon as possible.
  7. 28 March 2017 The solutions of WA3 have been updated.
  8. 27 March 2017 The solutions of WA1 and WA2 have been released.
  9. 27 March 2017 Sample Code of linked list, stack, queue, binary search tree, AVL tree, heap, hashing, sorting and graph is for your reference.
  10. 27 March 2017 Final Exam will be arranged in the University Gymnasium from 9:30 am - 11:30 am, 10th May , 2017.
  11. 24 March 2017 The solutions of WA3 and WA4 have been released.
  12. 20 March 2017. Mid-term Exam Scope The scope of the mid-term programming exam is up to (and includes) hashing. The scope of the mid-term written exam is before hashing.
  13. 20 March 2017. Editors used in Mid-term Progamming Exam (1) Vi/Vim (2) Emacs (3) Gedit (with GUI) (4) Nano
  14. 20 March 2017. Mid-term Programming Exam The mid-term programming exam will be located in two rooms Rm924 SHB and Rm904 SHB. From 5:30p.m.-6:00p.m. there is a warmup session. The formal exam will be start at 6:00p.m. Your seating positions will be released just before the mid-term exam.
  15. 20 March 2017. Mid-term Written Exam The mid-term written exam will be located in two rooms LSK LT3 and LSK LT7. Students whose last name starts from A to K are arranged in LT3 and Students whose last name starts from L to Z are arranged in LT7.
  16. 19 March 2017. The solutions of PA1-PA3 have been released.
  17. 17 March 2017. We have received WA3 from students listed in the attachment: WA3. If you have submitted your homework but have not been included in the list, please contact TA as soon as possible.
  18. 13 March 2017. Please check your score of PA 1, PA2, PA3, WA1, WA2. If there is any mistake, please contact TA as soon as possible.
  19. 9 March 2017. PA4 was released. The reward vectors for Problem 1 & 2 are (3,2,2,2,1,1,0) and (3,2,2,2,1,1,0), respectively.
  20. 8 March 2017. Mistakes in tutorial: 'HashVal « 5' is equivalent to a multiplication by 32.
  21. 4 March 2017. Written Assignment 4 is now available.
  22. 3 March 2017. IMPORTANT The "Presentation Error" issue of problem 1 of PA3 has been fixed. Please try to submit your program again! If you have been deducted marks because of this issue, show me (wangzaicuhk@gmail.com) the judge system reply mails which are sent to you before 10:10 am as evidence. I will add your marks up.
  23. 01 Mar 2017. As for PA3, the reward vectors for Problem 1 & 2 & 3 are (4,3,3,3,2,1,0), (4,3,3,3,2,1,0), and (5,4,4,4,2,1,0) respectively. The online judge system will open for programming assignment 3 ( from 00:00 am, Mar 02 to 11:59 pm, Mar 09.)
  24. 25 February 2017. PA3 was released. There are three problems. You can choose any two of them. Since we will take the sum of two maximum scores for your final PA3 score. The maxmimum score is also 200.
  25. 21 February 2017. We have received WA2 from students listed in the attachment: WA2. If you have submitted your homework but have not been included in the list, please contact TA as soon as possible.
  26. 16 February 2017. Written Assignment 3 is now available.
  27. 10 February 2017. The second Programming Assignment has been released. The reward vectors for Problem 1 & 2 are (5,4,4,4,2,1,0) and (5,4,4,4,2,1,0), respectively. For example, if your code files for problem 2.20 is “220.c” and for problem 2.21 is “221.c”, then the submit commands are “submit 1 220.c” and “submit 2 221.c”, respectively
  28. 08 February 2017. To understand gets() and fgets() , please refer to the following links: link 1, link 2, link 3
  29. 08 February 2017. We have received WA1 from students listed in the attachment:WA1. If you have submitted your homework but have not been included in the list, please contact TA as soon as possible.
  30. 07 February 2017. We highly recommend you for the discussion forum, and if you want to send email, please send to all TAs.
  31. 06 February 2017. Possible solutions for the problems using online judge system. See FAQ section.
  32. 06 February 2017. IMPORTANT The classroom for tutorial I is changed to LHC 104
  33. 05 February 2017. IMPORTANT The online judge system is opening for programming assignment 1 ( from 00:00 am, Feb 06 to 11:59 pm, Feb 12.) 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.
  34. 03 Februray 2017. Temporary accounts have been sent to non-CSE students through their CUHK email.
  35. 25 Januray 2017. IMPORTANT The submitting period for programming assignment 1 is changed to be from 00:00 am, Feb 06 to 11:59 pm, Feb 12.
  36. 25 January 2017. Written Assignment 2 is now available.
  37. 23 January 2017. Video instructions for CSE UNIX server have been updated. You can get the links from our tutorial page.
  38. 23 January 2017. The first Programming Assignment has been released. 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.23 is “123.c” and for problem 1.24 is “124.c”, then the submit commands are “submit 1 123.c” and “submit 2 124.c”, respectively.
  39. 20 January 2017. For programming assign, submission 0 is always open for your testing, but the ranking page will not update. If you receive an 'accepted' email, it means everything is okay.
  40. 19 January 2017. A tutorial about how to transfer files to the cse server is released on the tutorial page for your reference.
  41. 18 January 2017. Two C programming tutorial videos have been put on the tutorial page. Hope these videos helpful.
  42. 16 January 2017. Mac users NOT in CSE network require to access the CSE linux server using the following command: ssh -oHostKeyAlgorithms=+ssh-dss username@gw.cse.cuhk.edu.hk. Tutorial2 is also updated for your reference.
  43. 15 January 2017. Written assignment 1 is now available. When you turn in your homework (the homework box is on Floor 10, SHB), please remember to staple them together if you have more than one page of A4 paper. Thanks.
  44. 7 January 2017. The new course website has been created.

Spring 2016-2017 Term 2

Lecture I Lecture II Tutorial I Tutorial II
Time M5, 12:30 pm - 1:15 pm T5-6, 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, 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.

本科介紹抽象數據類型之概念及數據抽象化的優點。並討論多種常用的抽象數據類型,包括向量、表格、堆棧、隊列、樹形;集(合)和利用不同的數據結構(例如:陣列、指示字為基的結構、連接表、2-3樹形、B樹形等)作出的實踐。更以實例(例如:檢索、排序等)來說明數據抽象化在計算機程序設計上的應用。並討論檢索與排序算法及數據結構之應用。

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.

Linux Command Line Basics

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
Name Irwin King Wang Chen Shuyue Hu Jiani Zhang
Email 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)
* 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)
* 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)
* 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)
* 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
* 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>
* 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)
* Chapter 6 of Weiss'97
* Chapter 5 of Weiss'97
9 6/3 1. Hash Functions
2. Sorting Algorithm

B-tree
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)
* 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)
* 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)

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

  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 at 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 afterward. 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 a 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.

Grade Assessment Scheme

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 grade appeal?
    A: 1) Students must write (in written) to the Dept. Chairman grade appeal. The letter should hand in to the General Office within the time frame set by RES. 2) Justifications for grade appeal must be given. Disappointment about the grade obtained is not a justification. Students have to provide their arguments over their expected grades based on scores they obtained from their work (eg. assignment, quiz, mid-term/final, etc.). 3) Office staff will then pass on the letter to the course teacher for review. It is the course teachers' discretion on whether they would like to go over the exam answer script with the student together. 4) Teachers inform the office staff whether grade amendment is needed. 5) Office staff prepares a formal reply to the students, and writes to the RES for grade amendment if necessary.
  2. 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, the inclusion of others' works or results without citation in assignments and reports is also regarded as plagiarism with a 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.
  3. 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.
  4. Q: What are some of the common mistakes made in online and real-time contest?
    A: There are a few common mistakes. Please check out this site for more information.
  5. Q: What does error message 'Restricted Function' mean in online judge?
    A: There is no standard definition of “Restricted Function”. One general accepted guideline is that any code which may threat the system should not be executed. More specifically, any functions which are not needed when solving the problem should not be called. There are several possible reasons: 1. Using file-operating functions which are not allowed; 2. Mis-usage of pointers or malloc(); 3. Using system('pause').
  6. Q: Why can't I pass the judge even though I've passed all of my own test cases on my own computer?
    A: First, it is very common so there is no need to be frustrated. Your test cases may be not good or large enough. Here we provide three suggestions: 1. use array instead of linked list as long as it is possible; 2. declare more space (usually 10 more is enough) for arrays, e.g., declare 1010 in length when the maximum n is 1,000; 3. be aware of boundary cases, e.g., n=0, negative number, null pointer, etc.
  7. Q: Return “not a text file” when submitting the code.
    A1:Delete all the comments in your code.
    A2: You may not set up your account. Set up your account following the instructions of the second tutorial ”Online Judge System” (8th page, Account Preparation).
  8. Q: “compile error in online judge system” but compile successfully in own PC.
    A: use notepad++ to convert the file into UNIX format. 1. Encoding → Convert to ANSI. 2. Edit → EOL Conversion → Unix(LF)
  9. Q: Can not receive the email after submitting successfully.
    A: The system may send the email for you after a while not immediately.
  10. Q: Get wrong answer in the system but get correct answer in local PC.
    A: run the c file in UNIX to check the answer. 1. gcc -o hello hello.c 2. ./hello
  11. Q: What is the meaning of the reply message 'Presentation Error'.
    A1: This may be because of the lack or abuse of '\n'.
    A2: Make sure the return(0) if you define your main function return an integer; This will print a separate line, i.e. a line after your actual output :). From Julius.
  12. Q: Can I declare and initialize variables in the for loop?
    A: Declaring and initializing variables in the for loop is not allowed in the judge.
  13. Q: Tips
    A: Defining the size of the array using a variable is not allowed. You can use a constant instead. Actually, this is not necessary to define a two-dimension array. You can read and output line by line.

Resources

    1. This site is the creator of Matlab. You will be able to obtain much Matlab-related information.
  1. C Programming