Applications of Mathematics, MATH 111

Homework due:

Euler Circuits, Chapter 5

Fri, Jan 21: Get the book. For the neighborhood drawn on the black-board, create the graph representing the possible routes for (a) policeman, (b) mail carrier (look at Chapter 5, p. 178, in the book to help clarify this task). Recall that a mail carrier may have to walk a street twice to deliver mail to both sides of the street.

Mon, Jan 24: More on Euler Circuits. Rewrite your notes nicely in your "good" folder. Write a paragraph or two in your journal sharing your experiences of the week. HW: Chapter 5, # 2, 4, 15, 17, 21.

Wed, Jan 26: Rewrite your class notes into your "good" folder. HW: Chapter 5, # 23, 25, 27, 29, 31.

Fri, Jan 28: HW: Chapter 5, # 30, 32, 38, 40. Also keep those attempts where you get stuck on the way. Explore why that happens. Think about strategies to avoid getting stuck in this way. Transfer your findings to your "good" folder.

Monday: Jan 31: Chapter 5: # 72, 73. Add journal entry. Make sure your "good" notes about Euler circuits are complete. You shuold include some information about (1) graphs, paths, circuits, (2) Euler paths and Euler circuits, (3) unicursal drawings (w/o lifting pen), (4) how to check whether a graph has an Euler path/circuit (based on the degrees of the vertices), (5) find an Euler circuit using Fleury's algorithm (illustrated by a small example graph), and (6) Eulerization (doubling certain edges to create an Euler circuit).

Hamiltonian Ciruits, Chapter 6
Wed, Feb 2:Read Introductory part of Chapter 6.

Fri, Feb 4:Chapter 6: 3, 5, 7

Mon, Feb 7:Chapter 6: 26, 27. Add a journal entry.

Wed, Feb 9:Chapter 6, # 31, 33, 37, 39.

Friday, Feb 11: Chapter 6, # 41, 43, 45. Add a journal entry. Double-check your notes on Hamiltonian Circuits (HCs). It should contain: (1) definition of Hamiltonian circuit, (2) a few small graphs that do and do not have Hamiltonian circuits, (3) what is a complete graph, (4) complete graphs with weight (cost, distance) labels on their edges, (5) Traveling Salesman Problem: how to find a shortest route, (6) Algorithms, (7) Brute Force (and its limitations), (7) Nearest Neighbor Algorithm, (8) Cheapest Link Algorithm.

Mon, Feb 14: Networks, Chapter 7
Wed, Feb 16: Chapter 7: #1, 11, 13.

Fri, Feb 18: Chapter 7: #19, 22, 27, 29.

Tue, Feb 22 (Monday schedule): Chapter 7: #37, 41, 42. Write journal entry.

Wed, Feb 23: Review your good notebook, to make sure it has all the material from Chapter 7 (Networks, Shortest Networks, Minimum Spanning Trees, Kruskal's Algorithm, interior points, Steiner points, Finding Steiner points using Torricelli's construction). Make sure your journal entries are up-to-date.
Scheduling, Chapter 8
Good notebook contents: Tasks, processors, processing times, formalism using a table, precedence relationships, precedence digraph (incl. start and end nodes), priority lists, how to use a priority list to find a particular schedule, states of a task: unavailable, ready, in progress, completed (and the short-hand street signs), good ideas for scheduling algorithms (ie. finding good priority lists) such as the Decreasing Time Algorithm..

Fri, Mar 5: Chapter 8: #29 with priority list D, A, E, B, C, G, F; # 34, 36, 38. Sign up for first project.

Mon, Mar 8: Chapter 8: # 40, 41, 42, 44. Journal entry. Sign up for first project.

Mathematics of Voting, Chapter 1
Good notebook contents: Based primarily on our work-sheets, but the book might help to tie things together: Math Club Election, preference schedule, Majority Criterion, Plurality Method, Condorcet Criterion, Borda Count Method, Plurality-with-Elimination Method (Instant Runoff Voting), Problem: Monotonicity Criterion, Method of Pairwise Comparisons (Copeland's Method), Problem: Independence-of-Irrelevant-Alternatives.
We observe Arrow's Impossibility Theorem (1949): We can not satisfy our four Fairness Criteria all at once.

Weighted Voting Systems, Chapter 2
Good notebook contents: Players and their weight, quota of votes needed to pass a motion, meaningful quotas, one-person-one-vote in disguise, unanimous consent, dictators and dummies, veto power.

Banzhaf Power Index: coalitions, winning coalitions, critical players, Applications (UN Security Council, European Union).
Shapley-Shubik Power Index: sequential coalitions of all players, ie. order matters; pivotal players. Applications (Electoral College, UN Security Council, European Union).