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.
Type of course
Course coordinators
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
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: