To develop programming and problem solving skills, to encourage a thoughtful approach to analysis and design problems, to introduce and familiarise students with logical and mathematical inference. Students learn syntax and semantics of first-order logic and various proof methods. Students should be able to apply this knowledge to specification of algorithms and logic programming. This is a one-unit course.
| Term | Prerequisites | Core For | 1 & 2 | 1B12 | CS2, CSEE2, CSMA2, CSCG2, MACS2 |
Mathematical proofs: Some basic forms of mathematical proof including induction, proof-by-cases, proof-by-contradiction.
Applications of predicate logic: Case studies of using predicate logic in information technology, including relational databases, software engineering, and artificial intelligence.
Automated reasoning: Utility and problems of automated reasoning, Introduction to basics of logic programming - including hand-evaluation of Prolog programs.
Searching and sorting algorithms: Elementary searching - comparing sequential, binary and interpolation search. Binary search trees. Balanced trees. B-trees. Hashing.
Graph algorithms: Depth-first search of undirected and directed graphs. Articulation points. Strongly connected components. Topological sorting of acyclic graphs. Breadth-first search of directed and undirected graphs. Network flow. Ford-Fulkerson method. Euler circuits.
Text algorithms: String searching. File compression including Huffman coding. Crytology including public key cryptosystems.
Analysis of algorithms: Empirical versus theoretical analysis. Algorithmic complexity. O notation. Worst and average cases. Classifications of algorithms. Hierarchies of complexity. Tractable and intractable problems. Sums of series. Simple summation formulae. Use of differentiation to derive more complex sums. Estimating a sum using integration.
Algorithms with loops: Nested loops. Gaussian elimination. Examples in geometric algorithms including Graham Scan.
Recursive algorithms and recurrence relations: First-order recurrence relations. Solving recurrence using the characteristic equation. Change of variable conditional asymptotic notation. Examples of maths algorithms including exponentiation, large multiplication, and Strassen's algorithm for matrix multiplication.
Introduction to model building: Attributes and relations (object view) Metrics, parameters & factors. The model cycle. Factor reduction. Evaluation choices (analytical, physical, simulation etc).
Data reduction: Stochastic vs Deterministic results. Distributions. Measurement errors (Random & Markovian). Summarisation.
Inference: Hypothesis testing. Estimation. Correlation.
| Weighting | No. Exam Questions | No. Courseworks | 85% examination; 15% coursework | TBN | TBN |
R Sedgewick, Algorithms in C++, Addison-Wesley (1992)