EECS1019

EECS1019 MATH/EECS 1019: Discrete Math
Jeff Edmonds: Fall 2023-2024 A

Jeff, Readme, Marking, Times, Dates, Description,

Mental Health, EClass, Zoom, Forum, Videos, Survey

***************
1019 exam Fri Dec 15, 9am 1019 Exam TC SOBEYS
Old Exams
Review Slides
Practice Questions

Topics Jeff Ass Sol days Book Chpts Book Neal
Introduction ppt ppt ppt
Logic and proofs pdf
ppt pdf pdf 5+1 1.1-1.8
?1.3.5-7
? = optional, x = omit ppt
ppt
ppt 01 02 03
04 05
Sets, functions, infinity ppt 4-2 2.1-2.5
?2.2.4 x2.2.5&2.3.6 ppt 06 07
Growth of functions; big-O ppt 1 3.2 ppt 11
Induction (+structural) ppt 4-1 5.1-5.3
x5.2.4 Thm 1&5.3.5 ppt 08 09 10
12 12'
Recurrence Relations ppt pdf pdf 2 8.1-8.2
?8.1.3, Thm 4&5, 6 deg 2 ppt 18 19 20
Graphs ppt 4-1 10.1-10.5
x10.2.6 ppt 14 15 16
17 21
Relations (+equivalence) ppt 2 9.1&9.5
?9.1.5&9.3.3 ppt 13 14 20
Trees ppt pdf 2 11.1
?11.1.1 ppt 22

Request:
Jeff tends to talk too fast. Please help him go pole pole slowly.
Please ask questions.

Mandate:
       Teaching numerous courses has led me to believe that a lack of
       abstract and logical thinking, along with a shallow grasp of the big
       picture, is often the root cause of student struggles.
       To address this, I explain the same material from many perspectives,
       aiming for at least one to resonate with your subconscious.
       To ensure you aren't overwhelmed, I offer detailed insights on the
       main topic while keeping peripheral matters in a more relaxed context.

How to Study:
     Watch, Pause, Think, and Unpause the slides/videos.
     Try to solve things yourself.
     If you get stuck, watch for another slide or two.
     Repause it. Was that enough of hint so that you can now solve it?
     After watching the entire solution, ask yourself what you were missing.
     Maybe set all notes aside and see if you can now write up the solution on your own.

Readings:
Jeff's Logic Chapter
Discrete Mathematics Applications by Kenneth H. Rosen & Connect
Neal Madras & Suprakash Datta's slides
Additional exercises (not for grading)
Tutoring: mathlab, Math & Stat Help Center, note, Bethune Peer Tutoring Schedule
Resources from Rosen Book
     Self Assessment
     Instructions for using Connect
     Crib Sheets
     Common Mistakes in Discrete Math
     Advice on the Writing Projects
YouTube:
     logic, 1, all or 4, 6, 10-21
     Find us others.
Foundations of Computer Science
Discrete Math
More Jeff Topics
Jeff's Fun Stuff

Symbol Meaning:
ppt Power Point Slides
5 Video from this year's Math1019 (5min)

Introduction (ppt):
  Administrative Details How the course will be run.
  Summary of course Just a quick over view

Logic and Proofs (ppt) (More EECS1090):
- Propositional Logic: And, Or, Neg, Implies

- Predicate/Quantifier Logic: Forall object, Exists object
  Objects, Predicates, & Relations ∀x,y [Daughter(y,x) iff Parent(x,y) ∧ Female(y)]
    - Hugely Expressive Helps you understand and prove mathematical statements
  Intro to Quantifiers ∀x ≡ for All x  and   ∃x ≡ there Exists a y
     - Testing Validity An Infinite Iterative Algorithm
  Order of Quantifiers ∀x∃yP(x,y)   vs   ∃y∀xP(x,y)
    - So wrong ∀inputs x, ∃program J, J(x)=P(x)
  Understand as as a Game Prover provides ∃x, adversary ∀y, and oracle helps with assumptions
