##### 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__describe__–__all__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 S_{1}= n, S_{i+1}= if (S_{i}% 2 == 0) S_{i}/2 else 3S_{i}+ 1, Syracuse(n) = lease i such that S_{i}= 0 if S_{k}> 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?

- If any of them is easy, they are all easy
**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, Σ, δ, q_{0}, 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, q
_{0}∈ 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 = w
_{1}w_{2}...w_{n}(n ≥ 0) be a string where each symbol w_{i}is from the alphabet Σ

M**accepts**w if states s_{0},s_{1},...s_{n}exist s.t- s
_{0}= q_{0} - s
_{i+1}= δ(s_{i}, w_{i+1}) for i = 0, ... n – 1 - s
_{n}∈ F - (w is accepted if it starts at the start state and ends at an accept state)

- s
- 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

- Given definition from last class, and let w = w
- [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* { x _{1}x_{2}... x_{k}| K ≥ 0 and each x_{i}∈ 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 19
^{th} - 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, s
_{0}, δ, F)

L(M) = { w | δ*(s_{0},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', s
_{0}', δ', F')- s' = s/≈
- s
_{0}' = [s_{0}] - δ'([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') ⇔ δ'*([s
_{0}], x) ∈ F' - ⇔ [δ*(s
_{0},x)] ∈ F' - ⇔ δ*(s
_{0},x) ∈ F - ⇔ x ∈ L(M) ∎

- x ∈ L(M') ⇔ δ'*([s
- 41:29