Apr 27, 2010 Various errors were fixed in the last two days. Here is a (complete) list of changes made. Thanks to everyone who finding these mistakes.

Apr 26, 2010 Grade statistics are now available.

This is a reminder that there are office hours today from 10am to 11:30am and from 2pm to 4pm.

Apr 23, 2010 This is a reminder that there are office hours today from 2pm to 4pm.

Apr 22, 2010 Here is a summary of topics not covered on the final exam.

Here are some comments for assignments 3,4 and 5 (most comments are from the grader, but some are mine). It also includes an explanation for shorthand used when marking.

Apr 21, 2010 There is now a practice final available (PS PDF). Point values for questions and the length of the practice final have not been adjusted. Question 1 was originally intended for your midterm and will not appear in the actual final exam.

Example 1 for notes on shortest path (PS PDF) and the statement of claim 1 for the solutions for assignment 5 (PS PDF) had typos in them. They have now been fixed. Thanks goes to Jimmy Karam and Patrick Desmarais for pointing them out.

Grades for assignment 5 are now available.

Notes on probability (PS PDF) and planar graphs (PS PDF) are now up. Note that some examples seen in class may not appear in the notes.

Slides (PPT) on the Four colour theorem are also available now. Note that a subset of the slides contain a visual representation of the proof of the five colour theorem. The only macro used in these slides is for scrolling slide 13. All other slides will still render correctly with macros disabled.

Apr 20, 2010 Office hours during the exam period will be in MC 109 (this includes today's office hours).

Apr 13, 2010 Tomorrow, we will look at the proof for the Four Colour Theorem (source).

Apr 12, 2010 The deadline to fill in McGill's Online Course Evaluation is this Wednesday. It only takes 5-10 minutes and there are many reasons why you should participate.

Apr 11, 2010 There seems to be a lot of interest for combinatorial game theory. Second place is close to a tie right now. There is also a request for "economic game theory" (Nash equilibrium, prisoner's dilemma, auctions, etc) which you can also vote for.

Apr 9, 2010 The next tutorial is Wednesday April 14 at 2:30 pm in MC 103. I will be deriving and explaining solutions to the questions on assignments which were the most missed. Other requests can be made by voting.

The solution for assignment 5 (PS PDF) are now up. The solution to the bonus is coming soon.

A reminder that assignment 5 is due today at 2:30 pm and that no assignments will be accepted later than that.

It seems that the link to notes on Ramsey theory PS PDF was accidentally deleted in a previous update.

Assignment 6 (PS PDF) is now up. Do not hand it in since it does not count. Almost all questions have a reference to the solution. You should attempt these questions before looking at the solution.

Apr 7, 2010 We are now discussing planar graphs and colouring planar graphs.

Apr 1, 2010 You can now get your final letter (A-F) grade for MATH 363.

Mar 31, 2010 Please vote on what you would like to see for the next few weeks of the semester (including whether you would like to have a tutorial instead of office hours for the next two weeks).

Assignment 5 is now "due" on April 9. It should still be thought of as being due on April 7. This is since no assignment will be accepted after April 9 at 2:30 pm (absolutely no exceptions). The solutions will also be posted at that time. Furthermore, there is a good chance that you will not get you assignment back before your final if you submit it later than April 7. You are strongly encouraged to submit your assignment in class on April 7.

Mar 30, 2010 Notes on the pigeonhole principle (PS PDF) are now up.

Grades for assignment 3 are now up.

Notes on combinations with repetitions (PS PDF) are now up.

Mar 28, 2010 Notes on the inclusion-exclusion principle (PS PDF) are now up. The ordering of the material differs slightly from what we've seen in class. Counting the number of subsets of size k has been added to notes on counting (PS PDF).

Mar 27, 2010 A clarification for assignment 5. For question 1, we assume that d is at least 1.

Mar 26, 2010 Here is the source for the last two slide on Fibonacci numbers in nature.

A version of today's lecture's slides is posted PPT (warning: the slides are 4.5 MB and made in Powerpoint, although there is a free viewer).

The deadline for assignment 5 has been extended to April 7.

Mar 24, 2010 The solution for assignment 4 (PS PDF) with separate Chinese postman problem solutions (PS PDF) are now up.

Mar 22, 2010 Assignment 5 (PS PDF) is now up. It is due in class April 5, 2010.

Mar 19, 2010 The appendix in the final exam (PS PDF) has been posted. It is only currently missing theorems from assignment 4 and 5 (which cannot be posted because it would give away the answer to prove or disprove questions). Please inform if you find any mistakes or if you notice something is missing. This is especially useful while it can still be changed. Also note the change in number of items in Appendix 3 to ease binary search.

Mar 17, 2010 A replay option has been added to the Chinese postman problem.

The last part of today's office hours (from 3:30 to 4:00) will again change location (moved nearby).

Mar 11, 2010 Partial notes on counting (PS PDF) have been posted.

Mar 10, 2010 There was an error in question 4b) of assignment 4. It should read y^x rather than x^y. This has been fixed.

Mar 9, 2010 I have put up what I think is the value of the optimal solution to the Chinese postman problem as well as some notes at the bottom of the webpage. A new version with a "replay" button will be posted in a week (so people still have time to try to find the optimal solution).

The last part of tomorrow's office hours (from 3:30 to 4:00) will change location (moved nearby).

Grades for assignment 3 bonus 2 are now up.

Mar 8, 2010 The solutions for assignment 3 (PS PDF) are now up. The code for question 6 and some input cases (tar.gz zip) are also available.

All questions for assignment 4 (PS PDF) are now up. Remember that the assignment is due March 22.

Anyone who is considering submitting a late assignment should talk to me after class today. Solutions to the assignment will be posted otherwise (and no late assignment will be accepted after that point).

Mar 5, 2010 For those who would like to submit solutions for Bonus 2 of Assignment 3 should just e-mail me their code (before class today). Make sure that I reply to confirm receipt.

Mar 4, 2010 Notes on the Chinese postman problem (PS PDF) are now up.

A clarification for assignment 3, question 4b): your algorithm should output a minimum weight subset F such that (V,F) is a spanning tree and E₀ is a subset of F. Otherwise, it would be too easy since you can output E₀ all the time.

