Math 2602
Linear and Discrete Mathematics
Section F, Spring 2014



Handout
Click here for the handout from the first day.
Instructors
Prof. Dan Margalit
TAs: Rebecca Winarski, J.D. Walsh
Book
Class Meetings
 Lecture: Tuesday and Thursday, 12:051:25, CULC 102.
 Section F1 (Winarski): Monday and Wednesday 1:051:55, CULC 423.
 Section F2 (Walsh): Monday and Wednesday 1:051:55, CULC 129.
Office Hours
 Prof. Margalit: Monday 34, Tuesday and Thursday after class, and by appoinment in Skiles 244.
 Rebecca Winarski: Wednesday 121, Skiles 152
 J.D. Walsh: Monday 121, Skiles 149
Course Objectives
The main goals of this course are to learn how to prove mathematical statements, to solve mathematical problems, and to apply and analyze known theorems and algorithms in the subject areas of combinatorics, number theory, and graph theory.
TSquare
The course TSquare
site includes links to the course Grade book, Piazza site, and Announcements.
Clickers
The course will use Turning Point clickers. Student scores are based solely on their response rates. It is the student's responsibility to maintain a working clicker and to have it registered on TSquare.
Piazza
Piazza will be available on TSquare as an optional tool for online discussions about the course material.
Homework
Homework will primarily assigned via WebWork. It is generally due on Tuesday night at midnight and covers the previous week's material. Multiple attempts are usually allowed. Some weeks, there will be problems that are not graded, and hence do not count towards the final score.
Quizzes
Quizzes, again assigned via WebWork, are given before each class meeting, and are intended to check comprehension of the reading/viewing material. Multiple attempts are not allowed on the questions. For the quizzes you will be learning new material that has not yet been covered in class.
Write to Becca if you still need to sign up for a WebWork account. Send your gtlogin, recitation number (1 or 2), your email address, and your full name.
Reading, Viewing, Notes, Schedule, and Exams
Meeting 9
Date 
Topics 
Text Sections 
Videos 
Notes 
Jan 7 
Statements 
0.1 
Statements
Converse / contrapositive
Negation
Negation of conditional
Quantifiers

Meeting 1 
Jan 9 
Proofs 
0.2 
Direct proof
Proof by contradiction
Proof by contraposition
Proof by cases
Infinitude of the primes

Meeting 2 
Jan 14 
Truth tables / Logic 
1.11.2 
Truth Tables
Truth Tables for Conditional Statements
Truth Tables for Conditional Statements
Truth Table with 3 statements
Tautologies
Contradictions
Logical Equivalence with truth tables
Logical Equivalence without truth tables

Meeting 3 
Jan 16 
Binary relations 
2.32.4 
Binary Relations
Equivalence Relations
Equivalence Classes
Properties of Equivalence Classes

Meeting 4 
Jan 21 
Functions 
3.13.2 

Meeting 5 
Jan 23 
Cardinality 
3.3 
Cardinality of Sets
Infinite Sets
Different Infinities

Meeting 6 
Jan 28 
Congruence 
4.44.5 
Congruence
Reducing modulo n
Linear Congruence Equations
Chinese Remainder Theorem

Meeting 7 
Jan 30 
Midterm 1 
0.10.2, 1.11.2, 2.32.4, 3.13.3 

Solutions 
Feb 4 
Snow day 



Feb 6 
Induction 
5.1 
Proof by Induction
Proof by Induction

Meeting 8
Induction

Feb 11 
Snow day 



Feb 13 
Snow day 



Feb 18 
Recursive sequences 
5.25.3 
Arithmetic Sequences
Geometric Sequences
Recurrence Relations

Recurrence relations 
Feb 20 
Algorithms / Complexity 
8.18.3 
What is an algorithm?
Big O
Order of complexity

Meeting 10 Big O 
Feb 25 
Inclusionexclusion 
6.16.2 
InclusionExclusion
Multiplication and Addition Principles

Basics of counting 
Feb 27 
Midterm 2 
4.44.5, 5.15.3, 8.18.3 

Solutions 
Mar 4 
Pigeonhole principle 
6.3 
Pigeonhole Principle

Meeting 12 
Mar 6 
Permutations / Combinations 
7.17.2 
Permutations
Combinations

Meeting 13 Permutations and Combinations 
Mar 11 
Probability 
7.3 
Basic Probability
Probability (coin flips)
Probability (more than 2 outcomes)

Meeting 14 
Mar 13 
Bayes' Rule 
7.4 
Conditional Probability
Bayes' Theorem
Bayes' Theorem and Cancer Screening

Meeting 15 
Mar 25 
Repetitions 
7.5 
Permutations with Repetition

Meeting 16 
Mar 27 
Binomial Theorem 
7.7 
Pascal's triangle and binomial coefficients
Introducing Pascal's triangle
Patterns in Pascal's triangle

Meeting 17 
Apr 1 
Graphs 
9.19.3 
Konigsberg Bridge Problem
Graph Definitions
Bipartite Graph
Sum of degrees is twice the number of edges
Graph Isomorphism

Meeting 18 
Apr 3 
Midterm 3 
6.16.3, 7.17.5, 7.7 

Solutions 
Apr 8 
Euler / Hamilton Paths 
10.110.2 

Meeting 19 
Apr 10 
Shortest Paths 
10.4 
Weighted Graphs
Dijkstra's Algorithm

Meeting 20 
Apr 15 
Trees 
12.112.2 
Trees

Meeting 21 
Apr 17 
Spanning Trees 
12.3 
Spanning Trees
Krushkal's Algorithm
Prim's Algorithm

Meeting 22 
Apr 22 
Planar Graphs 
13.1 
Planar Graphs

Meeting 23 
Apr 24 
Graph Coloring 
13.2 
Graph Coloring

Meeting 24 
Apr 29 
Final Exam 
0.10.2, 1.11.2, 2.32.4, 3.13.3
4.44.5, 5.15.3, 8.18.3
6.16.3, 7.17.5, 7.7
9.19.3, 10.110.2, 10.4, 12.112.3, 13.113.2


Practice exam 




Course notes 
Grading
Final grades will be computed according to the following scale:

Quizzes  15% 
Clickers  10% 
Homework  25% 
Midterms  30% 
Final Exam  20% 

Absences
As a general rule, absences are excused for official Georgia Tech business only. I reserve the right to ask for a letter from the Dean of Students. In general, internships and interviews are not grounds for excused absences. If you have an official excuse for absence for an exam, you will be excused from that exam without penalty, meaning that your other exams will count for a larger portion of your grade.
Resources
TSquare
Math Labs, in Clough 280. Math 2602 TAs will be available on Mon 12, Tue 1112, Wed 23, and Thu 34.
Center for Academic Success, Drop in tutoring and oneonone tutoring
ADAPTS, Disabilities Services Program
Honor code