AMS 301 FINITE MATHEMATICAL STRUCTURES

Fall 2018

Class Time and Place: TuTh 2:30 - 3:50 pm, Eng 143
Instructor: Prof. Alan Tucker
Offices: Eng 127 (back right office)
Office Hours: Tu 1:00-2:20 pm , Wed 11 am - 1 pm, and F 10am - noon or by appointment
How to Reach Prof. Tucker: telephone: 2-9941; e-mail: alan.tucker@stonybrook.edu
Course Text: Applied Combinatorics, Sixth Edition, by A.Tucker, John Wiley & Sons.
Tests: three hour Tests (31%,31%,23%), the last one during final exam week.
Homework: Assigned weekly and submitted through Blackboard; graded out of a maximum score of 5; Counts for 15% of course grade; Solutions to all problems available before tests.
Weekly Assignments Listed Below.

Graders Unless otherwise noted, office hours are in the AMS Help Room in Harriman 132.
> Guilherme.Larangeira@stonybrook.edu MW 1-2pm; grades students with last names starting with A-D
Shaopeng.Chen.1@stonybrook.edu , Wed 2-4 pm, grades last names E-J
Jingtong.Huang@stonybrook.edu , Monday 2-4 pm, grades last names K-N
Ruishi.Wang@stonybrook.edu MW 8:30-9:30 am, grades last names O-S
jiarui.zhang.1@stonybrook.edu, TuesThur 11:30-12:30, grades last names T-Z
Students with disabilities or who need special assistance with exams or other aspects of the course are asked to let Prof. Tucker know about their circumstances at the beginning of the course.
Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http: //www.stonybrook.edu/uaa/academicjudiciary
Critical Incident Management: Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the school of Medicine are required to follow their school-specific procedures. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.
Mastermind Extra Credit:In the first month of the course, there will be weekly Mastermind puzzles posted on this webpage each Thursday night at 10:00 pm. Mastermind is explained in the Prelude at the front of the textbook. The first five students to email the correct solution (with an explanation of their reasoning) will get 3 extra points on the first test; the next five students to e-mail me the correct sequence will get 2 extra points on the first test and the next 5 students will get one extra point on the first test.

Learning Outcomes for AMS 301
1.) Strengthen logical reasoning skills to solve combinatorial problems using:
        * elements of propositional calculus;
        * proof by contradiction;
        * logical consequences of assumptions.
2.) Learn to find multiple (equally valid) ways to solve a combinatorics problem
        * apply a top-down strategy (breaking a problem into parts and subparts)
        * apply a bottom-up strategy (solving special subcases and building up).
        * learn to solve problems from first principles, rather than looking for existing templates or formulas.
        * solve a complementary problem;
        * use different strategies to categorize subcases of a problem;
3.) Learn basic graph theory results and apply them in problem-solving: 
        * isomorphism; 
        * planar graphs; 
        * Hamilton circuits and Euler cycles;
        * graph coloring; 
        * trees and ways to search them.
4.) Use formulas for counting basic combinatorial outcomes to construct solutions to more complex combinatorial enumeration problems:
        * permutations, with and without repetition;
        * combinations, with and without repetition.
5.) Apply counting strategies to solve discrete probability problems.
6.) Use specialized techniques to solve combinatorial enumeration problems:
        * generating functions; 
        * recurrence relations; 
        * inclusion-exclusion principle.

COURSE OUTLINE:
NOTE THAT PROBLEMS ARE FROM THE SIXTH EDITION OF THE TEXTBOOK. THE NUMBERING AND WORDING OF MANY PROBLEMS IS DIFFERENT IN EARLIER EDITIONS. See Corrections of 6th and 5th editions of Applied Combinatorics for errors in the text and errors in Odd-Numbered Answers. Week 1 -- Aug 28- 30: Graph Theory Basics, Isomorphism-- Section 1.1,1.2,1.3 Homework (due 9/4): Sect 1.1: 1,6,9,14,16,20,23; Sect. 1.2: 4,5bck,6cdf,7; Sect. 1.3: 1,6,10, 12b. Week 2 -- Sept 4-6 : Planar Graphs, Euler Cycles-- Section 1.4, 2.1 Homework (due 9/11): Sect. 1.4: 3bh,7befgh,8,11,15,16,20,25; Sect. 2.1: 2,4,9,10. WeeK 3 -- Sept 11-12: Hamilton Circuits, Graph Coloring--Section 2.2, 2.3, 2.4 Homework (due 9/18): Sect. 2.2: 3,4bjko,7b,9,16; Sect 2.3: 1bcgl, 14,15; Sect 2.4: 7a. Week 4 -- Sept 18-20: Trees and Searching-- Section 3.1 Homework: (due 9/25): 1a,4,6,11,13,19,25,29; Sect 3.2: 1ab,4,5,16b,25. Week 5 -- Sept 25-27: Traveling Salesperson Problem and Review--Section 3.3 Homework OPTIONAL (for your own practice): Sect 3.3: 1,5 Week 6 -- Oct 2-4 Further review and First Test (Oct 4th) Fall 2018 First Test Spring 2018 First Test Fall 2017 First Test Spring 2017 First Test Solutions to Old First Tests Solutions to Homeworks Week 7 -- Oct 11-16: Basic Permutations and Combinations-- Section 5.1, 2 Homework (due 10/18): Sect.5.1: 6,7,9,12,13,16abc,20,22,25,26,33,36; Sect 5.2: 4,5,8,10,16bcd,29,48,53,69A Week 8 -- Oct 18-23: Counting Problems with Repetition-- Sections 5.3,5.4, Homework (due 10/25): Sect 5.1: 24,29,30; Sect 5.2: 32,38,55; Sect 5.3: 2,4,5,7,9,12,21; Sect 5.4: 2,3ab,7,10,12,27 Week 9- Oct 25- 30: Generating Function Models-- Section 6.1,4 Homework (due 11/1): Sect 5.2: 26,46 56; Sect 5.3: 15,19,22; Sect. 5.4: 11,19,21,28,47,48; Sect 6.1: 2b,4bc,6,7,10; 6.4: 1,2,3 Week 10- Nov 1-6: Evaluating Generating Function Coefficients-- Section 6.2,4 Homework (11/8): Sect 6.1: 3ac,8,13,16: Sect 6.2: 1,2,5,13,15b,17ab,20,22; Sect. 6.4: 6, 7a Week 11-- Nov 8-13: Review and Test 2 (Test Nov 13th) Old Second Tests Solutions to Old Second Tests Solutions to Homeworks Week 12-- Nov 15-20: Recurrence Relations-- Section 7.1, 7.3 Homework (due 11/27): Sect. 7.1: 2,4,6ab,7,11,12,15,19,20, 28, 30; 7.3:1,2,3A Week 13-- Nov 27-29: Inclusion-Exclusion Principle-- Section 8.1, 8.2 Homework (due 12/4): Sect. 8.1: 9,10,11,12,15,16,24,26,29,36; Sect. 8.2: 2,5,8,11,13,15,19,23b Week 14-- Dec 4-6: Rook Polynomials and Review for third test-- section 8.3 Homework (due:12/11): 8.2: 31,32; 8.3: 2b, 4, 6. Finals Week-- THIRD TEST IS HELD AT THE ASSIGNED TIME FOR THE FINAL EXAM (but just one-hour long, Tue 11:30am - 12:30pm; in regular classroom Eng 143. Solutions Old Third Tests Old Third Tests Solutions to Homeworks
Historical Curve in Prof. Tucker's AMS 301 classes:
approximately 25% A's, 40% B's, 25% C's, 10% D's,F's & W's