CSCI3190 Introduction to Discrete Mathematics and Algorithms

 

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