EEN511 (Computability, Complexity, and Algorithms) Autumn 2013
Mon, Wed 5:00-6:15 in MM-212

Examinations

Assignments

     NEW: Requirements for submitting assignments.   
     1    Due Sat 14th Sept.
                Sort Race part 1, preliminary version of quicksort.     
2 Due Sat 28th Sept.
Find the minimum number of operations required to multiply together a chain of matrices. Input: number of matrices and their sizes (rows, columns). Output: the minimum number of operations (multiply and add two numbers) plus if you can, the optimal ordering for the multiplications.
A scruffy diagram to serve as a reminder.
     3 Due Mon 21st Oct.
Sort Race part 2, good version of merge-sort on arrays of strings.
     4 Due Mon 28th Oct.
Sort Race part 3, good version of heap-sort on arrays of strings.
     5 Due already
AVL trees.
Database files: dbrandom.txt, and dbsorted.txt.
     6 Due
Investigate this function, analysis-wise.
     7 Due Thurs 19th Dec. Absolute deadline no extensions no matter what.
Lambda Calculator.
Readability and good sample runs are really important this time. I won't have time to work out any strange input formats.
     8 Due Fri 6th Dec.
Absolute deadline Noon on Saturday.
Deliver the final versions of your three sorting algorithms, all ready to be recompiled with testlib and run in the race.
Either attach the source as a plain text attachment or tell me exactly where they are and what they are called in your rabbit account.

Class History

Class 1  ‑ Mon 26‑8‑2013   Quick introductions.
Class 2  ‑ Wed 28‑8‑2013 Three different partition methods. We wonder which could be the best?
Class 3  ‑ Wed 4‑9‑2013 Tricks for optimisation of code, some general, some for quicksort.
How many numbers are there? How do you compare infinite numbers? Skinny alligators holding hands with fluffy animals attempting to form a bijection. Enumerators: produce every element of a set one by one, none may be repeated, every one must be produced eventually.
Class 4  ‑ Mon 9‑9‑2013 Some C++ enumerators.
Summary of the important things.
Class 5  ‑ Wed 11‑9‑2013 Infinite streams of 0s and 1s, and what they mean.
Class 6  ‑ Mon 16‑9‑2013 Greedy algorithms: Minimum spanning tree, why does it work?
Optimal (least number of coins) change giving, why doesn't it always work?
Counting the number of different ways to give change for a particular amount - brute force is almost exponential, but memoising exactly the same function is linear.
Class 7  ‑ Wed 18‑9‑2013 A difficult trivial problem. Dynamic programming, a naturally recursive solution except that the number of recursive calls is too high, but there is a lot of overlap between them. Going straight to a dynamic programming technique without the intermediate step of a memoised recursive function.
Class 8  ‑ Mon 23‑9‑2013 A distraction about quicksort: publication, code part 1, part 2, hardware.
An easy difficult problem. A sequence of numbers.
Class 9  ‑ Wed 25‑9‑2013 Maximum sum contiguous subsequence: it's easier to work out backwards but it is symmetrical, the same solution works in the forward direction.
The descening missile defence system: C1, C2, C3, C4, Completed grid, Solution.
Minimum edit distance: E1, E2, Completed grid, Solution 1, Solution 2, All solutions.
Class 10  ‑ Mon 30‑9‑2013 Merge-sort for serial devices - pictures A, B.
Careful consideration of a non-recursive implementation for sorting arrays.
Class 11  ‑ Wed 2‑10‑2013 Priority queues, 4 operations: is it empty?, add new item with associated priority, remove item with top priority, alter priority of existing item.
Min-heaps as an efficient implementation of prioriy queues: is it empty? is constant time, other three operations are logN time.
Implementing a heap (or any full tree) in minimal space without pointers, in a specially ordered array or vector.
Class 12  ‑ Mon 7‑10‑2013 Using a heap to make another NlogN in-place sorting algorithm.
Heap/priority queues and the shortest path algorithm: A road map of Nebraska, The simple road and town data structures to implement it, Those structures properly connected. Pink objects are the town stand-ins which actually go in the heap and contain the necessary extra information - position in array and best known distance.
The entire procedure, step by step.
Class 13  ‑ Wed 9‑10‑2013 Once distances are known, tracing back the path is a simple linear operation All the distances.
The D/Dijkstra's Algorithm, a dynamic programming shortest path solution.
The lego sorting network. Constant time (amortised) sorting at the cost of quadratic hardware size.
Class 14  ‑ Mon 14‑10‑2013 Thinking about height-balancing a binary tree. Would it actually give good performance? (yes). Can we work out how to do it? ...
Class 15  ‑ Wed 16‑10‑2013 AVL trees.
The real average worst case without balancing: randomtree2.cpp
Plus 2-3-trees and red-black trees.
Class 16  ‑ Mon 21‑10‑2013 Radix sort for numbers and strings: needs an extra array, start at the least significant end, and make sure each pass leaves the previous pass's results undisturbed.
Counting or Bucket sort. All three are sort-of linear under the right circumstances. Big-endian Tries, take up a lot of space, but search and insertion time do not grow with the amount of data. Also they are naturally sorted.
Class 17  ‑ Wed 23‑10‑2013 Little endian tries allow for a lot of compression, which makes string based tries also viable.
Rabin-Karp fast substring detection (in four steps: one, two, three, four).
Complicated automata for concurrent multiple substring detection.
Class 18  ‑ Mon 28‑10‑2013 A Mystical Language, an introduction to the Lambda calculus.
An algorithmic method for creating substring-detection automata.
Some simple unarguable transformations that can be made to programs.
Class 19  ‑ Wed 30‑10‑2013 Progress: turning run-time errors into compile-time errors - Remember this?, Some others.
At last, a real uncomputable function. The halting problem, Turing's thesis.
Duplicate the input file, give both to the checker, confuse, and then act out its results.
Class 20  ‑ Mon 4‑11‑2013 The lambda calculus more deeply this time. Modelling numbers, addition and multiplication.
Class 21  ‑ Wed 6‑11‑2013 Lambda calculus: data structures, subtraction, non-recursive recusrion.
Introduction to top-down parsing.
Class 22  ‑ Mon 11‑11‑2013 Emergency Guide!.
Parsing for the lambda calculus in partiular, but also for programming languages in general.
Class 23  ‑ Wed 13‑11‑2013 Test Day, intended.
Class 24  ‑ Mon 18‑11‑2013
Class 25  ‑ Wed 20‑11‑2013 Programming with the lambda calculus, some examples, or functional programming.
Break
Class 26  ‑ Mon 2‑12‑2013 General observations on optimising code.
a practical detail.
Normal order evaluation = the magic of lazy evaluation.
The impressively easy sieve of Eratosthenes.
Class 27  ‑ Wed 4‑12‑2013
Class 28  ‑ Mon 9‑12‑2013 Boolean Satisfiability covers just about anything you could program so long as it has a known limit for the number of computational steps and amount of memory it needs for any given input. Boolean satisfiability is trivial for Disjunctive Normal Form (Or of Ands) but converting a circuit to DNF can take exponential time, so it doesn't really help. A non-deterministic Finite State Machine can't do anything that a deterministic one couldn't do, and the conversion is easy. A non-deterministic computer could easily and quickly solve boolean satisfiability for any circuit. Where does that lead us? ...

Sort race transcripts: Quick Sort, Merge Sort, Heap Sort.
Same data, sorted to put fastest first: Quick Sort, Merge Sort, Heap Sort.
Finally Quicksort and Mergesort compared.