Another clarification about late assignment. Late assignment receive a 10% penalty every 24 hours (rounded up, of course). So, for example, for assignment 3, submissions between Mar 5, 2010, 2:30pm and Mar 6, 2010, 2:30pm receive a 10% penalty and submissions between Mar 6, 2010, 2:30pm and Mar 7, 2010, 2:30pm receive a 20% penalty.

Notes on bipartite matchings (PS PDF) are now up.

Mar 3, 2010 This is a bit late. But here is a link to a page about the Travelling Salesman Problem and how an instance of (Euclidean) TSP with 85,900 cities was solved (and proven optimal). You can also download the solver from that page and try it out yourself. TSPLIB contains a set of instances of TSP and related problems (e.g., for testing out new algorithms). See the TSP data link on that page.

Mar 2, 2010 The first two questions of assignment 4 (PS PDF) are now up. More questions to come. The assignment is due March 22.

The grades for assignment 2 are up.

Mar 1, 2010 Here are some explanation for shorthand used for marking the midterm and some remarks.

You can now check your grades online (probably still buggy). Please inform me if the values do not match those on paper.

There was an error in the solutions for assignment 2 (PS PDF). A missing "not" on the last line for question 1a). There was also a missing line in the solution for assignment 1 (PS PDF) in question 1a).

