EEN511 (Software Engineering) Spring 2010
Tue Thur 5:00-6:15 in MM107

• 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: Tuesday 11th May 5:00 p.m.

Assignments

1. Due 8th February: GUI toolkit library, part 1:
   Making objects to represent windows and various components, and having them displayed properly on the screen. They do not need to do anything active (such as react to mouse clicks) yet.
2. Due 12th March: Min-Heap:
   By implementing a priority queue as a heap, make your U.S. shortest route program fast.
3. Due 28th March (strict deadline): Sort Race:
   Implement two fast sorting algorithms for large numbers of strings.
   Details here.
4. Due 10th May: Lambda Calculator:
   A program that allows the user to enter any lambda expression, and reduces it using normal order evaluation to its ground form, if it has one.
5. Due 11th May (strict deadline): Fully functional GUI library.

Class History, etc.:

			2009		Last year's class web-site.
	Class 1		Tues 19‑1‑2010		An object-oriented approach to creating GUI toolkit library.
	Class 2		Thurs 21‑1‑2010		A study of the original publication of Quicksort, and implementation part 1, part 2. the language it was programmed in, and the computers it was tested on.
	Class 3		Tues 26‑1‑2010		Entropy, disorder, unknownness, surprisingness. Amount of information. Going to the chair shop, proof that general purpose sorting can not be faster than NlogN, and that counting sort can't get around it. Compression, Huffman encoding.
	Class 4		Thurs 28‑1‑2010		How many things are there? Comparing infinite sizes, enumerations, the number of numbers, possible programs, data files, fractions (Cantor's enumeration), etc.
	Class 5		Tues 2‑2‑2010		The number of real numbers, complex numbers, sets of numbers and decision functions: discovering a bigger infinity, the existence of uncomputable numbers, and problems that can never be solved.
	Class 6		Thurs 4‑2‑2010		(Ackermann's function) Maximum and minimum depths for a balanced binary tree; the AVL tree transformations that guarantee balance.
	Class 7		Tues 9‑2‑2010		Implementation of AVL trees. Balanced trees could live in arrays, but AVL transformations would be impractical. Beginning of Heaps.
	Class 8		Thurs 11‑2‑2010		Balance isn't enough for a tree to fit in an array: full binary trees; Complete heap manipulations, heap-sort, third adjustment needed to make a fast priority queue.
	Class 9		Tues 16‑2‑2010		Gorillas with computers. The beginnings of an enumerator for binary trees, recursion elimination.
	Class 10		Thurs 18‑2‑2010		Completed tree enumerator. Inheritance as a way of generalising data access.
	Class 11		Tues 23‑2‑2010		Message passing with active objects. Beginning 2-3-trees.
	Class 12		Thurs 25‑2‑2010		2-3-trees efficientcy, insertion, and deletion; red-black trees; B-trees.
	Class 13		Tues 2‑3‑2010		Two related problems: boolean satisfiability and knapsack, an efficient algorithm for most cases of knapsack, but none for bool sat. A much worse problem, the travelling salesman.
	Class 14		Thurs 4‑3‑2010		Straightening out the permutations. Solutions to knapsack and boolean satisfiability can be constructed from a short series of yes/no questions. A solution to boolean satisfiability would also be a solution to knapsack, etc. Seeing that change-making and C(n, r) are very similar to knapsack and that the same technique might be used for all three.
	Class 15		Tues 9‑3‑2010		Dynamic programming solutions to knapsack, change-making, and C(n, r). Non-deterministic programs, Polynomial vs. Non-Polynomial time.
	Class 16		Thurs 11‑3‑2010		Non-deterministic choice is the same as a magic oracle. NP, NP-hard, and NP-Complete. Boolean Satisfiability (SAT) solves all NP problems. DNFSAT and 2CNFSAT are easy, 3CNFSAT is hard and would solve SAT. Reducibility.
			Spring Break
	Class 18		Thurs 25‑3‑2010		The Lambda Calculus, the simplest possible programming language.
	Class 19		Tues 30‑3‑2010		The true point of the Lambda Calculus (doc). Normal order evaluation and the Church-Rosser theorems.
	Class 20		Thurs 1‑4‑2010
	Class 21		Tues 6‑4‑2010
	Class 22		Thurs 8‑4‑2010		demo
	Class 23		Tues 13‑4‑2010		Sort races.
	Class 24		Thurs 15‑4‑2010		Fast string matching: Tries; Fast substring detection: Finite state automata, and rolling hashes: Rabin-Karp.
	Class 25		Tues 20‑4‑2010		The Busy Little Bee. Does a program ever stop? The Halting problem, Turing's Thesis, an insoluble problem, and uncomputable function. Two uncomputable numbers, the impossibility of omniscience.
	Class 26		Thurs 22‑4‑2010		Functional programming: fold, map, filter, etc. One line programs for generating primes and finding the sum of the maximal sum subsequence.
	Class 27		Tues 27‑4‑2010		Self-transforming programs, example: bubble-sort is insertion-sort with normal order evaluation. Automatically generated programs, formal proofs of correctness.
	Class 28		Thurs 29‑4‑2010		Career enhancement: dealing with legacy software. Fortran and Cobol