Math 340 Discrete Mathematics	Home   Homework   Syllabus
Instructor: Martha Yip Email: myip [at sign] math.upenn.edu Office: DRL 3N4C Office Hours: Tuesdays 4:30pm--5:30pm, Wednesdays 3:00pm--4:00pm Lecture: TR 3:00pm -- 4:20pm DRL 3C4 Midterm 1: Thursday October 6 Midterm 2: Thursday November 10 Final: Friday December 16, 12:00pm -- 2:00pm DRL 2C6

Class Blog + Announcements

Exam week office hours: Wednesday and Thursday 2:00pm -- 3:00pm. These two hours are dedicated to students in Math340 only; ie. no questions about matrices allowed, unless it's about adjacency matrices. The final exam is cumulative, and covers all sections and materials for which homework has been assigned. You are allowed to bring one sheet of notes, 8.5"x11", double-sided. Calculators are not allowed.

[08-12-11] Covered in today's lecture: 13.4 Matchings and covers of graphs.

[06-12-11] Covered in today's lecture: 12.3 Bubble sort, Merge sort, Quick sort.

[1-12-11] Covered in today's lecture: 12.2 Rooted trees. Preorder and postorder traversal. Depth-first search tree. Breadth-first search tree.

[29-11-11] Covered in today's lecture: 12.1 Trees. Labelled trees and Prufer codes.

[22-11-11] Covered in today's lecture: 11.6 Bipartite graphs are 2-colourable. 4, 5, and 6-colour theorem for planar graphs. Deletion-Contraction formula for chromatic polynomials. Chromatic polynomials for paths, cycles, complete graphs.

[17-11-11] Covered in today's lecture: 11.4 Planar and nonplanar graphs. Euler's formula. Kuratowski's Theorem.

Midterm 2 solutions

[15-11-11] Covered in today's lecture: 11.5 Hamilton paths and cycles. Bipartite graphs.

Midterm 2 is on Thursday November 10. It covers all material up to and including Section 11.3 (together with the material in the additional notes). The emphasis will be on material covered from October 13 and on. You are allowed to bring one sheet of notes, 8.5" x 11", double-sided. Calculators are not allowed.

[07-11-11] Covered in today's lecture: 11.1, 11.2, 11.3 Connectivity of graphs. Review of recurrence equations.

[03-11-11] Covered in today's lecture: 11.1, 11.2, 11.3 Complete graphs, graph complements. n-cube graph. k-regular graphs. Paths and walks. Adjacency matrix, incidence matrix.

[01-11-11] Covered in today's lecture: 11.1, 11.2, 11.3 Definitions: graph, multigraph, directed graph. Isomorphisms, various subgraphs, walks, paths, cycles. Konigsberg problem, characterization of Eulerian graphs. Sum (over all v in V) deg(v) = 2|E|.

[27-10-11] Covered in today's lecture: 1.5, 5.3 Set partitions. Noncrossing partitions, Narayana numbers. Temperley-Lieb algebra. Stirling numbers of the second kind.

[10-25-11] Covered in today's lecture: 10.5, 1.5 A special nonlinear recurrence: Catalan numbers and Dyck paths. Generating function for C_n. Alternate derivation of C_n via counting `bad' paths. Catalan objects: triangulations of convex n-gons, parenthesization of letters. FYI: more Catalan objects.

[20-10-11] Covered in today's lecture: 10.3, 10.4 Solving nonhomogeneous recurrence equations, Tower of Hanoi example. Using generating functions to get a closed formula for recurrence equations. Using recurrence equations to get a recursive formula for coefficients of generating functions. Notes for this.

[18-10-11] Covered in today's lecture: 10.1, 10.2 Finding solutions to linear homogeneous recurrence equations of order k, when k mostly equals 2.

[13-10-11] Covered in today's lecture: bivariate generating functions, 9.4 Bivariate generating functions and examples with binary strings. Calculating averages using bivariate generating functions. Exponential generating functions. Exponential generating functions for derangement numbers. Here are additional notes on partitions and bivariate generating functions. In the partition notes, there is a cute recurrence equation for the number of partitions which we haven't discussed in class. We might return to this if time permits.

Midterm 1 solutions

Midterm 1 is on Thursday October 6. It covers all material up to and including Section 9.3 (together with the additional material on generating functions not in your textbook). You are allowed to bring one sheet of notes, 8.5" x 11", double-sided. Calculators are not allowed. Sample midterm and solutions. Note that your midterm will have 6 questions. Question 3b on the sample is not relevant to your midterm. As promised, here are the additional notes on generating functions.

[04-10-11] Covered in today's lecture: extra material on partitions. Durfee square decomposition of partitions. Two generating functions for self-conjugate partitions. Some old homework problems, sample midterm problems.

[29-09-11] Covered in today's lecture: extra material on binary strings, 9.3 Counting binary strings. Partitions, Ferrers diagram, Young diagram, conjugate partition. Partitions with distinct parts = partitions with odd parts only.

Partial solutions to homework assignments will be posted on the homework page after the due date. Homework 2 solutions are available.

[27-09-11] Covered in today's lecture: 4.1, extra material on generating functions. Counting subsets with restrictions. Mathematical induction. Formulas for sums of integers, squares, cubes. Introduction to binary strings.

[22-09-11] Covered in today's lecture: 8.3, 9.1, 9.2 Derangements. Various formulas and identities. Introduction to generating functions of a sequence. Examples of computations of [x^n]f(x). An application: counting compositions of n with k parts, and other variations. Office hours for Tuesday September 27 will be moved to 1:30pm -- 2:30pm.

[20-09-11] Covered in today's lecture: 8.2 Applications of Inclusion-Exclusion: Euler phi function, integer solutions of equations with restrictions. Generalizations of Inclusion-Exclusion: exact and at-least formulas. Definition of permutations, derangements.

[15-09-11] Covered in today's lecture: 1.4, 8.1 Pascal's Triangle and some binomial identities. Theorem of Inclusion-Exclusion. Counting surjective functions.

[13-09-11] Covered in today's lecture: 1.3, 1.4 Examples of choosing sets and multisets. Counting nonnegative integer solutions to the equation x_1+...+x_n = k. Sum and Product rules, basic set theory. Binomial Theorem.

[08-09-11] Covered in today's lecture: 1.1, 1.2 Permutations, lists, sets, multisets. Counting linear arrangements, circular arrangements. Counting lists of length k from {1,...,n}, with or without repetition. Counting sets of size k from {1,...,n}, with or without repetition. Proving equality of two numbers using bijections between sets.

A brief outline of each lecture, homework assignments, and announcements will be posted here. Check frequently!