Math 213
Introduction to Discrete Mathematics
Section F1

Instructor: Alexandr V. Kostochka
Office: 234 Illini Hall Phone: (217) 265-8037 (office)
Fax: (217) 333-9576 E-mail: kostochk@math.uiuc.edu
Time and place: 2pm-2:50pm MWF, 147 Altgeld Hall
Final exam: 1:30pm - 4:30pm, Friday, December 16
Office hours: 3-4pm MWF and by appointment

Class Announcements

Topics for the final: 1. Sets, Cartesian product of sets. Set operations and identities. 2. Functions, inverse functions. Algorithms, greedy algorithms. 3. Sorting algorithms: bubble sort, insertion sort, merge sort, tournament sort. 4. Growth of functions, big-Oh notation. 5. Mathematical induction. 6. Sequences and summation. Arithmetic and geometric progressions. 7. Pigeonhole Principle. 8. Placing indistinguishable balls into distinct boxes. 9. The Binomial Theorem and some corollaries. Pascal Identity and Triangle. Vandermonde's identity. 10. Probability for finite sample spaces: elementary properties. 11. Random variables and their expected values. Linearity of expectations. 12. Recurrence relations (Sections 6.1--6.2). 13. Inclusion-Exclusion Principle and its applications (Sections 6.5--6.6). 14. Relations and their properties (Section 7.1). 15. Representing relations (Section 7.3). 16. Equivalence relations (Section 7.5). 17. Graph notions (Sections 8.1, 8.2). 18. Graph isomorphism and representing graphs (Section 8.3). 19. Euler and Hamilton paths and circuits (Section 8.5). 20. The Shortest Path Problem, Dijkstra Algorithm. Traveling Salesman Problem (Section 8.6). 21. Floyd-Warshall algorithm (A handout). 22. Planar graphs: Euler's Formula, Kuratowski's Theorem (Section 8.7). 23. Definitions and properties of trees, characterizations of trees (Section 9.1). 24. Minimum spanning trees: Prim's and Kruskal's algorithms (Section 9.5). 25. Binary search trees. Prefix codes, Huffman coding (Section 9.2). 26. Stable matchings (A handout).

To look at your grades, go to ``www.math.uiuc.edu'', then ``courses'', then ``scores reports''.

You may send comments to: kostochk@math.uiuc.edu

Last changed on December 07, 2005.