| Course code | CSCI3190 |
| Course title | Introduction to Discrete Mathematics and Algorithms 離散數學及算法導論 |
| Course description | This course introduces logic, combinatorics, recurrence relations and graph theory. Design and analysis of algorithms: greedy method, divide and conquer, and dynamic programming. Fundamental algorithms including sorting, graph algorithms, number-theoretic algorithms and numerical algorithms. Introduction to NP-completeness. 本科介紹邏輯，組合學，遞歸關係與圖論。算法之設計與分析：優先策略，分治策略與動態規劃。基本算法包括排序，圖算法，數論算法與數值算法。NP – 完全性。 |
| Unit(s) | 3 |
| Course level | Undergraduate |
| Pre-requisite | CSCI2100 or 2520 or ESTR2102 |
| Exclusion | CSCI3160 or ENGG2440 or ESTR2004 or 3104 |
| 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 | Students will be able to 1. understand the concepts of logic, sets, functions, and graphs; 2. analyze the time complexity of an algorithm; 3. obtain good knowledge of fundamental sorting, graph, number-theoretic, and numerical algorithms; 4. design greedy, divide-and-conquer, and dynamic-programming algorithms to solve new problems; 5. comprehend the concepts of NP-hardness and basic reductions. |
| Assessment (for reference only) |
Final exam: 50% Mid-term exam: 25% Assignments: 25% |
| Recommended Reading List | 1. Discrete Mathematics and Its Applications (5th Ed.), by K.H. Rosen, McGraw Hill. |
| 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); | TP |
| 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); |
T |
| 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); |
|
| 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 | |