ECE511 (Computability, Complexity, and Algorithms) Spring 2019
Mon, Wed 5:00-6:15 in MM 100

Examinations

Assignments

     Requirements for submitting assignments.   
     1    Due Sun 27th January
                Solve the mysterious fractal.     
2 Due Sun 17th February
Turing machine designs.
3 Due Mon 4th March
Make a Turing Machine executor.
4 Due Sun 14th April.
AVL Trees.
This is the data file.
5 Due Sun 28th April
Solve the second fractal mystery.
6 Due Sun 5th May
Lambda expression reducer.

Class History

Class 1  Mon 14‑1‑2019    Quick introductions,
An introduction to some of the things we'll be studying this semester.
Class 2  Wed 16‑1‑2019 A mysterious fractal.
Comparing the sizes of sets by defining one-to-one mappings;
Enumerations and enumerators, number of natural numbers = number of integers = number of even numbers = number of ASCII strings = number of C++ programs = Aleph-zero.
Class 3  Wed 23‑1‑2019 Some enumerators that we worked out: Natural numbers, Even numbers, Integers.
A grammar based enumerator for C++ programs.
Cantor's enumeration.
Class 4  Mon 28‑1‑2019 Infinite streams of zeros and ones, and what they can represent.
Integer decision functions, and how useful they are.
#IDFs is greater than #Programs; there must be uncomputable functions and even numbers.
Class 5  Wed 30‑1‑2019 Turing's Thesis: we identify an uncomputable function.
Class 6  Mon 4‑2‑2019 Turing Machines.
Class 7  Wed 6‑2‑2019 Turing machine designs.
Class 8  Mon 11‑2‑2019 Dynamic programming introduction: Dinosaurs arranging different parties, the combinatoric function.
Cutting a rod into lengths of varying values.
Class 9  Wed 13‑2‑2019 How many shortest paths in a rectangular grid?
Maximum sum contiguous subsequence
How many ways to give change for a given amount
Largest unobstructed square in an array
Comparing DP solutions to brute-force solutions.
Class 10  Mon 18‑2‑2019 How many coins to make change?
Longest common subsequence of two strings,
Minimum edit distance: E1, E2, Completed grid, Solution 1, Solution 2, All solutions.
Class 11  Wed 20‑2‑2019 Brief announcement.
Russian missile example 1, 2, 3, 4.
Longest (not necessarily contiguous) increasing subsequence, Q, A
The matrix multiplication order problem, (in C++).
The knapsack problem.
Class 12  Mon 25‑2‑2019 A logic circuit: Boolean Satisfiability,
Tractable vs. intractable problems, a time chart,
Transforming problem domains.
If the transformation takes non-P time, it is no use.
Back to Boolean satisfiability, it solves the knapsack problem.
Class 13  Wed 27‑2‑2019 Transforming some domains: 2-CNF-SAT is easy, (completed).
But 3-CNF-SAT is Hard.
Standard solution to eight queens: recursion gives backtracking.
Class 14  Mon 4‑3‑2019 8queens-ND, 8queens-ND-NR.
Revisiting the knapsack problem.
Revisiting boolean satisfiability.
knapsack solves 3-CNF satisfiability.
Class 15  Wed 6‑3‑2019 Test Day, (List of topics).
Two old samples (one) (two). Keep in mind that topics are covered in a different order each semester.
Class 16  Mon 18‑3‑2019 What we got from the test,
Some exercises in recursive design.
Class 17  Wed 20‑3‑2019 Transforming problem domains: Knapsack solves 3CNF-sat,
The clique problem solves 3CNF-sat,
What it means to be NP and NP-complete.
More recursive thoughts: iterative deepening instead of a queue.
Class 18  Mon 25‑3‑2019 Review of 2-3-trees: deleting from a 2-3-tree.
2-3-4-trees and Red-black trees.
Class 19  Wed 27‑3‑2019 Red-black tree transformations.
AVL trees.
Class 20  Mon 1‑4‑2019 AVL trees part two.
Class 21  Wed 3‑4‑2019 Introduction to functional programming with lazy evaluation.
Class 22  Mon 8‑4‑2019 F.P. and lazy evaluation part 2.
Class 23  Wed 10‑4‑2019 F.P. and L.E. part 3.
Class 24  Mon 15‑4‑2019 Introducing the Lambda calculus.
Representations of objects.
Class 25  Wed 17‑4‑2019 A reminder about virtual methods in C++.
Lexical analyser and parser for lambda expressions.
Class 26  Mon 22‑4‑2019 End of parsing: dealing with choices.
More lambda calculus.
Class 27  Wed 24‑4‑2019