# CSCI3160 Design and Analysis of Algorithms

 Course code CSCI3160 Course title Design and Analysis of Algorithms 算法設計及分析 Course description This course introduces the basics of algorithm analysis: correctness and time complexity. Techniques for designing efficient algorithms: greedy method, divide and conquer, and dynamic programming. Fundamental graph algorithms: graph traversals, minimum spanning trees and shortest paths. Introduction to complexity theory: polynomial-time reductions and NP-completeness. 本科介紹算法分析基礎：正確性與時間複雜性。快速算法設計技術：貪婪策略、分治策略、動態規劃。圖算法基礎：圖搜索、最小生成樹、最短路徑。複雜性理論入門：多項式時間變換、NP 完全理論性。 Unit(s) 3 Course level Undergraduate Pre-requisite CSCI2100 or CSCI2520 or ESTR2102, and CSCI2110 or ENGG2440 or ESTR2004 Exclusion ESTR3104 or CSCI3190 Semester 1 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. Understanding of some fundamental algorithms; 2. Ability to desige some simple algorithms; 3. Ability to analyze the correctness and time complexity of some simple algorithms; 4. Ability to construct simple reductions to demonstrate NP-completeness; Assessment (for reference only) Final exam: 50% Mid-term exam: 30% Assignments: 20% Recommended Reading List The recommended reading list/references will be determined by the instructor(s) of the course.

 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); TM 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); T 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