MATH 363 Discrete Mathematics

email: firstname.lastname@mail.mcgill.ca

// home

Main page

News Course Information Notes and slides

Internal links

Forum Combinatorial game theory Final letter (A-F) grade End of semester vote Grades Midterm marking notes Chinese postman Slitherlink Midterm practice questions McGill policy

External links

Discrete Mathematics Elementary and Beyond (free book) The four colour theorem Colouring planar graphs Planar graphs Fibonacci in nature TSPLIB (travelling salesman instances) An application of Eulerian trails Slitherlink

Last two weeks

Tutorial

Student #:

1.Would you like to have a "tutorial" session (where solutions to the assignment are explained and/or more examples of material covered in class is given) instead of office hours for the last two weeks?
Yes
Yes, but only April 14, not April 7.
No
Abstained
Topic request (if yes). Max 100 chars.

If you did not answer "yes" above, skip the next two questions.

2.If you would like to come to the tutorial, are you able to attend (Wednesday 2:30pm-4 pm)?
Yes
No

3.Would a different time be better (even if you are able to attend)?
Yes
No
Other time (if yes). Please specify as many time slots as possible. Max 100 chars.

Extra topics

In the last few classes, we will see some results from other areas of discrete mathematics (all non-examinable). Which of the following would most interest you (see the table at the bottom of this page for a brief description)?

Combinatorial game theory
Four colour theorem
Counting labelled trees
Combinatorial design
Other
Please specify. Max 100 chars.

Combinatorial game theory	Nim is a 2 player game. At the start of the game, there are 3 piles of tokens. Players take turn choosing one pile and removing a positive number of tokens from the chosen pile. The player to taken the last token wins. In a variant of this game, there is only one pile of tokens but players must remove either 1, 7 or 10 tokens from the pile when it is their turn We look at how to win at these and other turn based full information games.
Four colour theorem	The four colour theorem is a famous problem in graph theory. The theorem states that the regions of any map can be coloured with four colours so that regions sharing a border receives different colours Although the theorem is simple to state. Its proof is surprisingly difficult. An interesting, but less well know, fact about this proof is that it is computer assisted. That is at some points in the proof, a computer is used to check hundreds of cases. We look at the proof on a high level and see just how a computer is used.
Counting labelled trees	Determining the number of (unlabelled) graphs with n vertices is difficult. However, determining the number of labelled graphs is easy. Suppose instead we want to determine the number of labelled trees. It turns out that there is a very nice bijection for counting labelled tree. This is know as the Prüfer sequence. We look at the simple algorithm which turns a tree into a number and back.
Combinatorial design	Suppose we building large complex system which has many "switches" which can be individually set to "on" or "off". We want to make sure our system does not break but it would take too much time to test all combination of switch states. It was noticed that if the system breaks, it is due to a combination of a small number of switches. We would like to design a series of tests (in each test, we set each switch to some state "on" or "off"). We use combinatorial designs to show that few tests are needed.

Website design modified from Sliqua taken from OSWD