ECE511 (Computability, Complexity, and Algorithms) Spring 2022
Mon, Wed, 6:00 to 7:15 in MM 101

Examinations

Assignments

     Requirements for submitting assignments. to grader511 @ rabbit.eng.miami.edu   
     1    Due Sat 5th February.
                Solve the mystery fractal.     
2 Due Fri 25th February.
Program a solution to the "Russian missiles" problem.
3 Due Sun 13th March.
Turing Machine designs.
4 Due Sun 27th March.
Sudoku by backtracking.
5 Due Sun 17th April.
Implement a Trie.
6 Due Mon 2nd May.
Implement an AVL tree.

PC log in - use Putty or your own preferred SSH app.
OR mac users: start the terminal app, windows users: start powershell, then type the command
ssh username@rabbit.eng.miami.edu and type your password when prompted.
Windows users beware: you can't use ctrl-V in pico, but page up and page down will do the job.

Class History

Class 1  ‑ Wed 19‑1‑2022   Hello to everyone, and the syllabus.
Bool Sat,
Times,
Transforming (de Morgan, etc.).
An interesting fractal design.
Today's scruffy notes.
Class 2  ‑ Mon 24‑1‑2022 Examining the sizes of some infinite sets,
Discovering that #N, #Evens, #Z, #Q, and #Strings are all the same size,
Is there only one infinity?
Enumerations.
Today's notes, and the program.
Class 3  ‑ Wed 26‑1‑2022 Correcting the enumeration of rationals by removing duplicates.
Any enumeration can be made to go backwards.
So we could enumerate all possible pairings of programs with their potential inputs.
#N = #Z = #Q = #Strings = #(progs and inputs) = Aleph-0.
Unending streams of zeros and ones, and what they might represent.
It is impossible to enumerate all infinite streams of ones and zeros.
#R = #IDF = Aleph-1 > Aleph-0. There must be uncomputable numbers and functions.
Today's partial notes.
Class 4  ‑ Mon 31‑1‑2022 Here's a properly rendered Aleph
Cantor's enumeration for pairs of enumerations.
The Halting Problem: our tester can not exist.
Class 5  ‑ Wed 2‑2‑2022 Dynamic Programming:
The combinatoric problem,
Shortest paths through a grid,
Maximal sum contiguous subsequence,
and starting the Knapsack problem.
Class 6  ‑ Mon 7‑2‑2022 The knapsack problem solved.
How many ways can you make change for G cents?
Cutting up a valuable rod.
Class 7  ‑ Wed 9‑2‑2022 Longest increasing subsequence,
Largest vacant square,
The gold miner,
Minimum cost traversal.
Class 8  ‑ Mon 14‑2‑2022 Longest common subsequence,
Russian missile example 1, 2, 3, 4,
Minimum edit distance: E1, E2, Completed grid, Solution 1, Solution 2, All solutions.
Class 9  ‑ Wed 16‑2‑2022 The matrix multiplication order problem, (in C++).
Number of jumps to destination,
Tiling a narrow strip (comes out the same as fibonnaci),
Up-down numbers, extra credit available for a good verified solution.
Class 10  ‑ Mon 21‑2‑2022 Finite State Machines (or Finite Automata),
Recognising languages,
Intersection and Union.
Class 11  ‑ Wed 23‑2‑2022 Non-deterministic Finite Automata (can always be converted to deterministic ones).
Any number of zeros followed by the same number of ones can't be recoginsed.
Turing Machines:
How many X's, modulo three?
Replace all "dog"s with "cat"s.
Any number of zeros followed by the same number of ones.
Class 12  ‑ Mon 28‑2‑2022 Running Turing Machines.
Are parentheses correctly matched?
Increment a binary number,
Unary addition,
Attempted: is a unary number a power of two?
Class 13  ‑ Wed 2‑3‑2022 Turing Completeness, the Universal Turing Machine.
Minsky machines,
Conway's Game of Life, which is Turing complete.
Solving a puzzle (The grid),
Eight Queens, the C++ code.
Class 14  ‑ Mon 7‑3‑2022 Review day.
Class 15  ‑ Wed 9‑3‑2022 Mid-term day.
A sample, keep in mind that topics are covered in a different order each semester.
Break
Class 16  ‑ Mon 21‑3‑2022 The knight's tour, by backtracking.
Hamiltonian Cycles similarly, all cycles, the "graph" file.
8queens, non-deterministic.
Knapsack is really an NP problem,
The classes P and NP.
Boolean satisfiability is NP.
Boolean satisfiability solves Knapsack (and vice versa).
The classes NP-complete and NP-hard, EXPtime, the $1M question.
Class 17  ‑ Wed 23‑3‑2022 It is no use if the transformation is not P.
2CNF can be transformed into an easy graph problem: problem, and solution.
Bool-SAT solves 3CNF, and 3CNF solves Bool-SAT.
Knapsack solves 3CNF.
Class 18  ‑ Mon 28‑3‑2022 The Heighway dragon fractal, working.
Ackermann's function, not even in exptime.
The Clique problem solves 3CNF.
Clique and Vertex Cover solve each other.
Class 19  ‑ Wed 30‑3‑2022 Minimum Spanning Trees, Kruskal's and Prim's algorithms.
Job selection algorithm.
Huffman encoding.
Class 20  ‑ Mon 4‑4‑2022 Tries, and how to implement them.
KMP (Knuth-Morris-Pratt).
Rabin-Karp, (needs fixing).
Class 21  ‑ Wed 6‑4‑2022 Network flow, Ford-Fulkerson, A Network, Residual Network.
Reminder about 23-trees, and how to delete from one.
234-trees and red/black trees.
Class 22  ‑ Mon 11‑4‑2022 AVL trees.
Class 23  ‑ Wed 13‑4‑2022 Functional programming, part one:
Today's typescript, and side notes, and x.fun.
Class 24  ‑ Mon 18‑4‑2022 Functional programming: part two:
The seive of Eratosthenes in all its detail.
Mergesort and trees and arrays (the picture).
Maximum Sum Contiguous Subsequence.
Class 25  ‑ Wed 20‑4‑2022 Introducing the Lambda calculus.
The rules formalised.
Numbers, increment, add, multiply, decrement, linked lists.
Class 26  ‑ Mon 25‑4‑2022 More lambda calculus:
Logical operators and conditionals, subtraction and division,
Y, the paradoxical combinator, pulling recursion out of thin air.
Class 27  ‑ Wed 27‑4‑2022 Second mid-term.
Possible topics: Backtracking, NP-complete and conversions, Minimum Spanning Trees, String matching, Lambda calculus.
Class 28  ‑ Mon 2‑5‑2022 What we learned from the tests, etc.