TU Wien:Diskrete Mathematik für Informatik VO (Drmota)/Mündliche Prüfung 2016-01-17

What are generating functions?

• Example for coefficients (e.g. choosing balls)
• Multiplication of GF
• Combinatorial Structures
• Demonstrate solving of linear recurrences by self chosen example (Fibonacci)

Planarity?

• Example of planar, non-planar graphs
• Which graphs are not planar? (Kuratowski-Wagner)
• Euler's Polyhedron formula

Grade: 3

---

What can you tell me about Stirling numbers?

• 1st kind, what do they count, explain recurrence
• 2nd kind, what do they count
• What's the OGF of the Stirling numbers of the first kind?

What is a matching?

• In a general graph
• Perfect matching?
• Condition for the existence of a perfect matching? (Marriage Theorem, Dilworth Theorem)

Question withdrawn after explaining this was not part of the lecture in WS14/15

What are finite fields?

• Definiton of field in general
• What's the smallest finite field
• Are there finite fields of arbitrary size? How can we construct them?
• What is peculiar about the multiplicative group of fields? (-> cyclic)

Grade: 1

No proofs were asked, just general knowledge, "open" questions