1. 19 April 2015. The last tutorial will be given at 5:30 pm, 20 April in ERB 407.
2. 15 April 2015. IMPORTANT & URGENT The schedule of make-up exam for students who did not solve any problems during programming midterm is out. It will be held between 6:30 pm - 8:00 pm, April 17, Friday, 2015 in SHB 924. We will provide three straightforward problems and you only need to solve one of your choice to pass the exam. The details are sent to your email (s11550XXXXX@mailserv.cuhk.edu.hk). If you have time conflict or other issues, please contact Mr. ZHANG Hongyi or Mr. HUANG Xin as soon as possible. We will try our best to make proper arrangement for you. Thanks.
3. 8 April 2015. 1) The deadline for HW5 is postponed to next Friday, April 17, 2015. 2) The tutorial on April 15 is canceled. The content of tutorial of next Monday will be the same as this Wed, i.e., April 8.
4. 29 March 2015. We've prepared an archive of sample code for almost all the data structures you've learnt by now. Please download it from the syllabus frame. We recommend you print it and bring it to the midterm exam. You can find the original files here. We've combined each data structure into one single file for your convenience.
5. 26 March 2015. In WA4, Problem 6.6(2), note that median of three, we take the median of first, middle and last element as the pivot, then swap the first and pivot, after this, the partition is the same as the code in the lecture notes. The code in lecture notes (Slide 65) will split the array into three parts, left part less or equal to pivot, pivot and right part larger than pivot. Please note that the goal in Slide 66 is not corresponding to the code in Slide 65, the goal should be < =p, p, >p which is corresponding to the code in Slide 65.
6. 26 March 2015. In WA4, Problem 4.14, the right answer should be for ordered list O(N^2), for unordered list O(N). The meaning is that when collision happens, we want to make the chaining list ordered or unordered. So if ordered, we need the do insertion sort in the chaining list, if unordered, we just need to insert at the front. Sorry that the tutor misunderstood the meaning of problem during the tutorial.
7. 26 March 2015. Last year's programming midterm paper is posted on the website for your reference. No answers will be provided though.
8. 25 March 2015. The grading of Written Assignment 3 has been finished. You may retrieve your homework during the tutorial session. You can fetch your homework at Rm 1024 SHB if you do not collect during the tutorial. If you find the sum of score is miscalculated or cannot find your assignment, please contact TA as soon as possible.
9. 23 March 2015. The reward vectors for Problem 1, 2 and 3 are (5,5,4,4,3,2,1), (4,4,3,3,2,2,1) and (4,4,3,3,2,2,1), respectively. You can check the ranking here.
10. 19 March 2015. IMPORTANT Please pay attention that for your ease of reading input, we've changed the input format for Problem 2 (5.12) of programming assignment #4.
11. 10 March 2015. If you want to know the details about your written midterm score, you can come the SHB1024 to check your exam paper during office hour or by appointment. Thanks for the cooperation.
12. 25 February 2015. Information for written midterm examination.
    1. Date: 4 March
    2. Time: 10:35 am to 12:25 pm
    3. Venue:
       1. SWH 2 (117) AU to KIM
       2. YIA LT2 (248) LAI to ZHANG
    4. One A4 sheet (2-sided) of notes allowed
    5. No tutorial this week.
