menu

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
    UnionA ∪ B{ x | x ∈ A or x ∈ B }
    ConcatenationA ∘ B{ xy | x ∈ A and y ∈ B }
    StarA*{ 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∀xx ~ 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