Math 213, Section X1, Spring 2006

Midterm Exam 3 Information

General Information

Date/time/location: The exam will be given during the regular class time, Monday, 5/1/2006, 12 pm - 1 pm, in the usual room, 149 Henry.

Exam rules: Closed books/notes, and no calculators.

Exam Content

The exam will be on the material covered in class since the last midterm and through Friday, April 28. The breakdown is as follows:

• Inclusion/exclusion (Sections 6.5 and 6.6): Inclusion/exclusion formula. Applications: sieve of Eratosthenes, derangements (skip the application to counting onto functions, which I didn't cover in class).
• Relations (Sections 7.1, 7.3, 7.5): Definition and representations (set of pairs, directed graph, binary matrix). Reflexive, symmetric, and transitive properties. (You can skip other properties, and also composition of relations (p. 477-479).) Equivalence relations, equivalence classes, representatives. Congruence classes modulo m.
• Graphs (Sections 8.1 - 8.5): The material from these sections covered in class through Friday, 4/28. The list of topics is as follows.
  • Definition of a graph and its variants (simple graph, directed graph, multigraph, pseudograph, directed multigraph). (8.1)
  • Terminology: Vertices and edges. Concepts of adjacent and incident. Degree of a vertex. In-degree and out-degree of a vertex in a directed graph. Sum-of-degrees formula ("handshake theorem"). (8.2)
  • Special graphs: Complete graphs, cycles, wheels. Bipartite graphs, complete bipartite graphs. Regular graphs. (8.2)
  • Representation of graphs: Adjacency matrix (8.3)
  • Isomorphism of graphs. (8.3)
  • Paths and connectedness. (8.4)
  • Euler paths and circuits. Connection with degrees of vertices. (8.5)
  Note that there will be no homework assignment on this chapter, partly because of timing issues, but mainly because the material is not very suitable to hw assignments as most problems simply require knowing appropriate definitions and terminology, which would be easy to look up with the book at hand. By the same token, those problems make for great problems for a closed books/notes exam.