20 Points This paper introduces computer science and mathematics students to the formal theory of computation, as well as some important ideas in discrete mathematics of relevance to computer science and IT.
In the discrete mathematics half of the paper, a formal approach to logic is introduced: the basic connectives, wellformed formulas, truth tables, laws of equivalence, testing validity of logical arguments, plus an introduction to predicates and quantifiers. Also covered are modular arithmetic and its applications (to coding and cryptography for example) as well as an introduction to binary relations and directed graphs (connectivity and Warshall’s algorithm).
The other half of the paper deals with the theory of computation. Topics include: finite state automata and regular languages, Kleene’s theorem, Turing machines and the Halting problem, formal grammars and the Chomsky hierarchy. There is laboratory work in which students design Turing Machines. Students who pass this paper will understand the differences between data types such as sets, functions, relations, graphs and trees. They will be able to explain several common graph and tree algorithms. They will be able to manipulate propositional logic formulae and explain the limitations of computation systems such as finite state automata and Turing machines.
MATH102.
COMP140, COMP240, MATH258.
B Semester
http://www.math.waikato.ac.nz/~stokes/COMP235
Three to four lectures per week, a weekly tutorial and up to five hours in total of supervised laboratory work.
Official Timetable Information
Internal assessment/final examination ratio 1:1 or 0:1, whichever works in your favour.
This paper is compulsory for a major in Computer Science, except for the Applied Computing specialisation.
Academic Integrity Follow this link for Academic Integrity information and this link for detailed explanation of How to prevent plagiarism in Computer Science assessment items. Performance Impairment Follow this link for information on Performance Impairment. Student Concerns and Complaints Follow this link for Student Concerns and Complaints information. Application for Extension Follow this link for information on applying for an Extension.
Review of Grade Follow this link for information on applying for a Review of Grade.
University Regulations Your attention is drawn to the following regulations and policies, which are published in the University Calendar:
