Navigation

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== CSCI2100 Data Structures ======
===== Discussion forum =====
[[https://edx.keep.edu.hk/courses/course-v1:cuhk+csci2100a+2015_2/discussion/forum|**Here**]] is the link to our **discussion forum**.

===== Merits =====
Congratulations again to these students who did an incredibly excellent job on this year's programming midterm!

From left to right: YIU Man Chi (2nd Runner-up), HO Kwun Ting (Most Precise Coder), LI Danli (Excellent Female Coder), CHEN Yu Zhen (Best Female Coder), WONG Ka Wing (3rd Runner-up), Prof. King, SU Jinhai (1st Runner-up), LAU Chi Yung (Champion).

{{:teaching:csci2100:awards.jpg?720x540|}}

===== Breaking News =====
  - <hi yellow>**5 May 2016**</hi>. Final exam papers are now ready to check, please come to Rm1024, SHB for checking before 20 May 2016. 
  - <hi yellow>**26 April 2016**</hi>. Written assignment sample solutions are out, along with some other related problems in same topics. {{:teaching:csci2100:hw5_sample_sol.pdf|WA#4 solution}} {{:teaching:csci2100:hw4_sample_sol.pdf|WA#5 solution}}
  - <hi yellow>**17 April 2016**</hi>. <html><font color="red"> <b>EMERGENCY</b></font></html> Due to the breakdown of SPARC workstations, we temporarily postpone the submission deadline of PA#5 for one day, i.e., to 23:59:59 April 18, 2016. You can try submissions tomorrow when the server is up, hopefully before noon.
  - <hi yellow>**12 April 2016**</hi>. <html><font color="red"> <b>IMPORTANT</b></font></html> This is a kind remainder: there is no class today and no tutorial tomorrow.
  - <hi yellow>**11 April 2016**</hi>. The Online Judge System will be open for PA #5 12p.m. this afternoon. The reward vectors for Problem 1&2&3&4 are (3,3,3,2,1,1,0), (3,3,3,1,1,0,0), (3,3,3,2,1,1,0) and (3,3,3,1,1,0,0), respectively. 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 [[http://course.cse.cuhk.edu.hk/~csci2100a/hw5-result.html|ranking]] page.
  - <hi yellow>**05 April 2016**</hi>. Some students asked us which head files can be used in the programming midterm. You can all std header file and string.h.
  - <hi yellow>**05 April 2016**</hi>. <html><font color="red"> <b>IMPORTANT</b></font></html> We have sent an email to all students who will attend the early session (1:30 pm - 5:00 pm, April 8) of programming midterm. If you already made a reservation and did not receive the email, please contact TAs and Prof. King as soon as possible. There are still 5 quotas left.
  - <hi yellow>**05 April 2016**</hi>. Due to conflict with programming midterm, PA#5's submission starting date has been postponed to Monday, April 11.
  - <hi yellow>**05 April 2016**</hi>. There is a mistake in the announcement!  The tutorial for the programming midterm examination is not today, but will be tomorrow, Wednesday from 5:30 pm to 6:30 pm in ERB 407.
  - <hi yellow>**01 April 2016**</hi>. PA#5 was out. The scores of Programming Assignment are released. The link is {{:teaching:csci2100:pa_score_v5.xlsx|here}}. Please check whether there are mistakes of your scores. If so, please send email to TAs. We will check the log asap.
  - <hi yellow>**31 March 2016**</hi>. Last year's programming midterm exam paper can be found {{:teaching:csci2100:programming_midterm_2014.pdf|here}}. Sample code of several data structures and functions can be downloaded {{:teaching:csci2100:sample_code_in_weiss_s.zip|here}}.
  - <hi yellow>**21 March 2016**</hi>. Written assignment sample solutions are out. {{:teaching:csci2100:wa1sol.pdf|}}{{:teaching:csci2100:wa2sol.pdf|}}{{:teaching:csci2100:wa3sol.pdf|}}
  - <hi yellow>**17 March 2016**</hi>. The Online Judge System will be open for PA #4 12a.m. tonight. The reward vectors for Problem 1&2&3&4 are (3,3,3,2,1,1,0), (2,2,2,1,1,0,0), (3,3,3,2,1,1,0) and (2,2,2,1,1,0,0), respectively. Remember to submit each problem twice to get partial scores. After submitting the code, you can check your scores at the [[http://course.cse.cuhk.edu.hk/~csci2100a/hw4-result.html|ranking]] page.
  - <hi yellow>**14 March 2016**</hi>.  {{https://www.dropbox.com/s/k1hiato01u2h4t2/CSCI2100-00-Announcements%2020160314.pdf?dl=0|Announcements}}
  - <hi yellow>**14 March 2016**</hi>. For Exercise 5.10 of Programming Assignment 4. There will be at most 100 words in the heap, i.e. the capacity of the heap is 100. We have updated the specification of Exercise 5.10 in the problem pool.
  - <hi yellow>**14 March 2016**</hi>. The due date of WA4 has been postponed to April 1st, Friday.
  - <hi yellow>**14 March 2016**</hi>. <html><font color="red"> <b>IMPORTANT</b></font></html> According to the feedback from your Evaluation Questionnaire, some students want to get partial marks for passing some of test cases. So, for each problem, we split the test cases into two parts, an easy one and a difficult one. You should submit the code for one question twice, e.g. for problem 4.17, you should enter the command 'submit 1 417.c' and 'submit 2 417.c'.
  - <hi yellow>**12 March 2016**</hi>.  Since there were some incidents about the PA last week. The scores of Programming Assignment are released. The link is {{:teaching:csci2100:pa_score_v4.xlsx|here}}. Please check whether there are mistakes of your scores. If so, please send emails to TAs. We will check the log asap.
  - <hi yellow>**05 March 2016**</hi>. <html><font color="red"> <b>EMERGENCY</b></font></html> The online judge system is fixed. You can continue to submit. For those who did multiple (>1) submissions for the same problem during judge was down (email with "Problem ID doesn't exist"), please report to TAs by email with exact number of extra submissions and a screenshot of email for proof if your final score is affected. We will give 5 points back for each extra submissions you made if you finally pass the corresponding problem (100 maximum). We are truly sorry for any inconvenience caused. 
  - <hi yellow>**05 March 2016**</hi>. <html><font color="red"> <b>EMERGENCY</b></font></html> The online judge system is down from about 3:00 pm today. Please stop submitting until further notice. We will try to fix the issue as soon as possible. For those who already submitted, your submission will be judged later.
  - <hi yellow>**03 March 2016**</hi>. The Online Judge System will be open for PA #3 12a.m. tonight. The reward vectors for Problem 1&2&3 are (5,5,4,3,2,1,0), (5,5,4,3,2,1,0) and (3,2,1,0,0,0,0), respectively. 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 [[http://course.cse.cuhk.edu.hk/~csci2100a/hw3-result.html|ranking]] page.
  - <hi yellow>**02 March 2016**</hi>. Since some students are confuse about the buildHeap algorithm, I have updated P.23 to P.27 of the tutorial notes again.
  - <hi yellow>**29 February 2016**</hi>. For tutorial notes 7, I am sorry that I have made a mistake on P.27. I have fixed it and updated the tutorial notes. I have also upload the supplementary file for the proof of running time of buildHeap algorithm.
  - <hi yellow>**29 February 2016**</hi>. FAQ for written assignment 3. For exercise 5.2, you need to write down the result of performing three Delete_Min operations in the heap of **problem 1** and **problem 2** of the previous exercise.
  - <hi yellow>**29 February 2016**</hi>. We have updated the schedule of the written mid-term and programming mid-term. Please check. In the week of 22 March, we will be holding a Q&A session, and we will announce the details very soon.
  - <hi yellow>**26 February 2016**</hi>. PA#3 is out.
  - <hi yellow>**22 February 2016**</hi>. WA#3 is out. For WA#2, We do not receive submissions from the following students: 1155062731, 1155064367, 1155063091, 1155067968, 1155029046, 1155063232, 1155062004, 1155068081, and 1155049971. Two of them did not write their name on the paper. If you have submitted it, please contact TAs as soon as possible.
  - <hi yellow>**18 February 2016**</hi>. The Online Judge System will be open for PA #2 12a.m. tonight. The reward vectors for Problem 1&2&3 are (5,4,3,2,2,1,0), (5,4,3,2,2,1,0) and (3,2,1,0,0,0,0), respectively. For example, if your code files for problem 2.3 is "23.c", for problem 2.16 is "216.c" and for problem 2.19 is "219.c" , then the submit commands are "submit 1 23.c", "submit 2 216.c" and "submit 3 219.c", respectively. After submitting the code, you can check your scores at the [[http://course.cse.cuhk.edu.hk/~csci2100a/hw2-result.html|ranking]] page.
  - <hi yellow>**15 February 2016**</hi>. The lecture video playlist on Trees is available [[https://www.youtube.com/watch?v=FLhbctR_c88&list=PLeWEsZy-mvdsEq6vqBvGdm4VqWBqycS3t&index=2|here]].  Please watch them this week since I plan to have a simple quiz on these topics next Monday, 22 February.
  - <hi yellow>**15 February 2016**</hi>. Since many students are confused about exercise 1.6 of written assignment 2, we are going to relax the requirements of this question. When you are asked to give the precise f(n) with n being the input, you can answer in either one of following ways.
    - Give the value of x after the termination of the algorithm, the initial value of x is 0.
    - Give the running time of the algorithm. Each assignment operation, arithmetic operation, and comparison operation cost 1 unit of time. Reminder: when calculating the running time of a “for” statement, you need to consider all the operations it performs.
We apologize that this question is not clearly written, even one of our TAs, Ken, got confused. This question actually intends to ask students to give the final value of x.
  - <hi yellow>**5 February 2016**</hi>. We do not receive written assignments of the following student: 1155068081. If you have submitted it, please contact TAs as soon as possible.
  - <hi yellow>**5 February 2016**</hi>. Programming assignment 2 is out. There are two compulsory problems and one extra problem (very difficult) for bonus.
  - <hi yellow>**5 February 2016**</hi>. Dear students, we will **still have** tutorials in the week **after** the Lunar New Year Break. Wish you Happy Chinese New Year.
  - <hi yellow>**5 February 2016**</hi>. Don't forget to check the "**Receive updates**" check-box in our discussion forum, so that you will receive an email digest once a day notifying you about new, unread activity from posts you are following. If you cannot find the check-box, you can refer to the screenshot [[https://www.dropbox.com/s/ylx01dfk5kgl05a/receiveUpdate.png?dl=0|here]].
  - <hi yellow>**2 February 2016**</hi>. We will be running a discussion forum in the KEEP Open Edx to encourage peer learning. To participate in the discussion forum, you need to register a KEEP account so that we can add you to the Data Structure course in KEEP Open Edx. The following are the instructions.
    - Sign up a KEEP account at https://account.keep.edu.hk/account/signup.
    - Login in https://keep.edu.hk/ with your KEEP account.
    - Visit https://account.keep.edu.hk/account/profile, click "My Institution" and then associate your CUHK identity to the KEEP account.
    - Visit https://edx.keep.edu.hk/courses/course-v1:cuhk+csci2100a+2015_2/about, click the "Enrol" button, then you will be enrolled into the course.
    - Click "Discussion" to enter the discussion forum.
    - Check the "**Receive updates**" check-box, so that you will receive an email digest once a day notifying you about new, unread activity from posts you are following.
  - <hi yellow>**1 February 2016**</hi>. FAQ for written assignment 2. For problem 1.6 (1), (3), and (5), some students asked us what is meant by write down the f(n) and the big-O notation for each "expression". It means that you need to write down the f(n) and the big-O notation for each "question". For problem 1.8 (3), some students asked us what is the difference between "for-next loop set-up" and "each loop". The difference is that, in "for-next loop set-up", we need to initialise the variable i, while in "each loop", we don't need to initialise i anymore.
  - <hi yellow>**29 January 2016**</hi>. Written assignment 2 is out. The deadline is 5:00 pm, Feb 19, 2016.
  - <hi yellow>**29 January 2016**</hi>. The Online Judge System is open for PA #1. After submitting the code, you can check your scores at the [[http://course.cse.cuhk.edu.hk/~csci2100a/hw1-result.html|ranking]] page.
  - <hi yellow>**26 January 2016**</hi>. Corrections to WA #1 1.3(3): Since this problem seems a little bit difficult, we want to simplify it by defining <hi yellow>**a=2, b=1 and c=2**</hi>. If you need more time to finish the homework, you can turn it in before 5:00 pm, Mon, Feb 1, 2016.
  - <hi yellow>**26 January 2016**</hi>. The assignment box for written assignment is located on the 10th floor of SHB. You can refer to the precise location [[https://www.cse.cuhk.edu.hk/irwin.king/_media/teaching/csci2100/box_location.jpg|here]].
  - <hi yellow>**25 January 2016**</hi>. As for the score of Asg#0, some students submitted correct code and also received "Accepted" email but still had 0 mark on the [[http://course.cse.cuhk.edu.hk/~csci2100a/hw0-result.html|ranking page]]. This is because the score system of assignment 0 has expired. But you can test the system by submitting Assign 0 throughout the whole semester. Asg#0 is only for you to test the judge system. The score of Asg#0 is not concluded in the final grade.
  - <hi yellow>**22 January 2016**</hi>.  The first Programming Assignment has been released. You can submit the code to online judge system from 6:00 pm, Friday, Jan 29, 2016 to 6:00 pm, Friday, Feb 5, 2016.  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.21 is "121.c" and for problem 1.22 is "122.c", then the submit commands are "submit 1 121.c" and "submit 2 122.c", respectively.
  - <hi yellow>**20 January 2016**</hi>.  Video instructions for CSE UNIX server have been updated. You can get the links from our [[https://www.cse.cuhk.edu.hk/irwin.king/teaching/csci2100/2015/tutorial|tutorial]] page. 
  - <hi yellow>**18 January 2016**</hi>.  Tutorial 2 has been modified in the [[https://www.cse.cuhk.edu.hk/irwin.king/teaching/csci2100/2015/tutorial|tutorial]] page. Written Assignment 1 only contains 1.1 (4), (6), and (12); 1.3 (3) and (9); 1.4 (1), (3) and (5) of {{:teaching:csci2100:hw1.19.pdf|the problem pool}}. The whole problem pool is for your reference to exercise. Programming Assignment 1 will be released this Friday. Please make sure you are familiar with the CSE UNIX environment.
  - <hi yellow>**11 January 2016**</hi>.  The website is now available!

===== Spring 2015-2016 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  |  M7 2:30 pm - 3:15pm  |   W10 5:30 pm - 6:15 pm  |
^ Venue    |  LSK LT3  |  LSK LT3  |  LSK LT3  |  ERB 407  |

<html><font color="red"> <b>The Golden Rule of CSCI2100: </b></font></html> 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 [{{:teaching:csci2100:staffstudentexpectations.pdf|here}}].



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

[[https://www.udacity.com/courses/ud595|Linux Command Line Basics]]

====== 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樹形等)作出的實踐。更以實例(例如：檢索、排序等)來說明數據抽象化在計算機程序設計上的應用。並討論檢索與排序算法及數據結構之應用。

===== 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), B-tree, 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  ^  Tutor 4  |
^ Name |  [[:home|Irwin King]]  |  Jiani Zhang  |  Ken Chan  |  Tong Zhao  |  Hongyi Zhang  |
^ Email |  king AT cse.cuhk.edu.hk  |  jnzhang AT cse.cuhk.edu.hk  |  hpchan AT cse.cuhk.edu.hk  |  tzhao AT cse.cuhk.edu.hk  |  hyzhang AT cse.cuhk.edu.hk  |
^ Office   |  SHB 908  |  SHB 1024  |  SHB 1024  |  SHB1024  |  SHB 1024  |
^ Telephone   |   3943 8398   |     |     |    |  |
^ Office Hour(s)   |   * By appointment  |  Friday\\ 1:00 pm - 2:00 pm  |  Tuesday\\ 11:00 am - 12:00 pm  |  Thursday\\ 3:00 pm - 4:00 pm  |  Thursday\\ 3:00 pm - 4:00 pm  |
Note: This class will be taught in<html> <font color="red">English</font></html>. 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 [[http://www.adobe.com/prodindex/acrobat/readstep.html#reader | Acrobat Reader]] from Adobe.

^ Week   ^    Date     ^  Lecture Topics\\ and Notes  ^  Tutorial Topics  ^  Homework Assignments \\  and Events  ^  Resources  ^   
|  1  |  11/1  |  **Introduction**\\  \\ {{https://www.dropbox.com/s/nct2cw5wkjub1ge/CSCI2100-01-Introduction.pdf?dl=0|Introduction}}  \\ {{https://www.dropbox.com/s/ddj6lexdcv40pjn/KEEPAttendance%203-Step%20Slides.pdf?dl=0|KEEPAttendance}}  |  Introduction of C  |  * **WA #1** {{:teaching:csci2100:hw_1.15.pdf|hw_1.19.pdf}}\\ <hi yellow>**Due on or before 5:00 pm, Mon, Feb 1, 2016** </hi>  \\ * <hi lightblue>**1.1 (4), (6), and (12); 1.3 (3) and (9); 1.4 (1), (3) and (5) {{:teaching:csci2100:wa1sol.pdf|WA#1 Solutions}}** </hi>  |  * Chapter 1 of Weiss'97\\ * Chapter 1 of Cormen et al.'90 \\   |
|  2  |  18/1  |  **Algorithm Analysis**\\    \\ {{https://www.dropbox.com/s/bxq0iqmzmb982al/CSCI2100-02-Analysis.pdf?dl=0|Analysis (updated)}}  |  Online Judge System  |  * **PA #1** {{:teaching:csci2100:hw_1.21.pdf|hw_1.21.pdf}}  \\  <hi yellow>**From 6:00 pm, Friday, Jan 29, 2016 to 6:00 pm, Friday, Feb 5, 2016** </hi>  \\  * <hi lightblue>**1.21(Problem 1){{:teaching:csci2100:121.zip|sample solution+test cases}};1.22(Problem 2){{:teaching:csci2100:122.zip|sample solution+test cases (in courtesy of Mr. SU, Jinhai)}}** </hi>  |  * Chapter 2 of Weiss'97\\   |
|  3  |  25/1  |  1. **Algorithm Analysis**\\ 2. **Lists, Stacks and Queues**\\  \\ {{https://www.dropbox.com/s/k8yldyhfxpig3gg/CSCI2100-03-LSQ.pdf?dl=0|LSQ}}   |  I\O issues  |  * **WA #2** {{:teaching:csci2100:hw_1.21.pdf|hw_1.21.pdf}}\\ <hi yellow>**Due on or before 5:00 pm, Fri, Feb 19, 2016** </hi>  \\ * <hi lightblue>**1.6 (1), (3), and (5); 1.8 (3); 1.9 (2) and (4) {{:teaching:csci2100:wa2sol.pdf|WA#2 Solutions}}** </hi>  |  * Chapter 2 of Weiss'97\\ * Chapter 3 of Weiss'97\\   |
|  4  |  1/2  |  1. **Lists, Stacks and Queues**\\   2. **Tree Data Structures and Algorithms**\\ \\  {{https://www.dropbox.com/s/u766vofatishz43/CSCI2100-04-Trees.pdf?dl=0|Trees}}  |  Lists, Stacks and Queues in C  |  * **PA #2** {{:teaching:csci2100:hw_1.22b.pdf|hw_1.22.pdf}}  \\  <hi yellow>**From 12:00 am, Friday, Feb 19, 2016 to 23:59 pm, Thursday, Feb 25, 2016** </hi>  \\  * <hi lightblue>**2.3(Problem 1){{:teaching:csci2100:23.zip|sample solution+test cases (in courtesy of Mr. SU, Jinhai)}};2.16(Problem 2){{:teaching:csci2100:216.zip|sample solution+test cases}};2.19(Problem 3 Bonus)** </hi>  |  * Chapter 3 of Weiss'97\\   |
|  5  |  8/2  |  <color red>**Lunar New Year Break**</color>\\   |    |    |    |
|  6  |  15/2  |  **Tree Data Structures and Algorithms**  \\   \\  The lecture video playlist is available [[https://www.youtube.com/watch?v=FLhbctR_c88&list=PLeWEsZy-mvdsEq6vqBvGdm4VqWBqycS3t&index=2|here]].   |  Linux commands and vim  |  * **WA #3** {{:teaching:csci2100:hw_1.22b.pdf|hw_1.22.pdf}}\\ <hi yellow>**Due on or before 5:00 pm, Fri, March 04, 2016** </hi>  \\ * <hi lightblue>**3.3 (2) (3); 3.10; 3.11; 3.18; 5.1; 5.2; 5.4 {{:teaching:csci2100:wa3sol.pdf|WA#3 Solutions}}** </hi>  |  * Chapter 4 of Weiss'97\\   |
|  7  |  22/2  |  1. **Tree Data Structures and Algorithms**   \\  2. **Heaps**  \\  \\  {{https://www.dropbox.com/s/604irl5ub9yero0/CSCI2100-06-Heaps.pdf?dl=0|Heaps}}  |  Binary and AVL Trees in C  |  * **PA #3** {{:teaching:csci2100:hw_1.23.pdf|hw_1.23.pdf}}  \\  <hi yellow>**From 12:00 am, Friday, March 4, 2016 to 23:59 pm, Thursday, March 10, 2016** </hi>  \\  * <hi lightblue>**3.24(Problem 1) {{:teaching:csci2100:324.zip|sample solution+test cases (in courtesy of Mr. SU, Jinhai)}};3.32(Problem 2);3.36(Problem 3 Bonus)** </hi>  |  * Chapter 4 of Weiss'97\\   |
|  8  |  29/2  |  1. **Heaps**  \\  2. **Hash Functions**  \\  \\  {{https://www.dropbox.com/s/0aei3vaftjuqh2x/CSCI2100-05-Hash.pdf?dl=0|Hashing}}  |  Heap in C  |  * **WA #4** {{:teaching:csci2100:hw_1.23.pdf|hw_1.23.pdf}}\\ <hi yellow>**Due on or before 5:00 pm, Fri, April 1, 2016** </hi>  \\ * <hi lightblue>**4.1; 4.14; 6.1; 6.2; 6.6(2)** </hi>  |  * Chapter 6 of Weiss'97\\ * Chapter 5 of Weiss'97\\   |
|  9  |  7/3  |  1. **Hash Functions**  \\  2.  **Sorting Algorithm**  \\ \\ {{https://www.dropbox.com/s/2nie5d2qeyv5onu/CSCI2100-07-Sorting.pdf?dl=0|Sorting}}  |  Hashing in C  |  * **PA #4** {{:teaching:csci2100:hw124.pdf|hw_1.24.pdf}}  \\  <hi yellow>**From 12:00 am, Friday, Mar 18, 2016 to 23:59 pm, Thursday, Mar 24, 2016** </hi> \\  * <hi lightblue>**4.17(Problem 1 easy testcases);4.17(Problem 2 tough testcases){{:teaching:csci2100:p2.zip|sample solution+test cases (in courtesy of Mr. SU, Jinhai)}};5.10(Problem 3 easy testcases);5.10(Problem 4 tough testcases) {{:teaching:csci2100:p4.zip|sample solution+test cases (in courtesy of Mr. SU, Jinhai)}} ** </hi>  |  * Chapter 5 of Weiss'97\\   |
|  10  |  14/3  |  **Sorting Algorithms**  \\   \\  \\ {{https://www.dropbox.com/s/k1hiato01u2h4t2/CSCI2100-00-Announcements%2020160314.pdf?dl=0|Announcements}}  \\  {{https://www.dropbox.com/s/7fpnhyc9qsr20xg/CSCI2100-Quicksort_Demo.pdf?dl=0|Quicksort Demo}}  |  Pointers in C  |  No assignment  |  * Chapter 7 of Weiss'97\\   |
|  11  |  21/3  |  **Open Forum**\\ \\  **Written Midterm Exam**\\   |  No Tutorials  |  No assignment  |  * Chapter 7 of Weiss'97\\   |
|  12  |  28/3  |  1.  <color red>**Easter Break**</color>\\   \\  2.  **Sorting Algorithms**  \\  3.  **Graph Data Structures and Algorithms**  \\  \\ {{https://www.dropbox.com/s/eefw0v43sblpvph/CSCI2100-08-Graphs.pdf?dl=0|Graphs}}  \\  {{https://www.dropbox.com/s/kd3r0fkv8d9qtds/CSCI2100-00-Announcements20160329.pdf?dl=0|Announcements}}   |  Programming Exam Preview  |  * **PA #5** {{:teaching:csci2100:hw124.pdf|hw_1.24.pdf}}  \\  <hi yellow>**From 12:00 am, Monday, Apr 11, 2016 to 23:59 pm, Sunday, Apr 17, 2016** </hi> \\  * <hi lightblue>**1.19(Problem 1 easy testcases);1.19(Problem 2 tough testcases);6.11(Problem 3 easy testcases);6.11(Problem 4 tough testcases)** </hi>  |    |
|  13  |  4/4  |  1. <color red>**Ching Ming Festival**</color>\\  \\  2.  **Graph Data Structures and Algorithms**  \\  3. **Programming Midterm Exam** \\    |  Programming Exam Preview  |  * **WA #5** {{:teaching:csci2100:hw124.pdf|hw_1.24.pdf}}\\ <hi yellow>**Due on or before 5:00 pm, Fri, April 22, 2016** </hi>  \\ * <hi lightblue>**7.1; 7.3; 7.4; 7.5 (1)** </hi>   |    |
|  14  |  11/4  |  **Discussions on Programming Midterm**\\   |  No Tutorial  |  {{:teaching:csci2100:midterm_summary.pdf|Midterm Summary}}  |  * Chapter 9 of Weiss'97\\   |
|  15  |  18/4  |  1. **Graph Data Structures and Algorithms**\\ 2. **Course Summary**\\  \\ \\ {{https://www.dropbox.com/s/3mbigt0uruv6un0/CSCI2100-09-Final.pdf?dl=0|Final}}  |  Mergesort and Quicksort in C  |    |  * Chapter 9 of Weiss'97\\   |

<box 90% round red | **Tutorial Page**>
  * For detailed tutorial and lab session information, please go to [[:teaching:csci2100:2015:tutorial|Tutorial Page]].
</box>

<box 90% round blue | **Manual Page**>
  * For supplementary material on various topics related with this course, please go to [[:teaching:csci2100:2014:manual|Manual Page]]. Enjoy your Exploration.
</box>

====== Examination Matters ======
===== Examination Schedule =====

|              ^        Time           ^        Venue          ^    Notes    ^
^    Midterm Examination\\ Written    |  March 22, 12:30 pm - 2:15 pm  |  LSK LT5  |  One cheat sheet (A4, both sides) of notes. No calculator.  |
^    Midterm Examination\\ Programming    |  April 8, 6:00 pm - 9:00 pm  |  SHB924  |  Printed out materials only.  |
^    Final Examination    |  April 28, 9:30 am - 11:30 an  |  Multi-purpose Hall, Pommerenke Stud Ctr  |  One cheat sheet (A4, both sides) of notes. No calculator.  |

  * [[http://rgsntl.rgs.cuhk.edu.hk/rws_prd_life/main1.asp|CUHK Registration and Examination]]

===== Programming Midterm Matters =====
  - 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.
  - 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 to 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 afterwards. 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 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.

===== Written Midterm Matters =====
  - The midterm will test your knowledge of the materials up to Homework #3, that will be to include Heaps.
  - Answer all questions using the answer booklet. There will be more available at the venue if needed.
  - You can bring one sheet (A4, both sides) of notes. Calculator is not required. No electronics are allowed.
  - 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%  |

  -Assignments (20%) 
    -Written assignment 
    -Programming assignment 
    -Optional quizs 
    -Late penalty: 10% for each day (no later than 3 days, only applicable for written assignment)
  -Midterms (30%)
    - Written (10%)
    - Programming (20%)
  -Final Examination (50%) 
  -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 ======
  - Pre-requisites
    -- CSCI 1110 or 1130 or its equivalent. (Not for students who have taken CSCI 2520). 

====== Reference Books ======
/*
  - [[http://www.amazon.com/exec/obidos/ASIN/0201498405/qid%3D949475985/sr%3D1-6/002-0319810-4772266|Data Structures and Algorithm Analysis in C]], **Mark Allen Weiss, Addison Wesley, second edition, 1997.**
  - [[http://www.amazon.com/exec/obidos/ASIN/0805316663/ref=sim_books/002-0319810-4772266|Data Structures and Algorithm Analysis in C++]], **Mark Allen Weiss, Addison Wesley, second edition, 1999.**
*/
  - {{amazon>0201498405}} <bibtex>@Book{weissc,
  AUTHOR     = {Weiss, Mark},
  YEAR       = {1997},
  TITLE      = {Data Structures and Algorithm Analysis in C},
  PUBLISHER  = {Addison Wesley},
  address    = {},
  series     = {},
  volume     = {},
  pages      = {},
  month      = {},
  edition    = {},
  keywords   = {},
  summary    = {},
  supersedes = {D-<oldumber>},
  SEMNO      = {D-<newnumber>},
  PUF        = {Bog},
  ID         = {Bog},
  URL      = {http://www.amazon.com/exec/obidos/ASIN/0201498405/qid%3D949475985/sr%3D1-6/002-0319810-4772266}}
</bibtex>
  - {{amazon>0201498405}} <bibtex>@Book{weissc++,
  AUTHOR     = {Weiss, Mark},
  YEAR       = {1999},
  TITLE      = {Data Structures and Algorithm Analysis in C++},
  PUBLISHER  = {Addison Wesley},
  address    = {},
  series     = {},
  volume     = {},
  pages      = {},
  month      = {},
  edition    = {},
  keywords   = {},
  summary    = {},
  supersedes = {D-<oldumber>},
  SEMNO      = {D-<newnumber>},
  PUF        = {Bog},
  ID         = {Bog},
  URL      = {http://www.amazon.com/exec/obidos/ASIN/0805316663/ref=sim_books/002-0319810-4772266}}
</bibtex>
  - {{amazon>0262031418}} <bibtex>@Book{cormen,
  AUTHOR     = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L.},
  YEAR       = {1990},
  TITLE      = {Introduction to Algorithms},
  PUBLISHER  = {The MIT Press},
  address    = {},
  series     = {},
  volume     = {},
  pages      = {},
  month      = {},
  edition    = {},
  keywords   = {},
  summary    = {},
  URL      = {http://www.amazon.com/Introduction-Algorithms-Electrical-Engineering-Computer/dp/0262031418}}
</bibtex>


====== Other Books ======
  - [[http://www.amazon.com/exec/obidos/ASIN/0201000237/qid%3D949476152/sr%3D1-1/002-0319810-4772266|Data Structures and Algorithms]], **Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Addison Wesley, 1983.**
  - [[http://www.amazon.com/exec/obidos/ASIN/067339736X/qid%3D949476404/sr%3D1-1/002-0319810-4772266|Data Structures and Their Algorithms]], **Harry R. Lewis and Larry Denenberg, HarperCollins Publisher, 1991.**
  - [[http://www.amazon.com/exec/obidos/ASIN/0130369977/qid%3D949476491/sr%3D1-2/002-0319810-4772266|Data Structures Using C and C++]], **Aaron M. Tenenbaum, Yedidyah Langsam, and Moshe J. Augenstein, Prentice Hall, 1995. **



====== FAQ ======
  - **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.
  - **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.
  - **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 [[http://www.acm.org/crossroads/xrds7-5/contests.html|this site]] for more information.
  - **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').
  - **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.

====== Resources ======

  -[[http://www.cyberdiem.com/vin/learn.html|Learn C/C++ Today]]
  -[[http://www.awl.com/cseng|Addison Wesley's Computer and Engineering Book Catalog and Programming Codes ]]
  -[[http://www.mathworks.com/|Matlab Homepage]]
    -This site is the creator of Matlab. You will be able to obtain much Matlab-related information. 
  -[[http://www.cse.cuhk.edu.hk/~acmprog|CSE's ACM Programming Contest Homepage]]
  -C Programming 
    -http://www.strath.ac.uk/CC/Courses/OldCcourse/CCourse.html 
    -http://www.cm.cf.ac.uk/Dave/C/CE.html 
    -http://devlib.virtualave.net/dir/files/cguide_3.zip 
  -[[http://pweb.netcom.com/~tjensen/ptr/pointers.htm |Arrays and Pointers]]
  -[[http://gcc.gnu.org/onlinedocs/gcc/|The 'gcc' compiler]] 
  -[[http://sourceware.org/gdb/current/onlinedocs/gdb_toc.html|The 'gdb' debugger]] 
  -[[http://www.gnu.org/software/make/manual/make.html|The 'make' utility]]  
  -[[http://www.redhat.com/develope]]
Navigation

About Us

Publications

Professional Activities

Lab and Projects

Affiliated Labs

Organizations

Current Activities

See Irwin King In

Book Titles

MISC
