APM 463/563, Applied Mathematics, Discrete Methods I, 4 credits—Fall 2008

• Detailed syllabus for the course.
  
  
• Place and Time: Tue, Thu at 7:30–9:17 PM in SFH 365.
  
  
• Office hours: Wed 1:00–2:00 PM, or by appointment (SEB 347).
  During office hours I let everyone who showed up into my office and discuss questions in a round-robin manner. If you need to see me outside regular office hours, ask or e-mail me to set up an appointment.
  
  
• Textbook: Graph Theory and Its Applications, Second Edition, by Jonathan L. Gross and Jay Yellen (GY) (Chapman & Hall/CRC, 2005) ISBN: 1-58488-505-X; and generatingfunctionology, third edition, by Herbert S. Wilf (W) (A K Peters, 2005), ISBN: 1-56881-279-5, and handout about partitions of integers and strings (CO). Any edition of these books will be appropriate for the course. I expect you to have a copy of these textbooks. Note that the second edition of generatingfunctionology can be downloaded for free from here.
  • Correspondence of sections between the two editions of (GY).
  
  
• Homework Assignments: There will be three or four homework assignments worth 20% of your final grade. Your solutions should be nicely presented. Write as clearly and cleanly as you can, use sentences, and explain the steps of the solution. I encourage you to work in groups and discuss the problems and their solutions with each other. However, the actual solutions you submit should be your own work (see Academic honesty for more info).
  • Assignment 4 in pdf format.
    Due date: Thu, Nov 20, 2008.
    Sample files for students choosing the Computer Science Option:
    • Sample file 1
    • Sample file 2
    • Sample file 3
    • Sample file 4
    • Sample file 5
    • Sample file 6
    • Sample file 7
  • Assignment 3 in pdf format.
    Due date: Tue, Oct 21, 2008.
    Template for the library project
    
    • Sample file 1
    • Sample file 2 (same graph, start from other vertex)
    • Sample file 3 (graph in Exercise 4.3.2 in (GY))
    • Sample file 4 (graph on page 180 in (GY))
    • Sample file 5 (big graph)
  • Assignment 2 in pdf format.
    Due date: Tue, Oct 7, 2008.
    
  • Assignment 1 in pdf format.
    Due date: Thu, Sep 18, 2008.
    Sample files for students choosing the Computer Science Option:
    • Sample file 1
    • Sample file 2
    • Sample file 3
    • Sample file 4
    • Sample file 5
  
  
• Midterm Exams: There will be two midterm exams tentatively scheduled on October 2nd (Thursday) and November 4th (Tuesday) worth 20% of your final grade overall. These will be closed-book exams, notes and textbooks will not be allowed.
  • Midterm Exam #2: CS option: Write a computer program to find a maximum matching in a simple bipartite graph using augmenting paths (not flows). Specifications of the program:
    Input: The input graph is given in a file in the following format: the first line contains just the number of vertices (which are assumed to be labeled with the numbers 1 up to the number of vertices), and then the edges are listed by specifying the two endpoints of an edge in each line (you may assume that the input graph is simple).
    Sample files:
    
    • Sample file 1
    • Sample file 2
    • Sample file 3
    • Sample file 4
    Output: The program should print the list of edges forming a maximum matching, and a corresponding minimum cover certifying that the matching is maximum.
    E-mail me the source code of the program as a simple text file and the resulting outputs for the given sample inputs. In addition, e-mail me or hand in documentation of the program (this may partially be in the source code), explaining the data structures and the main variables.
    Deadline: Thursday, November 13th.
    
  • Midterm Exam #1: CS option: Implement Prim's algorithm to find a minimum weight spanning tree in a graph. Specifications of the program:
    Input: The input graph is given in a file in the following format: the first line contains just the number of vertices (which are assumed to be labeled with the numbers 1 up to the number of vertices), and then the edges are listed by specifying the two endpoints and the corresponding weight of the edge (each line contains info about one edge, loops and multiple edges are possible).
    Sample files:
    • Sample file 1 (this is the example on page 177 of (GY))
    • Sample file 2
    • Sample file 3
    Output: The program should print the starting vertex and the edges as they are being selected. At the end, it should print the edges of the minimum weight spanning tree it found and state its total weight, or give reasons if the graph has no spanning trees.
    E-mail me the source code of the program as a simple text file and the resulting outputs for the given sample inputs. In addition, e-mail me or hand in documentation of the program (this may partially be in the source code), explaining the data structures and the main variables.
    Deadline: Thursday, October 9th.
    
  
  
