CSE3305 - Formal methods II

Offered

Clayton First semester 2007 (Day)
Malaysia First semester 2007 (Day)

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.

Assessment

Assignments: 30%; Examination (3 hours): 70%.

Contact hours

Two x 1 hr lecture/week, One x 1 hr tutorial/fortnight

Prerequisites

CSC2030 or CSE2303 and CSC2040 or CSE2304