Math 381 - Discrete Mathematical Modeling

Lecture Summaries

1W - 1/03/07

• Overview of course; lifeboats and life vests; graph theory definitions.
• Syllabus

1F - 1/05/07

• Homework #1. (Due Fri., Jan. 12.)
• Graph theory, traveling salesman problem, complexity of algorithms.

2M - 1/08/07

• Shortest path problems, Dijkstra's algorithm, using Dijkstra's algorithm for scheduling problems.

2W - 1/10/07

• Minimum spanning tree, Kruskal's and Prim's algorithm. Relation to traveling salesman problem when weights obey triangle inequality.

2F - 1/12/07

• Eulerian closed chains. HW for Wed.: Think about problems where graph theory techniques might be useful. Check the web. In particular, look at the link to the traveling salesman problem web page from the course web page (under References).

3W - 1/17/07

• Homework #2. (Due Wed., Jan. 24.)
• Discussion of problems where graph theory techniques can be useful. Using Matlab.
• Diary file showing basic use of Matlab: diary

3F - 1/19/07

• Implementing Prim's algorithm in Matlab.
• Matlab code implementing Prim's algorithm for a minimum spanning tree: prim.m
• Sample solutions for HW1

4M - 1/22/07

• Using Matlab. Basic statistics.

4W - 1/24/07

• Probability distributions and random variables. The Central Limit Theorem.
• Homework #3. (Due Wed., Jan. 31.)

4F - 1/26/07

• Continuous random variables. Monte Carlo simulations. The Buffon needle problem.

5M - 1/29/07

• Monte Carlo methods. Buffon needle problem and estimating pi. Using the Central Limit theorem to estimate error in approximations.
• Sample code for HW2

5W - 1/31/07

• Poisson processes and Bernoulli trials.

5F - 2/2/07

• Discuss projects. Queuing theory.
• MatLab code to simulate a queue (from p. 39 of Course Notes): queue.m
• Homework #4. (Due Wed., Feb. 14.)
• Information on course projects (Proposal due Wed., Feb. 14)

6M - 2/5/07

• Markov chains. Review of eigenvalues and eigenvectors.

6W - 2/7/07

• More on Markov chains. Finding steady state using eigendecomposition.
• Sample solutions for HW3

6F - 2/9/07

• More on Markov chains. Examples. Reducing number of states.
• Practice problems for midterm

7M - 2/12/07

• Applications of Markov chains. Card shuffling. Google's PageRank. Ecological models and Leslie matrices.

7W - 2/14/07

• Collect HW4 and Project Proposals. Review for midterm.
• Sample solutions to practice problems for midterm

7F - 2/16/07

• Midterm.

8W - 2/21/07

• Form more groups for projects. Go over midterms.

8F - 2/23/07

• Linear programming.

9M - 2/26/07

• Simplex algorithm. Collect revised project proposals.

9W - 2/28/07

• Integer programming.

9F - 3/2/07

• Traveling salesman problem as IP. Using IP to solve puzzles.
• Homework #5. (Due Fri., Mar. 9.) NOTE: In problem 1, the total capacity needed should be 11; that is, there should be enough life boats and life vests to accommodate 11 passengers with one or the other. This was accidentally omitted (and you need it).
• Puzzles using IP

10M - 3/5/07

• Go over solutions to IP puzzles. Maximum likelihood and evolutionary trees.
• Sample solutions to IP puzzles