13. 24 February 2015. The reward vectors for Problem 1 and 2 are (3,2,2,1,1) and (6,6,5,5,4), respectively. You can check the ranking here.
14. 9 February 2015. The solutions and sample codes for PA#1,2 have been out. In addition, several FAQ have been added on the course website (keep scrolling down). Please take a look at them.
15. 9 February 2015. The grading of Written Assignment 2 has been finished. You may retrieve your homework during the tutorial session. The left will be put above the homework collection box at 10th Floor, SHB. If you find the sum of score is miscalculated or cannot find your assignment, please contact TA as soon as possible.
16. 6 February 2015. IMPORTANT Started from 9 Feb, 2015 (Mon) the venue of CSCI2100A lecture M12:30-1:15 is changed from SC L2 to ERB LT, Thank you for your attention.
17. 4 February 2015. URGENT Please re-submit your code for Problem 2. Some of the original test cases have exceed the limit of int. We've deleted all those test cases. There will be no penalty for this problem. We are sorry and thank you for understanding.
18. 1 February 2015. The reward vectors for Problem 1, 2, 3 are (6,5,4,3,2,1,0), (5,4,3,2,1,0,0) and (5,5,5,4,3,2,1), respectively. You can check the ranking here.
19. 1 February 2015. IMPORTANT For programming assignment #2, Problem 3 is exactly the same as Problem 2 except for two things: 1. the range of n; 2. the answer will be fit in a signed 64-bit (not 32-bit) integer, which means you should use the type of long long to store it (use %lld in printf()). Please be careful on the time complexity of your algorithm.
20. 27 January 2015. Since It is the first time to use online judge as submission tool, we decide not to count penalty in your final score for Programming Assignment 1. You will get full mark for each accepted problem. Penalty will be considered from next time.
21. 26 January 2015. The grading of Written Assignment 1 has been finished. You may retrieve your homework during the tutorial session. The left will be put above the homework collection box at 10th Floor, SHB. If you find the sum of score is miscalculated or cannot find your assignment, please contact TA as soon as possible.
22. 22 January 2015. IMPORTANT Started from 26 Jan, 2015 (Mon) the venue of CSCI2100A lecture M12:30-1:15 is changed to SC L2.
23. 22 January 2015. The reward vectors for Problem 1 & 2 are (4,3,2,1,0) and (3,2,1,0,0), respectively. You can check the ranking here.
24. 21 January 2015. For those who still do not have CSE UNIX account to submit to programming assignment, you have two ways to retrieve your account info: 1. come to SHB 1024 and find TA; 2. email hyzhang AT cse.cuhk.edu.hk with your name and student ID. If you do not contact TA until tonight, we will send your account and password to your CUHK email (s11550XXXXX@cuhk.edu.hk).
25. 20 January 2015. The slides of Week 2 have been updated. Please download it again. The pdf file for Week 3 on List, Stack, and Queue (LSQ) is also available below now. You are also welcome to watch the videos on “Jill Rides Again”, “ADT”, “List”, “Stack”, and “Queue”.
26. 19 January 2015. Next time when you turn in your written assignment, if you have more than one A4 papers, please remember to staple them together so that it is easy for us to collect. Thanks.
27. 19 January 2015. We will distribute UNIX accounts for all the Non-CSE students on Wednesday (Jan 21)'s lecture. TA will keep all the remaining accounts. Do remember to collect it, otherwise you cannot submit your programming assignments.
28. 6 January 2015. The venue of Tutorial II will be ERB 404.
29. 5 January 2015. Tutorial II has been set up on every Wednesday 3:30 pm - 4:15 pm. The venue is still to be announced. The content of two tutorial sessions will be the same.
30. 1 January 2015. The website is now available!

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

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

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

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

1. Lectures
2. Tutorials
3. Web resources
4. Assignments
5. Examinations

Note: This class will be taught in English. Homework assignments and examinations will be conducted in English.

The pdf files are created in Acrobat XI. Please obtain the correct version of the Acrobat Reader from Adobe.

• CUHK Registration and Examination

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 to the venue 45 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 afterwards. 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 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.

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.

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.

1. Pre-requisites
   1. - CSCI 1110 or 1130 or its equivalent. (Not for students who have taken CSCI 2520).

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.

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.

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.

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?
   A: There are a few common mistakes. Please check out this site for more information.
4. 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').
5. 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.

1. Learn C/C++ Today
2. Addison Wesley's Computer and Engineering Book Catalog and Programming Codes
3. Matlab Homepage
   1. This site is the creator of Matlab. You will be able to obtain much Matlab-related information.
4. CSE's ACM Programming Contest Homepage
5. C Programming
   1. http://www.strath.ac.uk/CC/Courses/OldCcourse/CCourse.html
   2. http://www.cm.cf.ac.uk/Dave/C/CE.html
   3. http://devlib.virtualave.net/dir/files/cguide_3.zip
6. Arrays and Pointers
7. The 'gcc' compiler
8. The 'gdb' debugger
9. The 'make' utility
10. Programming C under Linux, provided by RedHat
11. Sorting Algorithm Animation Demo
12. Analysis of Algorithms Home Page
13. Mathematical Programming Glossary
14. Algorithm Animation Links
15. The Pickle Story