• Final Exam: The Final Exam is comprehensive, and will be given on Thursday, December 11, 2008, 7:00–10:00 PM. This will be a closed-book exam worth 60% of your final grade; notes and textbooks will not be allowed. Final grades will be available on Moodle.
  
  
• Computer science option: You will have the option of doing programming exercises for a portion of each assignment, some midterm exams, and the final exam. Whenever you want to choose this option, you will have to notify me ahead of time (at least a week before a midterm exam, and before November 5th for the final exam). The programming exercises involve implementing an algorithm discussed in class in C or C++, and I should be able to compile them in OU's Unix environment. Send me the source code with documentation by e-mail, explaining the data structures and main variables, and give the output for the sample inputs I provide. You may discuss the algorithms and data structures you use in your programs with others, but the source code and documentation should be your own work. You will still need to take the midterm and final exams, but may ignore the problems I indicate.
  
  
• Recommended exercises:

  Recommended Exercises

  Material	(W)	(CO)
  Exponential families, Lagrange inversion	Section 3: 1–2.	Pages 51–52: 1–3.
  Binary trees, planted trees	—	Pages 50–51: 1, 3.  Page 55: 1–2.
  Bivariate generating functions, averages	—	Pages 35–36: 1–6.
  Generating functions via weight functions. Block decomposition of binary strings	—	Pages 13–14: 2–4, 11–12.  Pages 19–20: 1–3, 5–6, 8.  Page 26: 1–3, 5–7.  Page 29: 1–3, 5.
  Calculus of ordinary power series and exponential generating functions	Section 2: 1–7, 21(a), 22, 27, 32.	—
  Formal power series	Section 1: 1, 3, 5, 6, 11.	—
  Material	(GY) 1st ed.	(GY) 2nd ed.
  Vertex coloring, Brooke's theorem, six- and five-color theorems	Section 10.1: 6–8, 10–11, 20–21, 31–32.  Section 10.2: 8–9, 16–17.	Section 9.1: 6–8, 10–11, 20–21, 31–32.  Section 9.2: 8–9, 16–17.
  Planarity, Kuratowsky's theorem	Section 8.3: 9–10, 13–14.  Section 8.4: 2–3, 10–11.  Section 9.1: 2, 6, 8–9, 20–21.  Section 9.2: 1–8, 10–12.  Section 9.3: 1–4.	Section 7.3: 10–12.  Section 7.4: 1–4.  Section 7.5: 2–3, 10–11, 28, 32, 34–35.
  Matchings in bipartite graphs	Section 12.4: 3–6, 12–14, 17, 20–21, 26–27.	Section 13.4: 3–6, 12–14, 17, 19, 21.
  Connectivity, Whitney's and Dirac's theorems	Section 5.1: 6–10, 12, 18, 25.	Section 5.1: 6–10, 12, 18, 25.
  Flows, Menger's theorems	Section 5.3: 2–3, 6–7.  Section 12.1: 3–6, 9–10, 13.  Section 12.2: 4–6.	Section 5.3: 2–3, 6–7.  Section 13.1: 3–6, 9–10, 13.  Section 13.2: 4–6.
  Matroids and the greedy algorithm, Kruskal's algorithm	Section 4.8: 1–9, 11–12.	Section 4.7: 1–9, 11–12.
  Walks, Eulerian tours, shortest paths, Dijkstra's algorithm	Section 6.1: 1–4, 6–8, 20–21, 25–28.	Section 6.1: 1–4, 6–8, 20–21, 25–28.
  Spanning trees, Prüfer code, Cayley's formula, Prim's algorithm	Section 4.4: 5–8.  Section 4.5: 3–4, 9–10, 12.	Section 3.7: 5–8.  Section 4.3: 3–4, 9–10.
  Trees, forests, binary trees, Huffman code	Section 1.4: 1–2, 18, 23–24, 31.  Section 1.5: 1–2, 5–6, 26–30, 36.  Section 3.1: 1–9, 14–16, 18–19, 23–26.  Section 3.3: 3–9.	Section 1.4: 1–2, 33, 38–39, 46.  Section 1.5: 1–2, 5–6, 30–33, 39.  Section 3.1: 1–9, 14–16, 18–19, 22–25.  Section 3.5: 1–7.
  Intro to graphs, degree sequences	Section 1.1: 13–19, 28.  Section 1.2: 1–6.	Section 1.1: 13–20.  Section 1.2: 1–6.

  
  
  
