EEN318, Programming III, Autumn 2011
Tues, Thurs at 12:20 in MM112

The Book

Examinations:

Assignments

     1    Due Sunday 18th September.
                Gazetteer Hash Table, here's the data file.     
2 Due 22nd October or 5th November. (one date for assignment 2, the other for 3, you choose)
Graphical map/atlas display.
3 Due 22nd October or 5th November. (one date for assignment 2, the other for 3, you choose)
Shortest route between two towns (I).
4 Due Sunday 4th December.
Partnership: Interactive U.S. Travel Planner.
5 Due Sunday 11th December.
Partnership: Make your own programming language.

Class History

Class 1  Wed 24‑8‑2011   General introductions to what the course is all about.
Introducing hash tables.
Class 2  Mon 29‑8‑2011   Hash tables, collisions, experiments, open hashing and chaining.
What are the chances of being lucky and not having any collisions?
Testing the quality of a hash function and the knotty problem of the number that can't be negated.
Class 3  Wed 31‑8‑2011   Experiments and theoretical analysis (Poisson distribution) to find an almost perfect hash function.
Some graphs: The effects of a changing fullness on efficiency.
Class 4  Wed 7‑9‑2011   Considering a clean and properly object oriented implementation of the phone-book hash table.
Class 5  Mon 12‑9‑2011   Processing non-text "binary" files.
Class 6  Wed 14‑9‑2011   Continuing with non-text files (Monday's notes have been updated to include the constants that I couldn't remember). Using the od command to investigate binary files. Viewing America as a first example program.
Class 7  Mon 19‑9‑2011   Programming in old-fashioned C. Strings as pointers to arrays of characters.
Class 8  Wed 21‑9‑2011   a map that looks like a tree. intersections, majorroads.
Exploring a tree-shaped map, and a more object-oriented version.
Class 9  Mon 26‑9‑2011   Shortest path in a graph; the tree-like recursive solution is depth-first and inefficient because it repeats work. Designing a Breadth-first solution. Nebraska positive and negative.
Class 10  Wed 28‑9‑2011   Completing the breadth-first search method, thinking about concrete implementations of the priority queue that is needed to drive it.
Class 11  Mon 3‑10‑2011   Heaps as priority queues, and accidentally discovering the third O(N×logN) sorting algorithm, Heap-Sort.
Class 12  Wed 5‑10‑2011   Comparing all we know about sorting algorithms. Counting sort, a non-general-purpose one. Beginning Quick-sort.
Class 13  Mon 10‑10‑2011   Three different methods for partitioning.
Class 14  Wed 12‑10‑2011   Quick-sort without recursion. (qsdemo)
The original publication of Quicksort, and implementation part 1, part 2.
Class 15  Mon 17‑10‑2011   General recursion elimination: split function into parts and make "activation records". Use a stack for depth-first or a queue for breadth-first search. Ackermann's function, computable but not in a practical way.
Class 16  Wed 19‑10‑2011   Trees as representations, designing a tree to represent and evaluate arithmetic expressions.
Class 17  Mon 24‑10‑2011   Better tree construction methods, and even a little "program" with an assignment statement. 5 & 9 = 1, 5 ^ 9 = 12, etc.
Class 18  Wed 26‑10‑2011   A quick and simple method for parsing expressions using an operator stack and an operand stack, and comparing priorities. It doesn't handle things more complex than expressions very nicely though.
Class 19  Mon 31‑10‑2011   Topics for the test.
Depth-first search with Iterative Deepening is exactly the same as Breadth-first search except that it requires less memory but takes more time.
Multi-threading can be very useful, but watch out for race conditions (the example of comparing the contents of two trees by recursively traversing both of them simultaneously).
Class 20  Wed 2‑11‑2011   Test Day.
Class 21  Mon 7‑11‑2011   The lexeme class: serious object orientation. Inheritance, Polymorphism, Virtual Methods.
Class 22  Wed 9‑11‑2011   A customisable print method shows the usefulness of virtual methods. Examining the vtable: how "virtual" really works. What is "int(**)(void)"?
Class 23  Mon 14‑11‑2011   Layered Software Design, separating different concerns and simplifying the task. A character-by-character input system underneath a Lexical Analyser ("tokenizer") underneath layers and layers of Parsers.
Class 24  Wed 16‑11‑2011   The Recursive Descent LL1 Parser.
Class 25  Mon 21‑11‑2011   Semi-Test 2A
Class 26  Wed 23‑11‑2011   Questions and Answers
Class 27  Mon 28‑11‑2011   Semi-Test 2B
Class 28  Wed 30‑11‑2011   Some words on the final exam.
Destructors, copy constructors, and assignment operators, and their very unfortunate interactions. The nature of numbers and how many of them there might be.
Review Sat 10‑12‑2011   in EB 216 from 1 to 3. Review session with the lab guys.
Final Mon 12‑12‑2011   Final Exam
If you are going to do the make-up question on hash tables, research "open addressing" also known as "closed hashing".