Example Proofs
    - Humans are Mortal "All humans are mortal" and "Socrates is human" hence "Socrates is mortal"
    - Reals ∃a∀x∃y x=a ∨ x×y=1
  Formal Proof System Arbitrary c vs Some c

- Removed

Sets, functions, carnality (ppt):
- Sets: Collects an ordered bunch of elements together.
   Examples Reals, integers, (a,b]={x|a<x≤b}
   Union, Intersection, ... A∪B={x|x∈A&x∈B}, A∩B={x|x∈A or x∈B}
   Cartesian Product, Power Set A×B={〈a,b〉|a∈A&b∈B}, P(S)=2^S={A|A⊆S}
   Subset, Equal A⊆B iff ∀x∈A x∈B, A=B iff ∀x∈A x∈B & ∀x∈B x∈A
   Inclusion-Exclusion |A∪B|=|A|+|B|-|A∩B|
   Proofs [A∪(B-A)]=[A∪B]
- Functions: f:A→B maps element x∈A to f(x)∈B
   Introduction A=domain, B=co-domain, range={y|∃x∈A,f(x)=y}⊆B
   Onto Every y∈B is mapped to. ∀y∈B,∃x∈A,f(x)=y.
   One-to-One y in B not mapped to twice. ∀x,x'∈A,[x≠x'→f(x)≠f(x')]
   Bijections both onto and one-to-one
   Inverses (one-to-one) f:A→B iff f^-1:B→A & f^-1(y)=x iff f(x)=y
   Function Operations (f₁+f₂)(x)=f₁(x)+f₂(x), (f₁∘f₂)(x)=f₁(f₂(x))
   Proofs If f₁ & f₂ are onto/1-1, then so is f₁∘f₂
   Graphs x vs y=f(x) like in high school
   Important Functions ⌊x⌋, ⌈x⌉, n!
- Sequences/Recurrences/Sums:
   Arithmetic 1+2+3+4+...+n=Θ(#terms×last), a_i=ci+b=a_i-1+c
   Geometric 1+2+4+8,...+2ⁿ=Θ(last), a_i=crⁱ=r×a_i-1
   Fibonacci 1,1,2,3,5,8,13..., a_i=a_i-1+a_i-2=1.618ⁱ
   Harmonic 1+¹/₂+¹/₃+¹/₄+...+¹/_n=Θ(logn), a_i=¹/_i
- Infinity:
   Countable (More EECS2001) S is countable if 1-1 function to integers if each element has a finite description
   Uncountable reals are uncountable because most element need an infinite description
   Uncomputable (More EECS2001) More problems than algorithms. The halting problem has no algorithm

Growth of functions; big-O (ppt)
         (We classify functions based on their rate of growth without giving too much detail.
   Growth Rates Θ(1). Θ(logn). Θ(n). Θ(n²). Θ(2ⁿ)
   Running Time (More EECS2011) Constant, binary search, sorting, feasible, every possible solution
   Classifying Functions Constant=Θ(1), Polynomial=n^Θ(1), Exponential=2^Θ(n)
   Notation n≪o(n²), n²≤O(n²), n²=Θ(n²), n²≥Ω(n²))
   Intuition 3(sin(n)+5)n²log(n)+7nlog¹⁰⁰(n)+5 = Θ(n²log(n)) ≤ O(n^2.001) ≤ n^O(1)
   Definition of Theta f(n)=Θ(g(n)) iff ∃c₁,c₂,n₀, ∀n≥n₀ c₁g(n)≥f(n)≥c₂g(n)
   Proofs 3n²+7n+5 = Θ(n²), 3n²+7n+5 ≠ Θ(n),
   Adding made easy. Σ_i=1..ni³ = Θ(#terms×last term) = Θ(n³)

Induction (+structural) (ppt):
- Induction: [S(0)&∀i[S(i-1)→S(i)]] → ∀iS(i)
  Counting Though we never reach all integers i, each i is eventually reached.
  Understanding Induction Though we never prove S(i) for all i, for each i, S(i) eventually is proved.
  Sums ∑_i=1..n i = ½ n(n+1)
  Special Prove that every positive integer is special.
  Faulty Proof All elephants in a given room are the same color.
  Counting, Inequalities, & Dividing # of subsets; 2ⁿ ≤ n!; n³-n is dividable by 3
- Strong Induction [∀i [(∀j<i S(j))→S(i)]] → ∀iS(i)
  Proof of Soundness Having is a proof of φ ensures that φ is valid.
- Loop Invariants: S(i) ≡ "My iterative algorithm's loop invariant is true in its ith iteration."
    - Establishing ⟨Pre-Cond⟩ & ⟨Pre-Code⟩ ⇒ ⟨Loop-Inv⟩
    - Maintaining ⟨Loop-Inv_t⟩ & ¬⟨Exit-Cond⟩ & ⟨Loop-Code⟩ ⇒ ⟨Loop-Inv_t+1⟩
    - Ending ⟨Loop-Inv⟩ & ⟨Exit-Cond⟩ ⇒ ⟨Post-Cond⟩
  Max in Array Max_{i∈[1..n] A[i]}
  Selections Sort Put the next element where it belongs
  Differential Equations Acceleration(t) = - Distance(i)
  Game of Life One day at a time
- Recursion: S(i) ≡ "My algorithm gives the correct answer on every input of size at most i."
  Friends Trust friends to solve any smaller instances meeting the pre-conditions
  Merge Sort Friends sort first and second halves and then I merge these solutions together.
  Tiling & Factoring L shaped pieces; 12 = 2 × 2 × 3
- Recursively Defined Structures
  Non-neg Integers Basis Step: Start with 0; Recursive Step: add n+1
  Balanced Parenthesis (()())
  No Adjacent 0's Let A_n be the set of all 0/1 strings of length n that do not have any adjacent 0's
  Well Formed Syntax ∀x∃yP(x,y)

Recurrence Relations (ppt):
   Recursive Algorithms T(n)=2T(n-1) → T(n)=2ⁿ
T(n)=2T(ⁿ/₂)+n → T(n)=Θ(nlogn)
   Thm 1b: Linear Relations Every solution to a_i=c₁a_i-1+c₂a_i-2 is a linear combination of any two different solutions
   Thm 5b: NonHomo Linear Relations Every solution to b_i=c₁b_i-1+c₂b_i-2+c is formed by adding in one fixed one.
   Thm 1a: Exponential Growth Two solutions are a_i = r₁ⁱ and a_i = r₂ⁱ for roots of a quadratic
   Thm 5a: Constant One solution is b_i = b
   Finances Solving b_i=1.05b_i-1-$20000

Graphs (ppt):
         (Graphs, ie nodes and edges, are very useful for representing
         data.

Relations (+equivalence) (ppt):

Trees (ppt):
         (A great data structure storing objects is a binary tree. If it is
         balanced than its depth is only log(n) with n nodes. Hence, operations
         are quick.)

Topics	Jeff	Ass	Sol	days	Book Chpts	Book	Neal
Introduction	ppt	ppt	ppt
Logic and proofs	pdf ppt	pdf	pdf	5+1	1.1-1.8 ?1.3.5-7 ? = optional, x = omit	ppt ppt ppt	01 02 03 04 05
Sets, functions, infinity	ppt			4-2	2.1-2.5 ?2.2.4 x2.2.5&2.3.6	ppt	06 07
Growth of functions; big-O	ppt			1	3.2	ppt	11
Induction (+structural)	ppt			4-1	5.1-5.3 x5.2.4 Thm 1&5.3.5	ppt	08 09 10 12 12'
Recurrence Relations	ppt	pdf	pdf	2	8.1-8.2 ?8.1.3, Thm 4&5, 6 deg 2	ppt	18 19 20
Graphs	ppt			4-1	10.1-10.5 x10.2.6	ppt	14 15 16 17 21
Relations (+equivalence)	ppt			2	9.1&9.5 ?9.1.5&9.3.3	ppt	13 14 20
Trees	ppt		pdf	2	11.1 ?11.1.1	ppt	22


Introduction (ppt):
	Administrative Details	How the course will be run.
	Summary of course	Just a quick over view

Logic and Proofs (ppt) (More EECS1090):
- Propositional Logic:		And, Or, Neg, Implies

- Predicate/Quantifier Logic:		Forall object, Exists object
	Objects, Predicates, & Relations	∀x,y [Daughter(y,x) iff Parent(x,y) ∧ Female(y)]
	- Hugely Expressive	Helps you understand and prove mathematical statements
	Intro to Quantifiers	∀x ≡ for All x and ∃x ≡ there Exists a y
	- Testing Validity	An Infinite Iterative Algorithm
	Order of Quantifiers	∀x∃yP(x,y) vs ∃y∀xP(x,y)
	- So wrong	∀inputs x, ∃program J, J(x)=P(x)
	Understand as as a Game	Prover provides ∃x, adversary ∀y, and oracle helps with assumptions
	Example Proofs
	- Humans are Mortal	"All humans are mortal" and "Socrates is human" hence "Socrates is mortal"
	- Reals	∃a∀x∃y x=a ∨ x×y=1
	Formal Proof System	Arbitrary c vs Some c

	- Removed

Sets, functions, carnality (ppt):
- Sets:		Collects an ordered bunch of elements together.
	Examples	Reals, integers, (a,b]={x\|a<x≤b}
	Union, Intersection, ...	A∪B={x\|x∈A&x∈B}, A∩B={x\|x∈A or x∈B}
	Cartesian Product, Power Set	A×B={〈a,b〉\|a∈A&b∈B}, P(S)=2^S={A\|A⊆S}
	Subset, Equal	A⊆B iff ∀x∈A x∈B, A=B iff ∀x∈A x∈B & ∀x∈B x∈A
	Inclusion-Exclusion	\|A∪B\|=\|A\|+\|B\|-\|A∩B\|
	Proofs	[A∪(B-A)]=[A∪B]
- Functions:		f:A→B maps element x∈A to f(x)∈B
	Introduction	A=domain, B=co-domain, range={y\|∃x∈A,f(x)=y}⊆B
	Onto	Every y∈B is mapped to. ∀y∈B,∃x∈A,f(x)=y.
	One-to-One	y in B not mapped to twice. ∀x,x'∈A,[x≠x'→f(x)≠f(x')]
	Bijections	both onto and one-to-one
	Inverses (one-to-one)	f:A→B iff f^-1:B→A & f^-1(y)=x iff f(x)=y
	Function Operations	(f₁+f₂)(x)=f₁(x)+f₂(x), (f₁∘f₂)(x)=f₁(f₂(x))
	Proofs	If f₁ & f₂ are onto/1-1, then so is f₁∘f₂
	Graphs	x vs y=f(x) like in high school
	Important Functions	⌊x⌋, ⌈x⌉, n!
- Sequences/Recurrences/Sums:
	Arithmetic	1+2+3+4+...+n=Θ(#terms×last), a_i=ci+b=a_i-1+c
	Geometric	1+2+4+8,...+2ⁿ=Θ(last), a_i=crⁱ=r×a_i-1
	Fibonacci	1,1,2,3,5,8,13..., a_i=a_i-1+a_i-2=1.618ⁱ
	Harmonic	1+¹/₂+¹/₃+¹/₄+...+¹/_n=Θ(logn), a_i=¹/_i
- Infinity:
	Countable (More EECS2001)	S is countable if 1-1 function to integers if each element has a finite description
	Uncountable	reals are uncountable because most element need an infinite description
	Uncomputable (More EECS2001)	More problems than algorithms. The halting problem has no algorithm

Growth of functions; big-O (ppt) (We classify functions based on their rate of growth without giving too much detail.
	Growth Rates	Θ(1). Θ(logn). Θ(n). Θ(n²). Θ(2ⁿ)
	Running Time (More EECS2011)	Constant, binary search, sorting, feasible, every possible solution
	Classifying Functions	Constant=Θ(1), Polynomial=n^Θ(1), Exponential=2^Θ(n)
	Notation	n≪o(n²), n²≤O(n²), n²=Θ(n²), n²≥Ω(n²))
	Intuition	3(sin(n)+5)n²log(n)+7nlog¹⁰⁰(n)+5 = Θ(n²log(n)) ≤ O(n^2.001) ≤ n^O(1)
	Definition of Theta	f(n)=Θ(g(n)) iff ∃c₁,c₂,n₀, ∀n≥n₀ c₁g(n)≥f(n)≥c₂g(n)
	Proofs	3n²+7n+5 = Θ(n²), 3n²+7n+5 ≠ Θ(n),
	Adding made easy.	Σ_i=1..ni³ = Θ(#terms×last term) = Θ(n³)

Induction (+structural) (ppt):
- Induction:		[S(0)&∀i[S(i-1)→S(i)]] → ∀iS(i)
	Counting	Though we never reach all integers i, each i is eventually reached.
	Understanding Induction	Though we never prove S(i) for all i, for each i, S(i) eventually is proved.
	Sums	∑_i=1..n i = ½ n(n+1)
	Special	Prove that every positive integer is special.
	Faulty Proof	All elephants in a given room are the same color.
	Counting, Inequalities, & Dividing	# of subsets; 2ⁿ ≤ n!; n³-n is dividable by 3
- Strong Induction		[∀i [(∀j<i S(j))→S(i)]] → ∀iS(i)
	Proof of Soundness	Having is a proof of φ ensures that φ is valid.
- Loop Invariants:		S(i) ≡ "My iterative algorithm's loop invariant is true in its ith iteration."
	- Establishing	⟨Pre-Cond⟩ & ⟨Pre-Code⟩ ⇒ ⟨Loop-Inv⟩
	- Maintaining	⟨Loop-Inv_t⟩ & ¬⟨Exit-Cond⟩ & ⟨Loop-Code⟩ ⇒ ⟨Loop-Inv_t+1⟩
	- Ending	⟨Loop-Inv⟩ & ⟨Exit-Cond⟩ ⇒ ⟨Post-Cond⟩
	Max in Array	Max_{i∈[1..n] A[i]}
	Selections Sort	Put the next element where it belongs
	Differential Equations	Acceleration(t) = - Distance(i)
	Game of Life	One day at a time
- Recursion:		S(i) ≡ "My algorithm gives the correct answer on every input of size at most i."
	Friends	Trust friends to solve any smaller instances meeting the pre-conditions
	Merge Sort	Friends sort first and second halves and then I merge these solutions together.
	Tiling & Factoring	L shaped pieces; 12 = 2 × 2 × 3
- Recursively Defined Structures
	Non-neg Integers	Basis Step: Start with 0; Recursive Step: add n+1
	Balanced Parenthesis	(()())
	No Adjacent 0's	Let A_n be the set of all 0/1 strings of length n that do not have any adjacent 0's
	Well Formed Syntax	∀x∃yP(x,y)

Recurrence Relations (ppt):
	Recursive Algorithms	T(n)=2T(n-1) → T(n)=2ⁿ
		T(n)=2T(ⁿ/₂)+n → T(n)=Θ(nlogn)
	Thm 1b: Linear Relations	Every solution to a_i=c₁a_i-1+c₂a_i-2 is a linear combination of any two different solutions
	Thm 5b: NonHomo Linear Relations	Every solution to b_i=c₁b_i-1+c₂b_i-2+c is formed by adding in one fixed one.
	Thm 1a: Exponential Growth	Two solutions are a_i = r₁ⁱ and a_i = r₂ⁱ for roots of a quadratic
	Thm 5a: Constant	One solution is b_i = b
	Finances	Solving b_i=1.05b_i-1-$20000

Graphs (ppt): (Graphs, ie nodes and edges, are very useful for representing data.

Relations (+equivalence) (ppt):

Trees (ppt): (A great data structure storing objects is a binary tree. If it is balanced than its depth is only log(n) with n nodes. Hence, operations are quick.)