Fall 2022 - MATH 343 D100
Applied Discrete Mathematics (3)
Class Number: 4144
Delivery Method: In Person
Course Times + Location:
Mo, We, Fr 9:30 AM – 10:20 AM
AQ 5008, Burnaby
Exam Times + Location:
Dec 14, 2022
12:00 PM – 3:00 PM
AQ 5008, Burnaby
1 778 782-4699
Prerequisites:MACM 201 (with a grade of at least B-). Recommended: knowledge of a programming language.
Structures and algorithms, generating elementary combinatorial objects, counting (integer partitions, set partitions, Catalan families), backtracking algorithms, branch and bound, heuristic search algorithms. Quantitative.
This class focuses on combinatorial methods and algorithms for enumerating and generating various combinatorial objects, such as subsets, permutations, partitions, lattice walks, trees, graph traversals etc. For each family F of combinatorial objects, we ask the following. How can we count or generate all the objects of a given size? How can we search for an object with specific properties? Rather than focussing on fancy data structures or algorithm techniques (this would be the topic of a Computer Science class), our goal is to learn how to determine the underlying combinatorial structure of F, and use this information, together with some algebra, to count and efficiently generate the members of F. We will also discuss heuristic algorithms for searching less-structured families. Learning goals: As well as learning the beautiful interaction between recursive definition and polynomial algebra, students will be implementing some of the resulting algorithms using the Maple mathematical programming language, and its combinatorial packages. This software is available for free use to all SFU students. The student may select any of a number of topics for the course project.
Rough lecture schedule:
• Weeks 1,2,3,4,5: combinatorial specifications, recursive generation, Boltzmann sampling.
• Weeks 6,7,8: ranking, unranking, lexicographic generation, Gray codes
• Week 9: trees, Prufer encoding, Lagrange inversion¨
• Weeks 10,11: backtracking algorithms
• Weeks 12,13: heuristic algorithms
- Assignments 20%
- Midterm Exam 20%
- Project or Midterm 20%
- Final Exam 40%
THE INSTRUCTOR RESERVES THE RIGHT TO CHANGE ANY OF THE ABOVE INFORMATION.
Students should be aware that they have certain rights to confidentiality concerning the return of course papers and the posting ofmarks.
Please pay careful attention to the options discussed in class at the beginning of the semester.
This course is delivered in person, on campus. Should public health guidelines recommend limits on in person gatherings, this course may include virtual meetings. As such, all students are recommended to have access to strong and reliable internet, the ability to scan documents (a phone app is acceptable) and access to a webcam and microphone (embedded in a computer is sufficient).
Lecture notes will be provided.
Donald Kreher and Douglas Stinson
CRC Press, 1999
Recommended only and available online through the SFU Library.
REQUIRED READING NOTES:
Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.
ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS
SFU’s Academic Integrity website http://www.sfu.ca/students/academicintegrity.html is filled with information on what is meant by academic dishonesty, where you can find resources to help with your studies and the consequences of cheating. Check out the site for more information and videos that help explain the issues in plain English.
Each student is responsible for his or her conduct as it affects the university community. Academic dishonesty, in whatever form, is ultimately destructive of the values of the university. Furthermore, it is unfair and discouraging to the majority of students who pursue their studies honestly. Scholarly integrity is required of all members of the university. http://www.sfu.ca/policies/gazette/student/s10-01.html