Solutions to all problems available before tests.

Prahladnarasim.Kasthurirangan@stonybrook.edu, grade HW with last names A-H; office hours: Monday, Fri 12:30-1:30 pm.

Jared.Leonard@stonybrook.edu, grades last name J-R; office hours: Mon,Wed 9:15-10:15am (Zoom only)

Yikun.Zhou@stonybrook.edu, grades last name S-Z; office hours: Mon, Wed 2-3pm

Americans with Disabilities Act: If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Student Accessibility Support Center, ECC(Educational Communications Center) Building, Room 128, (631)632-6748. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.

Academic Integrity: 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. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology & Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. 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.

Learning outcomes for AMS 3031.) Develop skill with proofs in graph theory (this is the only Applied Math course that teaches proofs), including: * the careful use of definitions and stated conditions, and their consequences; * direct arguments; * indirect arguments, i.e., proof by contradiction; * proof with generalized figures. 2.) Examine graph theory topics in greater depth (than AMS 301) with a focus on studying and extending theoretical results: * general graph properties; * planar graphs; * graph coloring, including edge and face coloring. 3.) Understand the theory behind Polyas Enumeration Formula and use this understanding in applied problem-solving. 4.) Develop the network algorithms for: * maximal minimal flows; * maximal matching; * the transportation problem. 5.) Understand the set-theoretic constructions underlying the theory of progressively finite games and apply this knowledge to develop winning strategies for such games: * kernel of a game; * level-by-level construction; * Grundy functions; * direct sums of games, including Nim. 6.) Use combinatorial reasoning to efficiently solve cryptograms based on keyword transpose encodings; extend this reasoning to solve polyalphabetic codes.COURSE OUTLINE:See Corrections of 6th edition of Applied Combinatorics for errors Week 1-2:Aug 23- Aug 30:Applied Combinatorics Chapter 9, sect 1,2,3,4ug 23-Aug 30 Lecture Notes for Chap. 9 (Applied Combinatorics) Homework 1 (due 9/1):Applied Combinatorics 9.1: 5c,10bc; 9.2: 3,4,10; 9.3: 4ac,5de,7de; 9.4: 2bcd,3 (write the whole polynomial out term-by-term), 7de, 9ab Week 2-4 -- Sep 1 - 13: A.C. Chapter 4 Lecture Notes for Chap. 4 (Applied Combinatorics) Homework 2 (due 9/15):4.1: 4,(delete 'total' in line 2),9; 4.2:2,5; 4.3: 2ab,3,6,8,9,12,21; 4.4: 2,4,5,8; 4.5:4a,6a Week 5 -- Sep 15-20:Chapter 10 Lecture Notes for Chap. 10(Applied Combinatorics) Homework 3 (due9/22):10.1: 1ab,3,8ab,12a,15; 10.2: 1abc,2abc,3ab,4ab, 6ab Week 6 -- Sep 22- 27: Review and 1st Test (test on Sep 27th) Past First Tests and Solutions Past First Tests without Solutions Solutions to Homeworks 1,2,3 The course now switches to Wilson's Introduction to Graph Theory (5th edition). Week 7-- Sep 29-Oct 4: Intro to Graph Theory, Chapt 1&2 (skip sect 1.3) Lecture Notes for Chap. 1 Lecture Notes for Chap. 2 Homework 4 (due10/6):Chapt 1: #15,16,29 (skip k-cube), 31, Chapt 2: #3(skip part v),5 ,9(i), plus #33 on p. 48 of the Applied Combinatorics text. Week 8-- Oct 6-13: Chapt 4 Lecture Notes for Chap. 4 Homework 5 (due10/18):Chapt 4: 5(ii),8,10,13,14,15,16,17,18,19 plus #24 on p. 43 of Applied Combinatorics text Week 9-- Oct 18-20: Chap 5.1,5.3 and Review for QuiZ Lecture Notes for Chap. 5 Homework 6 (due10/25) Chapt 4: 22,23,24,25};Chapt 5: #1, 4(i)(ii), 7,8, 19 ,21,22,24 AMS 303 Old Quiz Questions and Solutions Week 10- Oct 25-27): Chapt 5, Quiz on Oct 27. Homework 7 (due11/1):Chapt 5: #9, 12, 25, 28, 31. Week 11- Nov 1-3: Review and Test 2 (Test 2 on Nov 3th) (you are allowed a 2-sided page of definitions and statements of theorems-- no proofs, no solutions to HW problems)) Past Second Tests and Solutions Solutions to Homeworks 4,5,6 (with old numbering 1,2,3

Week 12-15 Nov 8 - Dec 1: Postlude- Cryptanalysis Read the Postlude in the text before Tuesday's class. Homework to finish for class (do before class) Nov 8:: XTEIA DSL ASQA FKSF FKY IVYOPYUJQ NI PAY NI LNVRA TU SMYVTJSU UYLAESEYV YUCDTAK SUR FKYTV VSUG NVRYV SVY JDNAYDQ VYDSFYR Nov 10: Postlude problem #2 (Error in text, the repeated sequence is JPLENFYV -the L was missing) Nov 15: Postlude problem #3 Nov 17: Receive takehome cryptogram- due Dec 13 by 4 pm (for details, see below) Spring 2022 File with Everyone's TakehomeProject The following link explains the ways polyalphabetic encoding works Polyalphabtic Encoding The following link to frequency strips will be used in class to illustrate solving polyalphabetic codes Sample Frequency Strips The following links are helpful in the takehome project Template for Keyword Tables Template for Aligning Alphabets If you are having a problem, this file covers 99% of issues. PLEASE READ Tips for Takehome Final Take-Home Final due on Dec 13 by 4 pm . FOR FULL CREDIT: submit decoded cryptogram to Prof. Tucker by email along with pictures of aligned alphabets and trigraph table for collapsed cryptogram.

- approximately 35% A's, 40% B's, 20% C's, 5% D's,F's&W's