This is a challenging course that aims at studying discrete structures relevant to  mathematics and computer science.  You will study the basics of arithmetic, graphs, trees, some important algorithms (e.g. Euclidean algorithm), induction, finite automata, logic, counting and probability, and codes.  The course also introduces proof methods, such as direct proof, and  proof by contradiction.

Detailed syllabus:

• Propositional logic. The concepts of definition, theorem, and proof.
• Basics of arithmetic. Euclidean algorithm. Modular arithmetics
• Sets and relations. Operations on sets. Types of relations. Partial orders and equivalence relations.
• Functions. Injective, surjective, bijective functions, composition of functions.
• Induction and recursion. Solving recurrence relations.
• Elements of probability and counting.
• Finite automata.
• Basics of graph theory. Directed and undirected graphs. The path problem. Euler circuits.
• Trees. Spanning trees. Shortest path problem.

Course notes will be provided on Canvas by the lecturers.

These notes give you some idea of what is to come, but please keep in mind that not all material may be covered, and that they will get modified to some extent as we go along (so don't print them at present). For supplementary reading, we recommend

Discrete Mathematics (5th Edition): Kenneth A. Ross, Charles R. Wright.

Teaching staff: 

Mark Wilson, 303-423, mcw@cs.auckland.ac.nz

Meetings before/after lectures and by email appointment.

Tanya  Gvozdeva, 303-467,   t.gvozdeva@auckland.ac.nz

By email appointment.

 Simone Linz, 303S-481, s.linz@auckland.ac.nz, open-door policy.

Course coordinator:

André Nies, 303-421,  andre@cs.auckland.ac.nz

Office hour: by email appointment

Tutor:

Samin Aref,   sare618@aucklanduni.ac.nz

Office hour (February-May): Thursdays 10-11, Room 476, Bldg 303S

Tutorial times and locations:

We have set up Piazza for this course. The main purpose of Piazza is for you to interact with other students in the course. The tutor will monitor Piazza and help if necessary. Of course, do not post any solutions!

Information regarding university policies and technical support: