Linear and Discrete Mathematics

Spring 2005

MWF 10:05 - 10:55 Skiles 140
TTh 10:05 - 10:55 A. French 101

Course Information

Syllabus
Textbook: Linear and Discrete Mathematics, Third Edition Stephen B. Maurer & Anthony Ralston
Georgia Tech resources on Linear Programming

---

Homework

Week #2 (Jan 17 - Jan 21)

Section 0.1: 5, 10, 11, 12, 13, 14, 15, 16, 18, 31, 32, 33, 34, 35
Section 2.2: 3, 5, 6, 7, 8, 9, 11, 19, 20, 23, 24, 25, 28, 30

Tuesday January 18

• Advani 0.1.33cde
• Atchison 0.1.34afg
• Awofadeju 0.1.35

Thursday Janurary 20

• Bertran 2.2.5
• Bogue 2.2.20
• Brannon 2.2.24ad

Week #3 (Jan 24 - Jan 28)

Section 2.3: 4, 7, 9, 18, 20, 22, 24
Section 2.5: 25, 26, 27ac, 28
Section 2.6: 4, 5, 6
Section 2.8: 1, 2, 3, 8, 12, 16, 23, 28
Section 4.2: 3, 6, 7, 10, 12, 24, 25, 26

Tuesday January 25

• Byrd 2.3.24
• Carey 2.5.26

Thursday Janurary 27

• Chang 2.8.12
• Castro 4.2.12
• Coil 4.2.25

Week #4 (Jan 31 - Feb 4)

Section 4.3: 2, 4, 6, 10, 19, 28, 29
Section 4.4: 3, 6, 7, 8,
Section 4.5: 2, 4, 10, 14, 15, 20
Section 4.6: 4, 8, 9, 30, 34, 35
Section 4.7: 2, 7, 9, 10, 15, 20

Tuesday Febuary 1

• Conner 4.3.6
• Ditzler 4.3.28
• Dusterdieck 4.5.4

Thursday Febuary 3

• Hazell 4.5.20
• Hibbard 4.6.35
• Ingco 4.7.10

Week #5 (Feb 7 - Feb 11)

