ECE511 (Computability, Complexity, and Algorithms) Spring 2020
Mon, Wed 5:05-6:20 in MM 100

Examinations

Assignments

     Requirements for submitting assignments. to grader511 @ rabbit.eng.miami.edu   
     1    Due Sat 8 Feb
                Solve the mystery fractal.     
2 Due 27 Feb. extended to sat. 29th
Code the russian missile d.p. example.
3 Mon 30 March
Turing machine designs.
4 Due Wed 15 April
Program a Turing machine emulator.
5 Due 25 April
Solve the second mystery fractal - program the graphics.
6 Due 4 May
AVL Trees.
This is the data file.

Class History

Class 1  ‑ Mon 13‑1‑2020   Hello to everyone.
Bool Sat, Times, Transforming (de Morgan, etc.).
Class 2  ‑ Wed 15‑1‑2020 How many natural numbers are there? even numbers? integers? rational numbers?
How many real numbers? Strings? C++ programs?
Enumerations.
Discovering that #N = #Z = #E = #S.
Class 3  ‑ Wed 22‑1‑2020 Aleph-0. = the size of all those sets.
The number of possible programs in any language = that same infinite number.
Cantor's enumeration - even rational numbers has the same size.
Unending streams of zeros and ones, and what they might represent.
An interesting fractal design.
Class 4  ‑ Mon 27‑1‑2020 We discover that there are more IDFs and real numbers than possible programs, etc.
Therefore there must be uncomputable functions and numbers.
We discover an uncomputable function: the Halting Problem.
Class 5  ‑ Wed 29‑1‑2020 Dynamic Programming: the combinatoric problem,
and the number of shortest paths in a grid.
Class 6  ‑ Mon 3‑2‑2020 More dynamic programming:
Cutting a rod into variously priced lengths for maximal total price,
Maximum sum contiguous subsequence,
The knapsack problem again.
Class 7  ‑ Wed 5‑2‑2020 Number of ways to make change,
Largest vacant square in an array,
Starting with Minimum Edit Distance.
Class 8  ‑ Mon 10‑2‑2020 Minimum edit distance: E1, E2, Completed grid, Solution 1, Solution 2, All solutions.
Best (minimal) way to make change.
Class 9  ‑ Wed 12‑2‑2020 Longest common subsequence of two strings,table
Longest increasing subsequence Q, A (not necessarily contiguous).
Russian missile example 1, 2, 3, 4.
The matrix multiplication order problem, (in C++).
Class 10  ‑ Mon 17‑2‑2020 Finite Automata (or Finite State Machines)
Class 11  ‑ Wed 19‑2‑2020 Turing Machines.
The universal Turing Machine.
What is the number of Xes, modulo 3?
Replace all occurrences of "dog" with "cat".
Are parentheses correctly matched?
How do you add 1 to a binary number?
Class 12  ‑ Mon 24‑2‑2020 Multiplication base 1,
Are two binary numbers equal?
Is a base-1 number an exact power of 2?
Class 13  ‑ Wed 26‑2‑2020 Generate all subsets of a set, all permutations of a string.
Generate valid pairings of parentheses.
Class 14  ‑ Mon 2‑3‑2020 Review day.
Class 15  ‑ Wed 4‑3‑2020 Test Day,
A list of topics.
Break
Class 16  ‑ Mon 16‑3‑2020 (closed)
Class 17  ‑ Wed 18‑3‑2020 (closed)
Class 18  ‑ Mon 23‑3‑2020 (recorded class)
Class 19  ‑ Wed 25‑3‑2020 (recorded class) But 3-CNF-SAT is Hard.
Class 20  ‑ Mon 30‑3‑2020 More problem domain translations,
What it means to be NP complete.
(recorded class)
Class 21  ‑ Wed 1‑4‑2020 Review of 2-3-trees: deleting from a 2-3-tree.
(recorded class)
Class 22  ‑ Mon 6‑4‑2020 2-3-4-trees and Red-black trees.
Red-black tree transformations.
Depth and balance of randomly generated binary trees.
(recorded class)
Class 23  ‑ Wed 8‑4‑2020 AVL trees.
(recorded class)
Class 24  ‑ Mon 13‑4‑2020 Introduction to functional programming.
(recorded class)
Class 25  ‑ Wed 15‑4‑2020 Functional programming part two.
(recorded class)
Class 26  ‑ Mon 20‑4‑2020 Trees in functional programming.
The lambda calculus, part 1.
(recorded class)
Class 27  ‑ Wed 22‑4‑2020 More lambda calculus.
(recorded class)
Class 28  ‑ Mon 27‑4‑2020 Final exam part A
Class 29  ‑ Wed 29‑4‑2020 Review day
(recorded class)
Class 30  ‑ Mon 4‑5‑2020 Final exam part B