Prerequisite: Intermediate Algebra, Rutgers Math 026, Math 027, or equivalent.
Text: Excursions in Modern Mathematics, 4rd Edition, by Peter Tannenbaum and Robert Arnold.
Meeting times: MTWTh – 8:15 – 10:00 AM in FH-B5 (June 23 – July 31)
Final Exam: Thursday, July 31, 8:15 – 11:15 AM in FH-B5
Instructor:
|
Name: |
Robert Wilson |
|
Office: |
77 Hamilton Street (CAC) |
|
Office phone: |
732-932-8286 |
|
Messages: |
732-932-8286 |
|
Email: |
|
|
|
|
|
|
|
Office hours: TWTh – 11:00 AM – noon at 77 Hamilton Street (CAC)
Calculator: A basic calculator capable of taking square roots will be needed both for homework and examinations. Computers and calculators with typewriter keyboards will not be permitted on exams.
Other materials: A small plastic ruler will be required for homework and examinations during the later part of the semester.
Course topics: Chapters 1-8, 11, and 12. Chapter 12 involves the modest use of complex numbers. Since complex numbers are not part of the syllabus of Math 027, the basic arithmetic of complex numbers will be reviewed in class.
Grading: The term grade will be based on the results of the examinations, the scores on written homework, and on class participation, which will be measured using "one-point quizzes". The term grade will be based on a possible total of 515 points, as follows:
One-point
quizzes |
10 |
Homework
|
105
|
|
Hour
Exam 1 |
100 |
|
Hour
Exam 2 |
100 |
Final
Exam
|
200
|
|
|
|
|
Total |
515 |
Here is more information about the individual components of the grade:
Exams: There will be two hour exams and a final. The hour exams will count 100 points each and the final will count 200 points. Exams will be closed book. For the final exam, a two-page student-prepared formula sheets may be used; alternatively, an instructor prepared summary sheet may be used. Follow this link for the summary sheet for the Final Exam Final exam summary sheet
Homework: There will be a written homework assignment for of the chapters 1-3, 5-7, and 11. These seven assignments will count 15 points each, for a total of 105 points. Homework is due at the beginning of the first class after all relevant material has been covered. Homework that is late because of religious observance or similar reason will be accepted without penalty provided the instructor is informed in advance. In addition, every student will be allowed to turn in one assignment one class period late with no questions asked. All other late homework will be subject to a penalty unless documentation of illness or similar problem can be provided.
All homework solutions should include a description, in complete English sentences, of the method of solution. Students should imagine that one of their classmates does not believe their answer is correct. The written solution should explain enough about how the result is obtained that this person will have to accept the correctness of the answer.
One point quizzes: Students' involvement in the course will be assessed in several ways. In most class meetings there will be a short quiz, usually on some topic mentioned that day. These quizzes will count 1 point each. Credit will be awarded to anyone present who hands in a paper with their name on it. However, the answers will be read by the instructor and comments will be provided where appropriate. Thus students can get immediate feedback about their understanding of the material. A maximum of ten points may be earned from the one point quizzes.
Standards: The text contains homework problems with three levels of difficulty. The problems in the "walking" sections check basic understanding. Those in the "jogging" sections either involve more complexity or require slightly higher critical thinking skills, or both. The problems in the "running" sections are more difficult and may be open-ended. Questions on the examinations will be similar to those assigned for homework, which are mostly at the walking level, but include some at the jogging level and a few at the running level
Retests on Exam #1:
Students wishing to improve their grades on exam #1 (up to a maximum
of 78) may take a retest. This retest
will consist of 5 questions worth a total of 78 points. Retests should be taken before the second
exam (i.e., before July 23). Retests
may be taken during office hours or by arrangement at some other time.
Schedule:
|
June 23 |
Overview of course, Chapter 1 |
|
June 24 |
Chapter 1 |
|
June 25 |
Chapters 1 & 2 |
|
June 26 |
Chapter 2, Homework for Chapter 1 due |
|
June 30 |
Chapters 2 & 3 |
|
July 1 |
Chapter 3, Homework for Chapter 2 due |
|
July 2 |
Chapters 3 & 4 |
|
July 3 |
Chapter 4, Homework for Chapter 3 due |
|
July 7 |
Chapter 4 |
|
July 8 |
Hour Exam on Chapters 1 to 4 |
|
July 9 |
Chapter 5 |
|
July 10 |
Chapter 5 |
|
July 14 |
Chapter 6, Homework for Chapter 5 due |
|
July 15 |
Chapter 6 |
|
July 16 |
Chapter 7, Homework for Chapter 6 due |
|
July 17 |
Chapter 7 |
|
July 21 |
Chapter 8, Homework for Chapter 7 due |
|
July 22 |
Chapter 8 |
|
July 23 |
Hour Exam on Chapters 5 to 8 |
|
July 24 |
Chapter 11 |
|
July 28 |
Chapter 11, Homework for Chapter 11 due |
|
July 29 |
Chapter 12 |
|
July 30 |
Chapter 12 |
|
July 31 |
Final Examination – 8:15 – 11:15 AM |
First homework assignment (due Thursday, June 26)
Chapter 1: Problems # 4, 8, 16, 18, 32, 36, 52.
Chapter 2: Problems # 6,8,12,24,28(b), 44, 46
Chapter 3: Problems #8,10,16, 24, 36, 44, 46, 62
Chapter 4: Practice problems (DO NOT HAND IN) #4,10,18,24,30,46,62
Chapter 5: #10, 12, 18, 26, 30, 40(b), 42, 52
Chapter 6: #8, 12, 20, 24, 34, 38, 44, 56
Chapter 7: #2, 16, 22, 28, 34, 44, 52
Chapter 8: Practice problems (DO NOT HAND IN) #6, 18, 28, 30, 32, 40, 50
Chapter 11: #10,18,22,34,42,70,71,72, supplemental problems (handed out in class)
Chapter 12: Practice problems (DO NOT HAND IN) #2,4,10,12,20,52,58
Summary of lectures:
Lecture 1 (June 23): We defined preference ballots and preference schedules.
“Methods” are rules for determining the winner from a preference schedule.
“Criteria” are conditions that we hope a “fair” method of determining a winner will satisfy.
We discussed the plurality method, the Borda count method, the majority criterion, and the Condorcet criterion.
The Borda count method may violate the majority criterion.
The plurality method may violate the Condorcet criterion.
Lecture 2 (June 24) We discussed the plurality-with-elimination method, the pairwise comparison method, the monotonicity criterion and the independence-of-irrelevant-alternatives criterion.
Examples showed that the Borda count method may violate the Condorcet criterion, that the pairwise comparison method may violate the monotonicity criterion and that the plurality-with-elimination method may violate the monotonicity criterion.
According to the Arnow Impossibility Theorem, if the number of candidates is greater than two, it is impossible to find a method of determining the winner of an election which always satisfies all four of our fairness criteria (majority, Condorcet, monotonicity and independence-or-irrelevant-alternatives).
If it is desired to rank the candidates in order (instead of just determining a winner) there are extended versions of each of the four methods we discussed (plurality, Borda count, pairwise comparison, plurality-with-elimination). It is also possible to apply any one of these methods recursively, first determining the winner, then eliminating the winner from consideration and determining second place, etc.
Quiz #1
Lecture 3 (June 25): Examples of rankings using the four extended methods (extended plurality, extended Borda count, extended plurality-with-elimination, extended pairwise comparison) and the four recursive methods (recursive plurality, recursive Borda count, recursive plurality-with-elimination, recursive pairwise comparison)
Beginning of Chapter 2 - weighted voting systems: We defined players, weight, quota, dictators, dummies, veto power, coalitions, the weight of a coalition, winning coalitions, losing coalitions, critical players and the Banzhaf power index.
Lecture 4 (June 26): Examples of computation of the Banzhaf power index; definition of the Shapley-Shubik power index
Lecture 5 (June 30): Examples of computation of the Banzhaf power index (Problem #21) and of the Shapley-Shubik power index (problems #27(a,c), #31).
Beginning of Chapter 3: continuous, discrete and mixed fair-division problems, the divider-chooser method, the lone-divider method
Quiz #2
Lecture 6 (July 1): Solution of homework problem #52 from Chapter 1.
Continuation of discussion of fair-division problems: the lone-chooser method and the last-diminisher method
Lecture 7 (July 2): Continuation of discussion of fair-division problems: the method of sealed bids and the method of markers
Introduction to apportionment problems (Chapter 4)
Quiz #3
Lecture 8 (July 3): Apportionment problems – Hamilton’s Method, Jefferson’s Method, Adams’ Method, Webster’s Method
Lecture 9 (July 7): Review and solution of problems
Class 10 (July 8): Exam #1
Lecture 11 (July 9): Introduction to graphs: Definition of graphs (vertices and edges), adjacent vertices, adjacent edges, degree of a vertex, paths, circuits, connected graphs, disconnected graphs, connected components of a graph, Euler paths and Euler circuits. The sum of the degrees of the vertices of a graph is equal to twice the number of edges; consequently, the number of vertices of odd degree is even. If a graph has an Euler circuit, then every vertex must have even degree. If a graph has an Euler path, then either 0 or 2 vertices have odd degree. Fleury’s algorithm gives a procedure for finding an Euler path if there are at most two vertices of odd degree. To construct a route which covers every edge of a graph (repeating some edges if necessary) we may duplicate some edges in the graph to make the degree of every vertex even (a process called “Eulerizing” the graph). Then one can apply Fleury’s algorithm.
Lecture 12 (July 10): Examples from Chapter 5
Lecture 13 (July 14): Hamilton circuits and Hamilton paths; the traveling salesman problem; scheduling problems; a method for finding an optimal Hamilton circuits: the “brute force method” (an inefficient algorithm)
Lecture 14 (July 15): Approximate methods for finding Hamilton circuits: the “nearest neighbor algorithm,” the “repetitive nearest neighbor algorithm,” and the “cheapest-link algorithm”
Lecture 15 (July 16): Introduction to networks: trees, spanning trees and minimal spanning trees; Kruskal’s algorithm for finding a minimal spanning tree
Lecture 16 (July 17): Examples of the use of Kruskal’s algorithm, Steiner points, a triangle has a Steiner point if and only if no angle is greater than of equal to 120 degrees
Lecture 17 (July 21): Scheduling problems: processors; classification of tasks (ineligible, ready, in process, completed); precedence relations; the directed graph (digraph) of a job; priority list; scheduling a job given the digraph, a priority list and the number of processors.
Lecture 18 (July 22): Independent tasks; algorithms for efficient scheduling: the decreasing time algorithm, critical paths and the critical time; the backflow algorithm for computing critical times; the critical path algorithm
Class 19 (July 23): Exam #2 (on Chapters 5 – 8)
Lecture 20 (July 24): Rigid motions (reflections, rotations, translations, and glide reflections). Proper motions preserve left and right (or, equivalently) clockwise and counter-clockwise. Improper motions do not. Rotations and translations are proper motions, reflections and glide reflections are improper motions. Symmetries of finite shapes.
Lecture 21 (July 28): The symmetry types DN and ZN. Symmetries of infinite patterns: border patterns and wall paper patterns
Lecture 22 (July 29): Examples of symmetries; recursive replacement rules and self-symmetry; the Koch snowflake