Section 4.3: 30, 31, 33, 34, 35, , 36, 37, 38
Section 4.9: 3, 4, 7, 8, 29 (not on Test #1, also not necessary if you are comfortable with algorithms)
Section 4.10: 6, 9, 13, 14, 18
Section 0.3: 1, 5, 6, 7, 8, 9, 12, 13, 15, 16, 18, 22, 24, 26abde, 27 (not on Test #1)

Tuesday Febuary 8

• Manley 4.3.35
• McMillian 4.10.13
• Meggs 4.10.14

Thursday Febuary 10

• Test #1

Friday Febuary 11

• Morehead 0.3.12
• Oluwo 0.3.15
• Orkin 0.3.16
• Patel 0.3.22
• Powell 0.3.24

Week #6 (Feb 14 - Feb 18)

Section 3.1: 2, 3, 4, 5, 6, 7, 13, 19, 23, 24

Thursday Febuary 17

• Pratt 3.1.5
• Sabot 3.1.6
• Safir 3.1.7

Week #7 (Feb 21 - Feb 25)

Section 3.1: 21, 24, 26, 31
Section 3.3: 1, 2, 3, 9, 16, 22 ,25, 28, 29, 31, 32, 33, 34, 38, 39

Tuesday Febuary 22

• Sinagra 3.1.21
• Sokan 3.1.31
• Sweet 3.3.9

Thursday Febuary 24

• Snow 3.3.22
• West 3.3.28
• Wong 3.3.34

Week #8 (Feb 28 - Mar 4)

Section 3.2: 2, 3, 4, 8, 10
Section 3.4: 1, 7, 8, 9, 11, 12, 22(and solve), 23, 26
Section 3.7: 2, 6, 7, 14, 15, 16, 18, 20, 21

Tuesday March 1

• Young 3.2.4
• Advani 3.2.10
• Atchison 3.4.22(and solve)

Thursday March 3

• Awofandeju 3.4.23
• Bertran 3.7.20
• Bogue 3.7.21

Week #9 (Mar 7 - Mar 11)

Chapter #3 Supplementary: 1, 3, 10abc, 24, 34, 35
Week 9

Tuesday March 8

• Brannon Supplement:1
• Byrd Supplement:3
• Carey Supplement:10a

Thursday March 10

• Castro Supplement:35
• Chang Homework#1:1
• Coil Homework#1:3

Week #10 (Mar 14 - Mar 18)

Week 10

Tuesday March 15

• Ditzler Homework#2:2
• Duesterdieck Homework#2:3
• Hazell Homework#2:4

Thursday March 17

• Test #2

Week #12 (Apr 4 - Apr 8)

Week 12

Tuesday April 5

• Hubbard Homework#3:1
• Ingco Homework#3:2
• McMillen Homework#3:3

Thursday April 7

• Meggs Homework#3:4
• Morehead Homework#3:5
• Oluwo Homework#3:6

Week #13 (Apr 11 - Apr 15)

Week 13

Tuesday April 12

• Orkin Homework#4:1
• Patel Homework#4:2
• Powell Homework#4:3

Thursday April 14

• Pratt Homework#4:4
• Sabot Homework#4:5
• Safir Homework#4:6

Week #14 (Apr 18 - Apr 22)

Week 14

Tuesday April 19

• Sinagra Homework#5:1
• Snow Homework#5:2
• Sweet Homework#5:3

Thursday April 21

• Test #3

Week #15 (Apr 25 - Apr 29)

Week 15

Tuesday April 19

• West Chap 2: Suplmentary #5
• Young Chap 3: Suplementary #22
• McMillen Chap 4: Suplementary #2

Thursday April 21

• Hubbard Chap 4: Suplementary #3
• Oluwo Chap 4: Suplementary #19ab
• First Come First Serve

Schedule

Monday Jan 10 - Set Notation, Cantor's Diagonalization Proof
Wednesday Jan 12 - Induction
Friday Jan 14 - The Towers of Hanoi (more detailed explanation)
Wednesday Jan 19 - Strong Induction, Euclidean Algorithm
Friday Jan 21 - Counting, Permutations (Distinguishable, Indistinguishable, and Circular)
Monday Jan 24 - Combinations
Wednesday Jan 26 - Combinatorial Identities, Pascal's Triangle
Friday Jan 28 - Coumbinations with repition
Monday Jan 31 - Inclusion Exclusion, Euler's Phi Function (Additional information on RSA)
Wednesday Feb 2 - Inclusion Exclusion continued
Friday Feb 4 - The Pidgeonhole Principle, Random permutations
Monday Feb 7 - "Big-Oh" notation and order notation
Wednesday Feb 9 - Ordering the order notations
Monday Feb 14 - Introduction to Graph Theory
Tuesday Feb 15 - Euclidean Cycles
Wednesday Feb 16 - Test #1 Returned
Friday Feb 18 - Dijkstra's Algorithm
Monday Feb 21 - Dijkstra's Algoirthm, Adjacency Matrix
Wednesday Feb 23 - Adjacency Matrix and Connectivity, All pairs shortest path, Floyd-Warshall Algorithm
Friday Feb 25 - Trees, Forests, and Spanning Trees
Monday Feb 28 - Kruskal's and Prim's algorithms
Wednesday Mar 2 - Approximate solutions to metric TSP
Friday Mar 4 - Planar graphs and Kuratowski's Theorem
Monday Mar 7 - Matching and Hall's Theorem
Wednesday Mar 9 - M-alternating and M-augmenting paths and maximum matching
Friday Mar 11 - Algorithm Review
Monday Mar 14 - Algorithm Review Continued
Wednesday Mar 16 - Social Networks MEJ Newman Social Network Pictures
Friday Mar 18 - Matrix Inversion and the Sherman-Morrison-Woodbury Formula
Monday Mar 28 - Introduction to Linear Programming
Wednesday Mar 30 - Linear Programming and Graphs
Friday Apr 1 - The geometry of LP and graphical solutions
Monday Apr 4 - Characterization of feasible region in terms of rays and vertices
Wednesday Apr 6 - Characterization of vertices of standard form LP, the dual linear program
Friday Apr 8 - Examples of LP duality, Max-flow, Min-cut Theorem Monday Apr 11 - Simplex Method
Wednesday Apr 13 - Simplex Method continued
Friday Apr 15 - Full Tableau Simplex Method
Monday Apr 17 - Full Tableau Simplex Method continued
Wednesday Apr 19 - Test Review
Friday Apr 21 - Project Start