Fall 2008
Course Log
11/21/08 (Friday)
- Quiz 10 today. Here are the solutions.
- I did a few examples of finding Nash equilibria in non-zero sum games. We also did an example where a 4 by 4 matrix reduced to the 2x2 case by using dominating strategies.
- Everything is now graded.
- Happy Fall Break!
- Non-zero sum games and Nash equilibria. Prisoner's Dilemma.
- We talked more about zero-sum games. We showed how to solve any 2x2 zero-zum matrix game. We also talked about dominating strategies and saddle points.
- Quiz 9 today. Here are the solutions.
- We talked more about zero-sum games. We showed that both players need not have the same optimal strategy.
- We did another example of 4-pile nim. Beginning of zero-sum games. We did one example, then we worked on a worksheet.
- Today we talked about binary numbers. Converting between binary and decimal. We then used these ideas to solve nim using the nim-sum. We finished with some examples.
- Homework 5 is posted.
- We analyzed 2x2 and 2x3 Chomp. Try n x n Chomp. What is the winning strategy?
- We also had quiz 8 today. Here are the solutions.
- Play Chomp online here.
- Here are some links that you may find interesting:
- Collection of game theory links.
- Here are the notes I am roughly following: Combinatorial Game Theory.
- Mathematician of the Day: Oskar Morgenstern.
- Today we talked about subtraction games and Chomp.
- Today we talked about Combinatorial Game Theory. We saw our first game (21 chips with subtraction set {1,2,3}). We ended with P-positions and N-positions.
- Here are some links that you may find interesting:
- Wikipedia's Game Theory article.
- Notes on Combinatorial Game Theory.
- Mathematician of the Day: John von Neumann.
- Exam 2 today. Here are the solutions.
- Exam 2 grades posted. The average was an 85/100.
- Exam review today.
- We also decided on Game Theory for the next topic.
- Here is the final table for homework 4.
- Today we talked about the Electoral College. Why it exists? What are the arguments for/against it?
- Homework 4 is graded.
- Here are some links that you may find interesting:
- History of IRV.
- The Electoral College Votes Against Equality
- Wikipedia's Electoral College article.
- NARA Electoral College article.
- Founding Father of the Day: Thomas Jefferson.
- Potential workarounds to Arrow's Theorem. Went over Approval voting.
- We also had Quiz 7 today. Grades are now posted. Here are the solutions.
- Here are some links that you may find interesting:
- Wikipedia's Arrow's Theorem article.
- MIT Tech's Arrow's Theorem article.
- Site about range voting.
- Fairvote is a group advocating for the use of IRV in USA.
- Voting Theorist of the Day: Kenneth Arrow.
- Gave more examples of voting systems failing IIA. Sketched proof of Arrow's theorem.
- Today we talked more about the IIA condition and Arrow's theorem.
- Today we showed that CWC implies MC, but MC does not imply CWC. For example, plurality satisfies MC, but does not satisfy CWC. We also talked about Black's Voting System, and independence of irrelevent alternatives (IIA) condition. Think about whether our previous voting systems have the IIA condition.
- We also had Quiz 6 today. Grades are now posted. Here are the solutions.
- Here are some links that you may find interesting:
- Wikipedia's Condorcet Winning Criterion article.
- Voting Theorist of the Day: Jean-Charles de Borda.
- Today we did a few examples. We showed SPV is not neutral. We discussed Instant Runoff Voting, and showed this system is not monotone. We went over how to show a voting system has a property. You should think about whether IRV satisfies the CLC. Remember the Condorcet losing criterion (CLC) means that whenever a voting system has a Condorcet loser, then they will never win the election.
- Here are some links that you may find interesting:
- Wikipedia's Voting Theory article.
- Voting Theorist of the Day: Thomas Hare.
- Today we did some examples, introduced Condorcet winners/losers, Condorcet winning/losing criterion (CWC/CLC), and sequential pairwise voting.
- Homework 4 is now posted. It is due October 27.
- Here are some links that you may find interesting:
- Mathematician of the Day: Marquis de Condorcet.
- Quiz 5 is graded. Here are the solutions.
- We went over Borda count. Reviewed basic planarity tests. And I stumbled through an example.
- Homework 3 is graded.
- Continued our discussion of voting systems. We went over May's theorem and quota systems. Started talking about Plurality and Borda count.
- Exam 1 handed back.
- Started talking about Voting Systems. We defined anonymous, monotone, and neutral voting systems. And gave 4 examples of voting systems: majority rule, minority rule, imposed rule, and dictatorship.
- Homework 3 is not due until Wednesday now.
- Here are some links that you may find interesting:
- Mathsite has a bunch of cool math exhibits and flash games.
- Exam 1 is graded. The grades are posted to Score Reports.
- The average was 76/100.
- Exam 1 today. Here are the solutions.
- Homework 3 is not due until Wednesday now.
- Here are some links that you may find interesting:
- Mathematician of the Day: Carl Friedrich Gauss.
- Exam review session tonight at 7pm in Altgeld 143.
- We talked about Kuratowski's theorem and the 4-color theorem. Reviewed for exam.
- We decided the next topic will be social choice and voting theory.
- Extra office hours: Wednesday 4-6pm, and Thursday 10am.
- Here are some links that you may find interesting:
- History of the 4-color theorem.
- Wikipedia's article on 4-color theorem.
- Mathematician of the Day: Kazimierz Kuratowski.
- Exam review session Wednesday at 7pm in Altgeld 143.
- We went over Euler's Formula today. Then we used Euler's formula to get some tests for planarity. We showed the K5 is not planar, and that 3 houses each connected to 3 utilities must have a crossing utility line in the plane, but not on a torus (donut).
- Extra office hours: Tuesday 2-3pm, Wednesday 4-6pm, and Thursday 10am.
- Here are some links that you may find interesting:
- Explanation of Euler's formula.
- Wikipedia's article on Planar graphs.
- Mathematician of the Day: Leonhard Euler.
- Another Biography of Euler.
- Quiz grades posted. Here are the solutions.
- Added information about the first exam in the exams page.
- Today we will go over how to compute chromatic numbers using upper and lower bounds.
- The quiz will not be graded until Sunday (as I am leaving town immediately after class).
- Mathematician/Computer Scientist of the Day: Donald Knuth.
- Extra office hour tomorrow! I will be in my office from 11 am until 1 pm.
- I discovered an error in question 4 of homework 3. It is fixed now, so if you started already make sure to get the updated version.
- Homework 3 posted; homework 3 will be due October 3.
- Gave more problems to practice graph coloring.
- We went over some of the problems from homework 2.
- Here are some links that you may find interesting:
- Mathematician of the Day: Ronald Graham.
- Homework 2 grades posted. We will go over a few of the problems on Wednesday.
- Gave a puzzle to introduce graph coloring. We defined a graph coloring, chromatic number of a graph, and complete graphs. We went over a few examples and observed that the chromatic number of the n-th complete graph is n.
- Here are some links that you may find interesting:
- Wikipedia's Graph Coloring article.
- Graph coloring lesson at UTC.
- Graph coloring notes at UIUC.
- Mathematician of the Day: Paul Erdős.
- More examples of DNA sequencing problems.
- Quiz 3 today. Grades are online now. Here are the solutions.
- Here are some links that you may find interesting:
- A nice powerpoint presentation on graph theory applications.
- Gallery of graphs at CCNR.
- Mathematician of the Day: James Joseph Sylvester.
- Today we talked about DNA sequencing. We showed how given a bunch of DNA fragments we can reconstruct the original strand.
- Here are some links that you may find interesting:
- Wikipedia's article on DNA Sequencing.
- An article on DNA Sequencing.
- Sequencing by Hybridization and graph theory.
- Sequencing by Hybridization article from a professor in the computer science department here.
- Mathematician of the Day: William Rowan Hamilton.
- We talked about De Bruijn sequences today. I finally gave an application of Euler cycles and paths to making jewelery. Namely, we constructed necklaces made of diamonds and rubies that contained every sequence of rubies and diamonds of length 2, 3, and 4.
- Here are some links that you may find interesting:
- Wikipedia's article on De Bruijn sequences.
- Dan Zaharopol's article on De Bruijn sequences.
- Con game based on De Bruijn sequences.
- Mathematician of the Day: Nicolaas Govert de Bruijn.
- In homework 2, when I ask you to find non-isomorphic graphs with 4 vertices, do not include multiple edges between the same vertices.
- Homework 2 posted; it will be due September 22. We had Quiz 2 today. The quiz solutions are posted. Grades are also posted. We did some examples of Eulerian paths in directed graphs (with colored chalk!). Next week we will start talking about applications.
- Introduced directed graphs. Extended all our results about Eulerian cycles and paths to directed graphs.
- Reviewed Euler's theorem at the beginning of class. We characterized Eulerian paths, and we found an algorithm for finding an Eulerian path. Homework 1 grades are now online.
- Today we had quiz 1. The solutions are posted. The grades are posted to Score Reports. We also talked more about graph isomorphisms.
- Today we talked about graph isomorphisms.
- Introduction to graph theory. We defined a graph, paths, cycles, Euler cycles, and degrees. We proved Euler's theorem, and found an algorithm for finding an Euler cycle in a graph whenever it is possible.
- Here are some links that may help you understand basic graph theory:
- Graph Theory Tutorial
- Wikipedia's Graph Theory page.
- Graph Theory in Practice I. This link shows how some researchers in computer science use graph theory. They show that the internet is on average 19 clicks across.
- Another introduction to graph theory. This link talks about the history and fundamental questions in graph theory.
- Basic definitions in graph theory.
- More puzzles. First problem set posted. It will be due Monday, September 8.