| Course code | CSCI5160 |
| Course title | Advanced Algorithms 高級算法 |
| Course description | This course will study the design and analysis of exact and approximation algorithms using advanced techniques such as combinatorial methods, probabilistic methods, linear programming, semidefinite programming, and spectral methods. 本科將通過組合方法、概率方法、綫性規劃、半正定規劃以及譜方法等新技術對精確算法和近似算法的設計及分析進行研究。 |
| Unit(s) | 3 |
| Course level | Postgraduate |
| Exclusion | ENGG5102 |
| 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. Apply algorithmic techniques to solve problems in computer science 2. Understand one advanced algorithmic technique in depth, including the technical knowledge and the various applications 3. See the connections between the course content and their own research area |
| Assessment (for reference only) |
Essays：50% Others：50% |
| Recommended Reading List | 1. Combinatorial Optimization: Polyhedral and Efficiency, by Alexander Schrijver, Springer, 2003. 2. The Design of Approximation Algorithms, by David Williamson and David Shmoys, Cambridge University Press, 2010. 3. Semidefinite programs and combinatorial optimization, by L. Lovász, in: Recent Advances in Algorithms and Combinatorics (ed. B.A. Reed, C.L. Linhares-Sales), CMS Books Math./Ouvrages Math. SMC 11, Springer, New York (2003), 137-194. 4. Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995. 5. Lecture notes on “spectral graph theory”, by Daniel Spielman, Yale University, 2012. |
| 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); | T |
| 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); | T |
| 4. communicate effectively (S/V); |
|
| 5. succeed in research or industry related to computer science (K/S/V); |
T |
| 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); | TP |
| 8. practise high standard of professional ethics (V); | |
| 9. draw on and integrate knowledge from many related areas (K/S/V); |
T |
| Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured | |