| Lecture I | Lecture II | Tutorial I | Tutorial II | |
|---|---|---|---|---|
| Time | Tue, 12:30 pm - 1:15 pm | Wed, 11:30 am - 1:15 pm | Wed, 5:30 pm - 6:15pm | Thur, 5:30 pm - 6:15 pm |
| Venue | ERB LT | ERB LT | ERB 407 | LHC 103 |
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.
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 language: 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
Grade Assessment Scheme
- Assignments (20%)
- Written assignment
- Programming assignment
- Optional quizzes
- Late penalty: 10% for each day (no later than 3 days, only applicable for written assignment)
- Midterms (50%)
- Written (20%)
- Programming (30%)
- Final Examination (30%)
- Extra Credit
- Students from Elite Stream must complete all the bonus questions.
- Other students will receive extra credits if they complete the bonus questions.
Required Background
- Pre-requisites
- CSCI 1110 or 1130 or its equivalent. (Not for students who have taken CSCI 2520).
Reference Books
- Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, 3-rd Edition, The MIT Press, 2009.
- Mark Weiss, Data Structures and Algorithm Analysis in C, 2-nd Edition, Addison Wesley, 1997.
FAQ
-
Q: What is the 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 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 generally accepted guideline is that any code which may threaten 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
-
-
This site is the creator of Matlab. You will be able to obtain much Matlab-related information.
-
-
C Programming