This is challenging course that aims at studying discrete structures relevant to computer science and mathematics. You will learn to reason about discrete objects (e.g. programs) along with giving formal definitions to various concepts. You will study basics of arithmetic, graphs, trees, some known algorithms (e.g. Euclidian algorithm, Dijkstra's algorithm), proofs, induction, finite state machines, logic, counting and probability. An emphasis is placed on proving correctness of algorithms.
1) The concepts of definition, theorem, and proof. 2) Basics of arithmetic. Euclidean algorithm. 3) Basics of graph theory. Directed and undirected graphs. The path problem. Components of graphs. Euler circuits. 4) Trees. Induction on trees. Expression trees. 5) Sets and relations. Operations on sets. Types of relations. Partial orders and equivalence relations. Relational calculus. 6) Induction and correctness of programs. Loop invariants. 7) Spanning trees. Shortest path problem. 8) Propositional logic. 9) Functions. 10) Finite automata. 11) Elements of probability and counting.
There will be 8 assignments with the following due dates: March 12, March 19, March 26, April 9, May 7, May 14, May 21, and May 28. All assignments are due 4pm on the specified days. Submit your assignments through the Student Resource Centre of the Faculty of Science.
Assignments: 32%
Test: 23%
Exam: 45%
The test will be on Week 7, the week just after the break.
Lectures on Discrete Mathematics for Computer Science. Authors: Bakhadyr Khoussainov and Nodira Khoussainova. World Scientific. Singapore. Available at the University bookstore.
Three lectures per week on Mondays (Lecture Theatre 303-G23), Tuesdays (Engineering Block 1, Room 439) and Thursdays (303-G23). All lectures run from 4pm to 5pm.
Lecturer and supervisor: Prof. Bakhadyr Khoussainov, The University of Auckland.There will be 6 classes. Each class will have one tutorial per week. The classes are on Tuesdays (11am-12noon and 2pm-3pm) and Wednesdays (1pm-2pm and 3pm-4pm). For the tutorial classes talk to your tutor. Select the one that suits you the most but we try to distribute the students equally to each class. Here is the contact info for teaching assistants:
Tutor: Dr. Dimitry Berdisnky