back
Math 220: Finite Mathematics
Syllabus
Homework 1: (due Friday, 19 July)
Section 1.1: #1-4, 25, 26, 31, 32, 35, 36, 45, 53
Section 1.2: #1-8, 22-26, 44
Section 1.3: #1-3, 21-23, 36, 45
Section 1.4: #1, 17, 18, 31, 46, 49, 50
Section 1.5: #1, 3, 9, 10, 29, 30
Homework 2: (due Tuesday, 23 July)
Section 2.1: #3, 5, 8, 13, 21, 26, 40
Section 2.2: #5, 22, 35
Section 2.3: #12, 19, 23, 41
Section 2.4: #1, 16, 31, 42
(Notice that in 2.4 #31 they are telling you Euclid's postulate so that you can invoke it in your proof, you do not have to prove Euclid's postulate)
Review Problems for Quiz 1:
Chapter 1 Review: #1-13, 16-25, 31-58
Chapter 2 Review: #3-15, 17-20, 22-54
(This is most of the problems in the review section. I would recommend doing a few from each topic.)
Topics for Quiz 1: (this is a list of most topics which would be fair game for the quiz)
Statements and Truth Tables
Set Operations and Equality
Contrapositive and Negation of Statements (including those with quantifiers)
Venn Diagram representations of sets
Methods of Proof and Disproof (including but not limited to finding a counterexample, finding an example, contradiction, contrapositive, cases, direct, and showing set inclusion by choosing an arbitrary element of one set and showing it is in the other).
Homework 3: (due Tuesday, 30 July):
Section 3.1: #1, 3, 15-17, 37, 45
Section 3.2: #7, 8, 13, 27, 67
Section 3.3: #5, 23, 24
Section 3.6: #1, 2, 7
Also use section 3.1 #1 to formally show that for any integer n we have that n(n+1) is even (a fact that we used in class)
Notice that I have removed section 3.6 #55 from the homework assignment!
Review Problems for Midterm Exam: (on Thursday, 1 August)
All of the review problems for Quiz 1 (I would recommend being familiar with the problems on the quiz especially)
Chapter 3 Review: #1-10, 16-36, 53-60
Topics for Midterm: (including a few specific facts you should know)
All of the topics for Quiz 1
Divisors
Primes and Composites
Greatest Common Divisors
Well-Orderign Principle for the Integers
The Existence of Prime Divisors
The Division Algorithm
The Floor and Ceiling Functions
The Idea behind UPC and ISBN (you do not need to remember those formulas)
Binary Linear Codes (again, you do not have to remember the specific formula used in the book)
Shift Cyphers
GCD as a Linear Combination
Relatively prime iff a Linear Combination equals 1 (Cor. 3.14 form the text)
GCD Reduction
Euclid's Algorithm (including how to find the linear combination)
Euclid's Lemma
Modular Arithmetic
Properties of Modular Arithmetic (including Modular Cancellation and mult. inverses)
Linear Cyphers
Basic Properties and Definitions for Sequences
Homework 4: (due Wednesday, 7 August)
Sectoin 4.1: #3, 8, 31, 37
Section 4.2: #3, 17, 39
Section 4.3: #13, 17, 30
Section 4.4: #5
Section 4.5: #1, 5, 11, 16, 35
Section 4.6: #6, 25, 31, 39
Review Problems for Quiz 2:(on Thursday, 8th August)
Chapter 4 Review: #1-5, 6-14, 15-22, 24-50
Chapter 6 Review: #1-6, 8
Topics for Quiz 2:
Sequences (closed formulas and recursive formulas)
Sigma Notation
Standard Formula for known sums (From the text Thm 4.1, Thm 4.2 parts (a) and (b) only, and Thm 4.3)
Product Notation
Induction and Strong Induction as methods of proof
The Binomial Theorem
The Multiplication Principle for Counting
Homework 5: (Two parts, both due Wednesday, 14th August)
Part I:
Section 6.1: #41
Section 6.2: #14, 20, 21
Section 6.3: #3, 28
Section 8.1: #7
Part II: (optional for extra credit)
Section 8.1: #30, 33
Section 8.2: #3, 9
Section 8.3: #10
Section 8.4: #2, 5, 13
Section 5.3: #1, 6
Section 5.4: #1, 15
Topics to Study for Final Exam:
Statements and Truth Tables
Set Operations and Equality (including proving two sets are equal)
Contrapositive and Negation of Statements (including those with quantifiers)
Divisors and gcds (and the existence of prime divisors and standard factorization)
Primes and Composites
The Well-Ordering Principle for the Integers
The Division Algorithm
The fact that the GCD can be written as an integer linear combination
Two integers are relatively prime iff a linear combination of them equals one
Euclid's algorithm (including how to find the linear combination) and Eudlid's Lemma
Modular arithmetic and its properties (including cancellation and mult. inverses)
Sequences (including closed and recursive formula)
Sigma notation
Formula for sum of a constant and sum of just "i" (Don't worry about any of the higher powers such as i^2)
Product notation
Induction and Strong Induction as methods of proof (especially when used on sums with sigma notation or recursive sequences)
The Binomial Theorem
Basic Counting (including the mult. rule, permutations, combinations, and the Inclusion-Exclusion rule)
The Euler phi function
Definition a graph (and how to translate between a list of vertices and edges to a picture)
Definitions related to graphs (vertex, edge, loop, simple graph, subgraph, walk, cycle, distance, connected)
(you do not have to know: circuit, trail, path, induced subgraph)
Adjacency Matrices (and how to transfer back and forth between the matrices and the pictures)
Matrix multiplication (for 2x2 and 3x3 matrices that will probably have a moderate amount of zeros in them)
The fact that adjacency matrices are unique up to permutation (and what this means)
Powers of an adjacency matrix count walks of a certain length
Graph isomorphisms and automorphisms
Showing two graphs are isomorphic by stating an isomorphism
Graph invarients (number of edges, number of vertices, degree sequence up to order, maximal degree, minimal degree)
Showing two graphs are not isomorphic by finding an invarient on which they do not agree
The degree of a vertex
Two graphs are isomorphic iff there exists an ordering of each of their vertices such that they have the same adjacency matrix
The sum of the degrees is twice the number of edges (and be familiar with the three corollaries following this theorem on pg 462)
Function termonology (notation for a function, domain, range, codomain)(especially know the difference between the range and the codomain)
Be able to show when a function is not well-defined
Special Functions (injections, surjections, and bijections)
Good luck!