Feb 17, 2010 There were some errors in the midterm's appendix. These have been fixed in the new version (PS PDF). Thanks to Kamal Saleh for pointing them out. I've also added the instructions that will appear on the first page of the midterm (so that you don't waste time reading them during the exam).

A quick note about assignment 3. For the last question, you may assume that you have a subroutine which checks if an input graph contains a cycle. We briefly discussed such a subroutine in class but you do not need to write it down explicitly for the assignment. The focus of that question is the proof of correctness rather than the algorithm (the algorithm itself should be fairly easy to obtain). Two paragraphs were added at the end of the notes on trees (PS PDF) to address this.

Feb 16, 2010 The midterm appendix has been updated (PS PDF). The definition of some "named" graphs have been added. The theorem relating to Gray codes has been added. The third definition of paths and cycles has been changed to no longer refer to isomorphisms.

I've finally put up a sample midterm (PS PDF). Not nearly enough thought has gone into this one as your actual midterm, though (most of the work was done by a (pseudo)random number generator).

Some students have suggested that we have a review class tomorrow. I would like to know how many people want this. Of course, this would that we would finish bipartite matchings and the Chinese Postman Problem after the break. You can vote here. Please do not vote more than once (or for someone else). Apology in advance for transmitting your student number over unencrypted http.

Feb 15, 2010 Here are some places to find practice questions for the midterm (as well as my notes on how good I think they are).

The appendix that you will have available during the midterm (PS PDF) is now up. Please note that the appendix contains a lot of information and given the length of the midterm, it is impractical to read it all during the midterm. It is meant as a reference only (in case you forget one or two things during the midterm)! Please do not spend too much of your time reading through the appendix during the test. I would hate to see students do worse because I've added this.

Also, in case the announcement was not clear in class, the midterm covers the material up to last Friday (except for subjects explicitly mentioned as not being part of the course).

Notes on shortest path are now up (PS PDF). We essentially used lemma 2 when we saw the proof of correctness of Dijkstra's algorithm in class. But I forgot to mention it explicitly. The proof is straightforward and will be in assignment 4 (you do not need to know the proof for the midterm).

Feb 12, 2010 The solutions to assignment 2 (PS PDF) are now up.

If you still want to submit assignment 2 (late), you should talk to me today. I intend to post the solutions today (and it will not be possible to submit the assignment anymore after that).

Feb 11, 2010 Assignment 3 has been updated again with 2 bonus questions. The new due date is now March 5 (but it might be a good idea to still try to finish it by March 1 since that is when the next assignment will be posted).

Feb 10, 2010 Assignment 3 has been updated. A bonus question will be added soon.

Feb 8, 2010 The first 3 questions of assignment 3 (PS PDF) are up. There will be one more question added. It is due March 1.

Feb 6, 2010 The proof of optimality of Kruskal's algorithm in the notes on trees is correct. We just needed to look at the cycle containing f as a using only edges of F_i. Because F_i is contained in F^*, that cycle is actually contained in F^*.
Note that the proof we did see in class doesn't actually make use of the fact that e is the first edge not in F^*. So, in fact, we could have started with any edge e not in F^* (and not have to talk about the first iteration or F_i).

Feb 5, 2010 In a few classes, we will see the Chinese Postman Problem (this program also contains exercises for Eulerian paths and Hamiltonian cycle (for which there is no good algorithm in general, of course)). You can try to find good solutions before then. The server is not up yet though.

Notes on trees and minimum spanning trees (PS PDF) are now up. You can also look at chapter 10 of Rosen's book.

Feb 3, 2010 Someone has noted that the chapters of the book I have linked to are randomly order when seen in "Condensed List View" or "Expanded List View" (so that the chapter numbers do not correspond to the item numbers). However, they are correctly ordered in "Editorial View". The chapters I have referred to are titled "Graphs", "Trees" and "Finding the Optimum".

Notes on common errors in proofs (PS PDF) have been posted. Notes on trees and minimum spanning trees will be posted today or tomorrow. The book I had previously linked to also discusses trees (in more detail) and minimum spanning trees in chapters 8 and 9 respectively.

McGill's administration has made some policy announcements regarding all courses. Please be aware of these policies.

Feb 1, 2010 The notes on NP-completeness (PS PDF) and Gray codes (PS PDF) are now up. As usual, tell me if you find any errors. From the NP-completeness notes, for this class, you only need to know the definition of a polynomial time algorithm (but you might already know that from a different class).

For assignment 2, question 1, to re-clarify (because of questions I received), you can only use rules of inference to prove the argument if it is valid. That is, no truth tables, no equivalences, etc. If the argument is invalid, you can (and should) use truth tables. That solution should look similar to the solution provided for assignment 1 questions 2 and 3.

I will also post something about common errors in proofs to avoid (including errors in proofs by induction).

Jan 28, 2010 The notes on Hamiltonian cycles (PS PDF) are now up.

Jan 27, 2010 Assignment 2 (PS PDF) is up now. It is due Wednesday, Feb 10.

Jan 26, 2010 The solution to assignment 1 has been posted. Please contact me if you find any mistake.

There was a mistake in question 4c) which made it impossible. Question 4a) and 4b) are now each worth 5 point. Anyone who chose question 4 and did not answer 4c) (or wrote "not answered") will receive 1 bonus point.

Jan 25, 2010 Here is another "application" of Eulerian trails.

There is a chapter on graph theory and Eulerian circuits in this book which is available in electronic format to McGill student (chapter 7, starting at page 125, terminology differs slightly). The material is of course also available in Rosen's book in chapter 9.

Jan 22, 2010 I posted Sean Kennedy's notes for Monday's lecture on introductory graph theory and Nicolas Sonnerat's notes for Wednesday's lecture on bipartite matchings.

Please remember that assignment 1 is due in class today and there is a 10% penalty for each late day (not each late weekday).

Jan 15, 2010 I added another (long) example of a proof using rules of inference which also uses the "special" elimination rule of question 1. You can get it here PS PDF

Office hours next week will be Thursday Jan 21 from 2:00 pm to 3:30 pm in ENGMC 320 (of course, you can always ask to see me by appointment at a different time).

Jan 14, 2010 I have posted Neil Olver's notes on propositional logic (see the notes section). Although what was covered in the last two lectures (except possibly the examples) are also in the book.

Jan 13, 2010 If you choose to solve question 5b), you do not state every inference rules that you use (also, the rules we've seen may not be sufficient to solve it). However, it is good to show some of the less obvious deductions that you have made on your way to a solution. Alternatively, you could also provide an ordered list of deduction using this or otherwise. In that case, there is no need to annotate that list or provide anything else. Note that this program may still be buggy.

Someone has pointed out today that 5b) does not have a unique solution, but rather it has 4. For the purpose of this assignment, you only need to give any one of the 4 solutions. Note that knowing that there are 4 solutions beforehand probably doesn't help at all in this case.

Interestingly enough, there is a square on the grid which is currently empty but each of the 4 numbers 0,1,2,3 would force a different solution if we put it inside that square.

Jan 12, 2010 The notes have been updated with minor fixes, the added definition of argument, valid and invalid and a missing inference rule: Fe (contradiction elimination). Although it was possible to obtain this rule from the others (see Assignment 1 Question 4c)).
Notes for lecture 3 are now up.

Jan 11, 2010 Assignment 1 is posted. You can get it here (PS PDF)

Jan 8, 2010 The votes are in! The midterm will be Friday, February 19, 2010. The results

Jan 6, 2010 A preliminary version of the notes on rules of inferences has been posted. More to come soon. Please inform me of typos and errors. There are likely many at this point.

Instructor

Logic

Graph theory

Combinatorics

Complexity

Other

You are allowed to discuss assignment problems with other students as long as you acknowledge this at the beginning of your assignment (e.g., "I have collaborated with John Doe for question 1.") and write up your solutions individually. You should acknowledge people even if they are not in this class (if they were helpful for your assignment, of course). You should also acknowledge other resources used (e.g.,books and websites other than the course textbook website) if they were useful for completing the assignment.