Discrete Mathematical Modeling

Fall 2017
Tuesdays 4-6:50pm
Stauffer 110

Instructor: Professor Allon Percus

Contact information: CGU Math South Building, tel. 909-607-0744

TA: Nan Rao, nan.rao@cgu.edu
TA sessions Wednesdays 10-12 at McManus 31

Office hours: Tuesdays 11-12 at CGU Math South, or by appointment

Course description: Discrete mathematics deals with countable quantities. The techniques used for discrete models are often significantly different from those used for continuous models. This course explores some of the main techniques and problems that arise in discrete mathematical modeling. Topics include combinatorial analysis, Markov chains, graph theory, optimization, algorithmic behavior as well as current research topics. The goal is for students to acquire sufficient skills to solve real-world problems requiring discrete mathematical models.

Background and prerequisites: Prior exposure to combinatorics, probability and linear algebra is assumed. Students must have sufficient programming skills (in any language) to write a basic simulation code. Other background that is helpful but not required: an undergraduate-level course in discrete mathematics, and some exposure to analysis of algorithms.

Learning outcomes: It is expected that, by the end of this course, students will be able to:

  • Understand and apply fundamental mathematical techniques needed for discrete modeling.
  • Confidently solve real-world problems that involve discrete mathematical modeling.
  • Develop valid algorithmic and computational approaches to implement discrete models.

Textbook: All required materials, including course notes, will be posted on Canvas under the “Files” section.

Tentative schedule:

  • Aug 29: Combinatorial analysis. Product and sum rule; permutations and combinations; inclusion-exclusion; pigeonhole principle.
  • Sep 5: Combinatorial analysis. Generating functions; algorithms and complexity.
    Assignment #1 due
  • Sep 12: Markov chains. Definitions; stationary distribution.
    Assignment #2 due
  • Sep 19: Markov chains. Sampling; card shuffling.
    Assignment #3 due
  • Sep 26: Markov chains. Markov-chain Monte Carlo; mixing time; spectral analysis.
    Final project proposal due
  • Oct 3: Markov chains. Strong stationary time.
  • Oct 10: Graph theory. Connectivity; graph coloring.
    Assignment #4 due
  • Oct 17: Graph theory. Spanning trees; graph algorithms.
    Assignment #5 due
  • Oct 24: MIDTERM EXAM
  • Oct 31: Combinatorial optimization. Minimum spanning trees; shortest path.
    Assignment #6 due
  • Nov 7: Combinatorial optimization. Network flows; heuristics; simulated annealing.
    Assignment #7 due
  • Nov 14: Random networks and algorithms. Random graph theory; zero-one laws; phase transitions.
  • Nov 28: Random networks and algorithms. Random graph coloring; first moment method; algorithmic consequences.

Assignments and grading: Homework assignments will be posted on Canvas. All completed assignments must be submitted electronically as a pdf file, either by e-mail to the instructor or uploaded to Canvas. You may submit a scanned hardcopy, as long as it is in pdf format. I will also post the LaTeX source code along with each homework assignment; those of who choose to typeset your homework submissions in LaTeX may find this helpful. No late homework will be accepted, since solutions will be posted the morning after the due date. Graded homework will normally be returned, with feedback, one week after submission.

There will be an in-class midterm exam and a final project. Grades will be calculated as follows:

  • 35% Homework assignments (lowest homework grade will be dropped)
  • 30% Midterm exam
  • 30% Final project
  • 5% Class participation

You may work together on homework assignments. However, all your answers must be explained in your own words. Your homework submission must also state the names of all those with whom you collaborated. Please familiarize yourselves with CGU’s academic honesty policies.