EEN511 (Software Engineering) Spring 2011
Tue Thur 2:00-3:15 in MM209

• Official Syllabus.
• Downloads: none yet.
• The Book: "Algorithms in C++ parts 1-5", by Robert Sedgewick,
  pub. Addison-Wesley 2002, ISBN 020172684X.

Examinations

• Mid-Term Examination: some time in the future
• Final Examination: Wednesday 4th May, 2:00 pm.

Assignments

1. Sort Race. The heapsort part is due on 8th February.
2. Quicksort and mergesort are due on 22nd February.
3. Balanced Tree Race. due on Thursday 24th March.
4. Lambda Calculator. strict fatal deadline 10th May.
   (see also here for some hints about renaming).

Class History, etc.:

			2010		Last year's class web-site.
	Class 1		Tues 18‑1‑2011		General introduction to the subject. Comparing the sizes of infinite things; the number of possible C++ programs is the same as the number of positive integers.
	Class 2		Thurs 20‑1‑2011		Enumerations. If you can enumerate a set (list its members one by one so that there are no repetitions, and every one would eventually be reached), and if it is infinite, you could pair it up with the natural numbers, therefor it would have to have the same cardinality, "Aleph 0". Cantor's enumeration. Natural numbers, rational numbers, strings, programs, pairs of numbers all have the same cardinality. Some practical experiments with enumerations.
	Class 3		Tues 25‑1‑2011		More enumerations, more huge things that turn out to be no bigger than the integers. It really is starting to look bad for the real numbers. Storing a full binary tree without any need for pointers. Starting to investigate the "heap" data structure.
	Class 4		Thurs 27‑1‑2011		Heaps as an implementation of Priority Queues. Logarithmic algorithms for insert new item with priority P, remove item with lowest priority, and adjust priority of item I to P. Max-Heaps giving a new in-place O(N log N) sorting algorithm. A spider climbed up through the air.
	Class 5		Tues 1‑2‑2011		Boolean Satisfiability, O(N×2N). Knapsack, O(N×2N) but with a much faster table method.
	Class 6		Thurs 3‑2‑2011		Dynamic programming: neat but inefficient recusive solution -> memo function that records previous answers to avoid repetition -> table pre-filled with all answers so no further computation is required.
	Class 7		Tues 8‑2‑2011		More dynamic programming - maximum sum contiguous subarray, this time an easy table method led to discovering an obscure recursive solution; largest empty rectangle; minimum edit distance.
	Class 8		Thurs 10‑2‑2011		The heap-sort-race. Alan's won, two of you were faster than the standard library. Techniques and tricks for optimising code. Measuring how surprising information is.
	Class 9		Tues 15‑2‑2011		The original publication of Quicksort, and implementation part 1, part 2. The computers it was tested on. Thinking about problems that optimising quicksort may present.
	Class 10		Thurs 17‑2‑2011		Radix sort on punched cards and as an algorithm, counting and bucket sorts; why they don't beat the NlogN algorithms. A special sorting elephant made of lego, O(1) sorting at the expense of O(N2) computing power.
	Class 11		Tues 22‑2‑2011		Balance of tree = height of left minus height of right; balanced if -1, 0, or +1. Balanced tree of height H: max = pow(2, H), min = pow((sqrt(5)+1)/2, H) nodes. Make a balanced tree by starting with a balanced one and restoring balance after each insertion/deletion. Discovering the AVL tree-balancing rotations.
	Class 12		Thurs 24‑2‑2011		Fully exploring the AVL methods. The two-three tree.
	Class 13		Tues 1‑3‑2011		The lessons learned from trying to make quicksort and mergesort as fast as possible. There are some very mysterious factors involved in optimising code.
	Class 14		Thurs 3‑3‑2011		Lots of details of 2-3 trees, and considerations about their implementation.
	Class 15		Tues 8‑3‑2011		Data compression: Huffman Coding, Greedy Algorithms, Hill climbing and simulated annealing, Minimum spanning trees.
	Class 16		Thurs 10‑3‑2011		Fast string searching with Tries; Fast substring finding with Rabin-Karp.
			Spring Break
	Class 17		Tues 22‑3‑2011		Infinite streams of zeros and ones. There must be uncomputable numbers and functions.
	Class 18		Thurs 24‑3‑2011		Identifying an uncomputable function. The halting problem.
	Class 19		Tues 29‑3‑2011		So many things about programs are uncomputable (the cow game) because they can be "reduced" to the halting problem. Turing machines and other models of computation. What it means to be computable: the Church-Turing thesis. State monitoring: numbur of bits in monitor must be 2 to the power of number of states in the monitored; nothing can know its own state of being.
	Class 20		Thurs 31‑3‑2011		The Lambda Calculus, communicating algorithms to little green men. Implementing numbers and data structures.
	Class 21		Tues 5‑4‑2011		More lambda calculus, engineering the formulas to do what you want. So far, we've got positive integers with unlimited size, addition, subtraction, multiplication, but not yet division, comparisons, ands, ors, ifs, but not yet whiles, and data structures.
	Class 22		Thurs 7‑4‑2011		Racing the tree balancing methods against each other. The details of red-black trees.
	Class 23		Tues 12‑4‑2011		The Church-Rosser theorems; Y, the paradoxical combinator; recursive functions without recursive definitions; normal order evaluation.
	Class 24		Thurs 14‑4‑2011		The benefits of normal order evaluation.
	Class 25		Tues 19‑4‑2011		Normal order evaluation implemented as lazy evaluation, insertion sort turns into selection (or maybe bubble) sort. What denotational semantics is.
	Class 26		Thurs 21‑4‑2011		"Conway's Game of Life" is Turing Complete.
	Class 27		Tues 26‑4‑2011		Non-deterministic machines. Non-deterministic choice, backtracking, computer duplication, magic oracles. Non-deterministic Polynomial (NP) algorithms.
	Class 28		Thurs 28‑4‑2011		The simple yes/no question "does a solution to this particular problem exist?", is the driving oracle in finding solutions. NP algorithms must take only a polynomial number of nondeterministic choices and have a polynomial time algorithm for verifying alleged solutions. NP algorithms for boolean satisfiability, knapsack, and travelling salesman. Showing that bool-sat solves knapsack, but 2cnf-sat doesn't.
					The final results of the races.