Math 2602

Linear and Discrete Mathematics

Section F, Spring 2014


Click here for the handout from the first day.


Prof. Dan Margalit

TAs: Rebecca Winarski, J.D. Walsh


Class Meetings

Office Hours

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.


The course T-Square site includes links to the course Grade book, Piazza site, and Announcements.


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 T-Square.


Piazza will be available on T-Square as an optional tool for online discussions about the course material.


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, 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 of conditional
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.1-1.2 Truth Tables
Truth Tables for Conditional Statements
Truth Tables for Conditional Statements
Truth Table with 3 statements

Logical Equivalence with truth tables
Logical Equivalence without truth tables

Meeting 3
Jan 16 Binary relations 2.3-2.4 Binary Relations
Equivalence Relations
Equivalence Classes
Properties of Equivalence Classes
Meeting 4
Jan 21 Functions 3.1-3.2 Meeting 5
Jan 23 Cardinality 3.3 Cardinality of Sets
Infinite Sets
Different Infinities
Meeting 6
Jan 28 Congruence 4.4-4.5 Congruence
Reducing modulo n
Linear Congruence Equations
Chinese Remainder Theorem
Meeting 7
Jan 30 Midterm 1 0.1-0.2, 1.1-1.2, 2.3-2.4, 3.1-3.3 Solutions
Feb 4 Snow day
Feb 6 Induction 5.1 Proof by Induction
Proof by Induction
Meeting 8
Feb 11 Snow day
Feb 13 Snow day
Feb 18 Recursive sequences 5.2-5.3 Arithmetic Sequences
Geometric Sequences
Recurrence Relations
Recurrence relations
Feb 20 Algorithms / Complexity 8.1-8.3 What is an algorithm?
Big O
Order of complexity
Meeting 10
Big O
Feb 25 Inclusion-exclusion 6.1-6.2 Inclusion-Exclusion
Multiplication and Addition Principles
Basics of counting
Feb 27 Midterm 2 4.4-4.5, 5.1-5.3, 8.1-8.3 Solutions
Mar 4 Pigeonhole principle 6.3 Pigeonhole Principle Meeting 12
Mar 6 Permutations / Combinations 7.1-7.2 Permutations
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.1-9.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.1-6.3, 7.1-7.5, 7.7 Solutions
Apr 8 Euler / Hamilton Paths 10.1-10.2 Meeting 19
Apr 10 Shortest Paths 10.4 Weighted Graphs
Dijkstra's Algorithm
Meeting 20
Apr 15 Trees 12.1-12.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.1-0.2, 1.1-1.2, 2.3-2.4, 3.1-3.3
4.4-4.5, 5.1-5.3, 8.1-8.3
6.1-6.3, 7.1-7.5, 7.7
9.1-9.3, 10.1-10.2, 10.4, 12.1-12.3, 13.1-13.2
Practice exam
Course notes


Final grades will be computed according to the following scale:

Final Exam20%


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.



---Math Labs, in Clough 280. Math 2602 TAs will be available on Mon 1-2, Tue 11-12, Wed 2-3, and Thu 3-4.

---Center for Academic Success, Drop in tutoring and one-on-one tutoring

---ADAPTS, Disabilities Services Program

---Honor code