Discrete mathematics 1000-711MAD
Counting methods: induction, recursive equation solving, finite sums, asymptotics.
Combinatorial objects: permutations, graphs, trees, words.
Set theory: sets, functions, relations (including orders and equivalence relations), cardinality.
Course coordinators
Type of course
Learning outcomes
A student finishing the course:
- can carry out inductive proofs, count objects, calculate finite sums, solve recursive equations, prove properties of Newton's binomial combinatorially;
- understands the concepts of sets, functions, relations and powers of sets, can analyze bijections, determine the cardinality of quotient sets and equivalence classes, knows and can use the Cantor-Bernstein theorem;
- knows basic data structures such as trees and graphs;
- can apply the above knowledge and skills to analyze the complexity of simple algorithms and study the size of data, understands the need for such analysis.
Assessment criteria
Admission to the exam based on homeworks, final assessment based on tests and writing exam.
Bibliography
Kenneth A. Ross, Charles R. B. Wright, Discrete Mathematics, Prentice Hall, 1988
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994