| Course code | CSCI5320 |
| Course title | Topics in Graph Algorithms 圖算法專題 |
| Course description | This course will discuss graph theory and graph algorithms with emphasis on the algorithmic aspects of graph theory. The course will cover classical topics such as search techniques, connectivity, colouring, matching and covering, network flows, planarity, traversability, perfect graphs, and NP-completeness of graph problems. The course will also discuss FPT algorithms for solving graph problems. 本科討論圖論與圖論算法。內容包括經典課題之搜索技術，連通性，著色，匹配與覆蓋，網絡流，平面圖，周游性，完美圖，以及圖論問題的NP－完全性。本科也討論解決圖問題的FPT演算法。 |
| Unit(s) | 3 |
| Course level | Postgraduate |
| Prerequisite | CSCI3160 |
| Semester | 1 or 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 | At the end of the course of studies, students will have acquired the ability to 1. use some fundamental graph algorithms to solve other graph problems, 2. establish NP-completeness of graph problems, and 3. use various tools to design FPT algorithms to solve NP-complete graph problems in practice. |
| Assessment (for reference only) |
|
| Recommended Reading List | 1. D. West, Introduction to Graph Theory, Prentice Hall, 2001. 2. M. Ashraf Iqbal, Graph Theory & Algorithms, 2010. 3. R.G. Downey and M.R. Fellows, Parameterized Complexity, Springer, 1997. 4. M.R, Garey, and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979. |
| 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); | |
| 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); |
|
| 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); |
|
| 5. succeed in research or industry related to computer science (K/S/V); |
|
| 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); |
|
| Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured | |