EEN511 (Computability, Complexity, and Algorithms) Spring 2018
Mon, Wed 5:00-6:15 in Merrick 204

Examinations

Assignments

     Requirements for submitting assignments.   
     1    Due 4th February
                Solve the mystery fractal.     
2 Due 19th February
Program the mystery fractal.
3 Due 16th April
Solve and code the second mystery fractal, (the pictures).
4 Due 16th April
Actually code the knapsack problem.
input: target and list of integers,
output: list of integers whose sum is closest to target without exceeding it.
5 Due 6th May
Code your solution to problem 8.4 from the set that you studied during classes 10 and 11.
6 Due 6th May
Extend the mini language that we developed between classes 18 and 20, so that it could be of some use. It must have at least a variety of loop forms (including the for loop) and the ability to receive user input.
7 Due 6th May
Turing machine designs.

Class History

Class 1  Wed 17‑1‑2018    Clever algorithms, with graphs (spanning, flow, etc), and balancing trees, and data compression.
Counting things, discovering unsolvable problems and unknowable things.
Dynamic programming: Russian missile example 1, 2, 3, 4.
Class 2  Mon 22‑1‑2018 The Mysterious Fractal.
Some basic enumerators: one, two, three.
The essential points.
Class 3  Wed 24‑1‑2018 Encoding various things as natural numbers, and vice versa.
Arithmetic on infinite cardinal numbers.
Infinite streams of zeros and ones.
Class 4  Mon 29‑1‑2018 Turing's thesis, the Halting Problem: a perfectly sensible but uncomputable question,
and some of its consequences - you can't predict much about what programs will do unless you're willing to fail sometimes.
Class 5  Wed 31‑1‑2018 Dynamic programming.
How many ways can a group of N dinosaurs have a party with R in attendance?
How many minimum distance routes are there from A to B on a rectangular grid?
Class 6  Mon 5‑2‑2018 Dynamic Programming.
Given values for various finished lengths, what is the best way to cut up a long piece of material?
Given a collection (bag) of numbers, can I find a sub-collection with a given sum?
What is that sub-collection?
Class 7  Wed 7‑2‑2018 Given a sequence of numbers, find the contiguous subsequence with the maximal total.
Introducing minimum edit distance.
Class 8  Mon 12‑2‑2018 A pattern.
The matrix multiplication order problem, (in C++).
Longest (not necessarily contiguous) increasing subsequence, Q, A
Class 9  Wed 14‑2‑2018 Boolean Satisfiability.
Time Chart.
Class 10  Mon 19‑2‑2018 Look at these problems.
Class 11  Wed 21‑2‑2018 Continue looking at those problems.
Class 12  Mon 26‑2‑2018 Discussion and investigation of the solutions.
Class 13  Wed 28‑2‑2018 Standard solution to eight queens: recursion gives backtracking.
Some simple non-determinism through finite state automata.
8queens-ND, 8queens-ND-NR.
Revisiting the knapsack problem.
(picture): Revisiting boolean satisfiability.
Class 14  Mon 5‑3‑2018 Transforming problem domains
Sometimes the transformation takes too long to be useful boolean satisfiability solves knapsack.
CNF satisfiability is hard, DNF satisfiability is trivial, converting takes exponential time.
2-CNF satisfiability is easy, but 3-CNF satisfiability solves boolean satisfiability.
knapsack solves 3-CNF satisfiability.
Class 15  Wed 7‑3‑2018 The Clique problem; Clique solves 3-CNF: 1, 2, 3, 4, N.
Vertex cover, hamiltonian cycles, travelling salesman, graph colouring.
last few minutes: recursion elimination.
Class 16  Mon 19‑3‑2018 Beginning of language transformation: the divide and conquer technique to be used, input processing, lexical analysis.
Class 17  Wed 21‑3‑2018 Test Day.
Two old samples (one) (two). Keep in mind that topics are covered in a different order each semester.
A quick list of topics.
Class 18  Mon 26‑3‑2018 The beginning: (pdf), (docx), lexical analysis,
Step 1: (pdf), (docx), just expression = num or var,
Step 2: (pdf), (docx), print and when statements,
Step 3: (pdf), (docx), binary expr and var declaration,
Step 4: (pdf), (docx), sequence of statements in { }.
Class 19  Wed 28‑3‑2018 Step 5: (txt), reinterpret the tree to make a compilable C++ program,
Step 6: (txt), Interpret/execute the tree directly.
Class 20  Mon 2‑4‑2018 Special event at 6.00 tomorrow.
Step 7: (txt), giving priority to operators,
Step 8: (txt), left-to-right evaluation for equal priority.
Class 21  Wed 4‑4‑2018 Linearisation: recursion in the lineariser, not in the executor.
Class 22  Mon 9‑4‑2018 AVL trees.
Class 23  Wed 11‑4‑2018 Reminders about 2-3-trees,
Turing machines.
Class 24  Mon 16‑4‑2018 How to run a Turing machine on rabbit.
Six Turing machine exercises: replace all dogs with cats, is the number of Xs a multiple of three? Are parentheses correctly matched? Add 1 to a number in binary, is the number of As a power of two? Perform multiplication in base one.
Class 25  Wed 18‑4‑2018 The Lambda Calculus.
Class 26  Mon 23‑4‑2018
Class 27  Wed 25‑4‑2018