| Course code | CSCI2100 |
| Course title | Data Structures 數據結構 |
| Course description | This course introduces the concept of abstract data types and the advantages of data abstraction. 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 樹形等）作出的實踐。更以實例（例如：檢索、排序等）來說明數據抽象化在計算機程序設計上的應用。並討論檢索與排序算法及數據結構之應用。 |
| Unit(s) | 3 |
| Course level | Undergraduate |
| Pre-requisite | CSCI1110 or 1120 or 1130 or 1510 or 1520 or 1530 or 1540 or ESTR1100 or ESTR1002 |
| Exclusion | ESTR2102 or CSCI2520 |
| Semester | 2 |
| Grading basis | Graded |
| Grade Descriptors | A/A-: EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions. B+/B/B-: GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered. C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems. D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems. F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course. |
| Learning outcomes | 1. 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); 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); |
| Assessment (for reference only) |
Essay test or exam: 50% Short answer test or exam: 25% Assignments: 25% |
| Recommended Reading List | 1. Horowitz, Sahni and Freed, Fundamentals of Data Structures in C 2. Weiss, Data Structures and Algorithm Analysis in C++ 3. Goodrich and Tamassia, Data Structures and Algorithms in Java 4. Roberts, Programming Abstractions in C: A Second Course in Computer Science |
| CSCIN programme learning outcomes | Course mapping |
| Upon completion of their studies, students will be able to: | |
| 1. identify, formulate, and solve computer science problems (K/S); | TPM |
| 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); |
TPM |
| 3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V); | |
| 4. communicate effectively (S/V); |
P |
| 5. succeed in research or industry related to computer science (K/S/V); |
P |
| 6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S); | |
| 7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V); | |
| 8. practise high standard of professional ethics (V); | |
| 9. draw on and integrate knowledge from many related areas (K/S/V); |
TP |
| Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured | |