Math 343, Applied Discrete Mathematics, Spring 2013

We will explore combinatorial classes by

• Meeting classical discrete objects
• Counting them
• Finding bijections between classes
• Generating random elements
• Using search algorithms on classes

Announcements

• Review questions for the final exam.
• Assignment 5 due date extended until Monday March 11 in class.
• Project guidelines. Important dates: choose project vs final by March 11, choose topic by March 18, due April 11.
• Midterm solutions.
• Midterm review questions and notes on the upcoming midterm.
• On Tuesday Jan 22 the 3:30-4:20 office hours are cancelled.
• More office hours: Tuesdays and Thursdays 10:00-10:20.
• Typo in assignment 1 corrected.
• I've requested a webct container for the use of its discussion list; it should appear in a few days.
• The midterm is Thursday, February 21 in class. An updated syllabus is below.

Assignments

1. Assignment 1, due Thursday January 17 in class. Solutions.
2. Assignment 2, due Thursday January 24 in class. Solutions.
3. Assignment 3, due Thursday February 7 in class. Solutions.
4. Assignment 4, due Thursday February 28 in class. Solutions.
5. Assignment 5, due Monday March 11 in class. Solutions.
6. Assignment 6, due Thursday March 21 in class. Solutions.
7. Assignment 7, due Thursday March 28 in class. Solutions.

Class Notes

I suggest you print out the lecture blanks and bring them to class.

The notes are something like a textbook appearing one section at a time and are based on notes by Marni Mishna. Let me know if you find any typos.

1. Lecture 1: notes and lecture blanks.
2. Lecture 2: notes and lecture blanks.
3. Lecture 3: notes and lecture blanks.
4. Lecture 4: notes and lecture blanks.
   Additional notes on other constructions.
5. Lecture 5: notes (no blanks as Steve will be lecturing)
6. Lecture 6: notes and lecture blanks and a text file of maple examples.
7. Lecture 7: notes and lecture blanks.
   Additional notes on labelled counting.
8. Lecture 8: notes and lecture blanks.
9. Lecture 9: notes and lecture blanks.
10. Lecture 10: notes and lecture blanks.
    On Monday February 18 we will discuss the midterm and do review questions.
11. Lecture 11: notes and lecture blanks and a maple function.
12. Lecture 12: notes and lecture blanks and a maple function.
13. Lecture 13: notes and lecture blanks and maple functions.
14. Lecture 14: notes and lecture blanks.
15. Lecture 15: notes and lecture blanks.
16. Lecture 16: notes and lecture blanks.
17. Lecture 17: notes and lecture blanks.
18. Lecture 18: notes and lecture blanks.
19. Lecture 19: notes and lecture blanks.
20. Lecture 20: notes and lecture blanks.
21. Lecture 21: notes and lecture blanks.
22. Lecture 22: notes and lecture blanks.
    On Thursday April 11 we will look at the review questions for the final.

References

1. Herbert Wilf, generatingfunctionology. Academic press (1990), 2nd edition (1994), 3rd edition AK Peters (2005)
2. Donald Kreher and Douglas Stinson, Combinatorial Algorithms. CRC Press (1999)

Information

Syllabus

Instructor:

Karen Yeats

Office:

SC K 10508

Email:

karen_yeats at sfu.ca

Office Hours:

10:00-10:20 and 3:30-4:20 Tuesdays; 10:00-10:20 and 1:30-2:20 Thursdays.

Lectures:

2:30-3:20 Mondays in AQ5018 and 2:30-4:20 Thursdays in WMC3510

Tutorial:

4:30-5:20 Tuesdays in WMC3253

There is no textbook for the course