6 points - Two 1-hour lectures per week - First semester - Clayton - Prerequisites: CSC2030 or CSE2303 and CSC2040 or CSE2304
Objectives On completion of the subject students will have an understanding of elementary information theory and computer simulation techniques, intractability and its practical implications, and will have the ability to prove that simple programs meet their formal specification.
Synopsis Information theory: in particular types of codings, entropy, information rate, communication channels. Shannon's coding theorems. A review of probability theory. Introduction to the simulation of discrete stochastic processes and Monte Carlo methods. Intractable problems: P, NP, and P-Space complexity classes; Cook's theorem and its application to proving NP-completeness. Approximate solutions to intractable problems. Formal specifications and proofs of correctness.
Assessment Examination (3 hours): 60% - Assignments: 40%
Recommended texts
Davis, M and Weyuker E J Computability, complexity, and
languages: Fundamentals of theoretical computer science Academic Press,
1983
Ross S M A course in simulation 2nd edn, Academic Press, 1997
Hopcroft J E and Ullman J D Introduction to automata theory, languages and
computation Addison-Wesley, 1979