• Material covered:
  
  • Week 11: (Nov 12–16)
    Formal power series, Calculus of ops, Class Notes on Nov 11, 2008, Class Notes on Nov 13, 2008
  • Week 10: (Nov 5–9)
    Midterm Exam #2, five- and six-color theorem, Formal power series, Class Notes on Nov 6, 2008
  • Week 9: (Oct 27–31)
    Kuratowski's theorem. Vertex colorings, Brooks's theorem, Class Notes on Oct 28, 2008, Class Notes on Oct 30, 2008
  • Week 8: (Oct 20–24)
    Whitney's and Dirac's theorems. Embeddings on the plane, planarity, Class Notes on Oct 14, 2008, Class Notes on Oct 23, 2008
  • Week 7: (Oct 13–17)
    Matchings in bipartite and nonbipartite graphs, Template for the library project in Assignment 3, Class Notes on Oct 14, 2008, Class Notes on Oct 16, 2008
  • Week 6: (Oct 6–10)
    Connectivity, Menger's theorem (edge version and vertex version), Matchings in bipartite graphs, Assignment 3, Class Notes on Oct 7, 2008, Class Notes on Oct 9, 2008.
  • Week 5: (Sep 29–Oct 3)
    Flows; Midterm Exam #1; Class Notes on Sep 30, 2008.
  • Week 4: (Sep 22–26)
    Finding minimum weight spanning trees (Prim's algorithm, Kruskal's algorithm); Matroids and the greedy algorithm; Class Notes on Sep 23, 2008, Class Notes on Sep 25, 2008
  • Week 3: (Sep 15–19)
    Trees, forests, binary trees, Huffman code; Spanning trees, Depth-first search and Breadth-first search, shortest paths, Dijkstra's algorithm; Example graph for Dijkstra's algorithm, Class Notes on Sep 16, 2008, Class Notes on Sep 18, 2008
  • Week 2: (Sep 8–12)
    Walks, Eulerian tours; Trees, forests, binary trees; Spanning trees, Prüfer code, Cayley's formula; Class Notes on Sep 9, 2008, Class Notes on Sep 11, 2008
  • Week 1: (Sep 1–5)
    Discussion of syllabus, Intro to graphs, degree sequences, Assignment 1, Class Notes on Sep 4, 2008
  Planned schedule:
  • Week 1: Discussion of syllabus. Intro to graphs, degree sequences.
  • Week 2: Trees, forests, binary trees, Huffman code
  • Week 3: Spanning trees, Prüfer code. Walks, Eulerian tours, shortest paths, Dijkstra's algorithm
  • Week 4: Prim's algorithm. Matroids and the greedy algorithm, Kruskal's algorithm. Connectivity, Whitney's and Dirac's theorems
  • Week 5: Flows, Menger's theorems
  • Week 6: Finding minimum cut. Matchings in bipartite graphs
  • Week 7: Matchings in nonbipartite graphs, Tutte's condition. Planarity
  • Week 8: Kuratowsky's theorem. Vertex coloring, Brooke's theorem
  • Week 9: Six- and five-color theorem. Formal power series
  • Week 10: Calculus of ordinary power series and exponential generating functions
  • Week 11: Generating functions via weight functions. Block decomposition of binary strings
  • Week 12: Bivariate generating functions, averages. Binary trees, planted trees
  • Week 13: Lagrange inversion. Exponential families.
  • Week 14: Permutations, set partitions. Labeled trees
  
  
• Academic honesty:
  Cheating is a serious academic crime. Oakland University policy requires that all suspected instances of cheating be reported to the Academic Conduct Committee for adjudication. Anyone found guilty of cheating in this course will receive a course grade of 0.0 in addition to any penalty assigned by the Academic Conduct Committee. Working with others on an assignment does not constitute cheating (unless explicitly forbidden), handing in an assignment or program that has essentially been copied from someone else does.