##### Lecture 1 • 2017/09/05
• A language L is any subset of Σ*, which represents all sequences of elements from a finite set Σ
• An algorithm A decides a language L by answering if x ∈ L
• Languages that we can decide = languages that we can describeall languages
• Decided languages and described languages are similar in size (#ℕ), but both are much smaller than the total available # of languages (#ℝ)
• Two sets have the same cardinality if there exists a one to one mapping with all elements from set A to set B without any remaining elements in either sets
• PCP – Post Correspondence Problem – Given tiles with a top sequence and a bottom sequence, find a sequence of such tiles (using any number of any tile) where the concatenated top sequence matches the concatenated bottom sequence
• PCP cannot be decided by any algorithm in a finite amount of time when there are no valid sequences
• Proof by reduction technique – if PCP was decidable, then another undecidable problem (the halting problem) would be decidable
• The Halting Problem – Given an algorithm and an input, will the algorithm halt on that input or will it loop forever?
• Algorithms can be fed an input matching their algorithm to return an incorrect response; no algorithm can be always correct
• Syracuse Conjecture – For any integer n > 0, where S1 = n, Si+1 = if (Si % 2 == 0) Si/2 else 3Si + 1, Syracuse(n) = lease i such that Si = 0 if Sk > 1 for all k in [1, i)
##### Lecture 2 • 2017/09/07
• Syracuse Conjecture – ∀n[n > 0 ⇒ Syracuse(n) > 0]
• Not all simple looking problems can be easily solved; for instance: x/(y + z) + y/(x + z) + z(y + z)
• NP-Complete Problems
• If any of them is easy, they are all easy
• In practice, some of them have special cases which may be more efficiently solved
• 3-colouring of Maps; hard to solve (no known efficient algorithm), but are easy to verify
• SAT – given boolean formula, is there an assignment to make the formula evaluate to true?
• Travelling salesman – given cities & distances between them, what is the shortest route to visit each city once?
• Knapsack – given items with various weights, is there a subset with total weight K?
• P – Tractable problems – Solvable in polynomial time
• Some problems may be efficiently solvable, but algorithm may not be provable
• 2-colorability of maps
• Primality testing (probably not factoring)
• Solving N x N x N Rubik's cube
• Finding word in dictionary
• Sorting elements
• NP-hard – broader term for NP questions that do not fall in the category of a language
• PSpace Completeness – problems requiring reasonable (Poly) amount of space to be solved, but may use very long time
• Finite-State Automata – simple model where there can be exactly one of a finite number of states at any given time
• Example: swinging door, elevator
• DFA – deterministic finite automaton, 5-tuple (Q, Σ, δ, q0, F)
• States – finite set Q (circle)
• Alphabet – finite set Σ, defines a language (letters)
• Transition function – explicit representation mapping states & alphabets to states (δ = Q x Σ → Q)
• Start state – special state representing entry point, q0 ∈ Q (arrow to state)
• Accept states – decision making state, F ⊆ Q (double circle)
##### Lecture 3 • 2017/09/12
• Next tuesday's class is cancelled
• Prof. Crépeau's office hours are cancelled next week
• Regular Languages
• Given definition from last class, and let w = w1w2...wn (n ≥ 0) be a string where each symbol wi is from the alphabet Σ
M accepts w if states s0,s1,...sn exist s.t
• s0 = q0
• si+1 = δ(si, wi+1) for i = 0, ... n – 1
• sn ∈ F
• (w is accepted if it starts at the start state and ends at an accept state)
• Note that the size of the state is typically one greater than the size of the string
• M recognizes language A if A = { w | M accepts w }
• A language is a regular language if some finite automaton recognizes it
• [Went through example proof by induction]
• ε represents an empty string
##### Lecture 4 • 2017/09/14
•  Regular Operations Union A ∪ B { x | x ∈ A or x ∈ B } Concatenation A ∘ B { xy | x ∈ A and y ∈ B } Star A* { x1x2 ... xk | K ≥ 0 and each xi ∈ A }
• Non-Deterministic Finite Automata
• May jump from state to state without consuming input (eg when encountering the empty string ε)
• Definitions are similar to DFA, except that:
• Alphabet – also includes an empty string ε
• Transition function returns P(Q), which is a subset (partition) of Q that meets the requirements
##### Lecture 5 • 2017/09/21
• (No class on 19th
• Minimization of DFA
• Lumping (quotient by an equivalence relation) – if two states lead to the same state(s) at all times, and are the same 'state' themselves, they may be merged together as their difference is forgotten after the next step.
•  ~ (equivalence relations) are Reflexive ∀x x ~ x Symmetric ∀x,y x ~ y ⇒ y ~ x Transitive ∀x,y,z x ~ y, y ~ z ⇒ x ~ z
• S/~ represents [s] = { x | x ~ s }
• δ(s, a) – state you went to after reading alphabet a at state s
• δ*(s, w) – state you went to after reading all letters in word w, starting at state s
• M = (s, s0, δ, F)
L(M) = { w | δ*(s0,w) ∈ F }
• Def p, q ∈ S are equivalent (p ≈ q) if
∀w ∈ Σ*    δ*(p,w) ∈ F ⇔ δ*(q,w) ∈ F
• Lemma A
• p = q ⇒ ∀a ∈ Σ    δ(p,a) ≈ δ(q,a)
• Note that p ≈ q can be written [p] = [q] (comparing equivalence classes
• Therefore: [p] = [q] ⇒ [δ(p,a)] = [δ(q,a)]
• For a new machine M' = (s', s0', δ', F')
• s' = s/≈
• s0' = [s0]
• δ'([s],a) = [δ(s,a)]
• F' = { [s] | s ∈ F }
• Lemma B
• if p ∈ F & q ≈ p, then q ∈ F
• Lemma C
• ∀w ∈ Σ*    δ'*([p],w) = [δ*(p,w)]
• Proof by induction
• Theorem: L(M') = L(M)
• Proof
• x ∈ L(M') ⇔ δ'*([s0], x) ∈ F'
• ⇔ [δ*(s0,x)] ∈ F'
• ⇔ δ*(s0,x) ∈ F
• ⇔ x ∈ L(M) ∎
• 41:29