EEN318 T (Algorithms) Autumn 2013
Tues, Thurs 5:00-6:15 in MM-212

The Book

Examinations:

Assignments

1 Due Fri 13th Sept.
Quicksort done well.
Data files: database1.txt, 2, 3, 5, 10, 20, 30, 50, 100.
2 Due Fri 27th Sept.
Merge-sort done well.
     3    Due Thur 17th Oct.
                Geographical Hash Table.     
4 Due Thur 14th Nov.
A manual tour of the United States (updated to new files now)
named-places.txt
intersections.txt
connections.txt
5 Due Sat 7th Dec.
Genetic engineering (see class 22 notes) Make some good-looking trees.
Project Due Sat 14th Dec.
All the map-related stuff combined into a single clean product.
Upgrade assignment 4 so that it takes two place names from the user, and automatically finds the shortest route from one to the other (you don't need to use a heap for your priority queue).
Then, before calculating the shortest path, find the smallest topological map tile (here) that contains both the start point and the destination, and display it nicely (graphics). Clearly mark the two points on it. When the shortest route is known, draw it on the map. Not as a straight line, but as all the little road segments joined up.

Class History

Class 1  ‑ Tue 27‑8‑2013   Quick introductions.
Getting ready to code some serious sorting algorithms.
Class 2  ‑ Thur 29‑8‑2013 Reminders about debugging under unix.
Serious analysis of best and worst quicksort times.
Knowing where the pivot is lets you avoid disaster.
Class 3  ‑ Tue 3‑9‑2013 file access e.g. ifstream f("/home/www/class/een118/database1.txt");
Remembering merge-sort for linked lists, and planning it for arrays.
Class 4  ‑ Thur 5‑9‑2013 Reminders of useful things: parameters to main, stringstreams, sprintf/snprintf, etc.
Carefully working out the loops and special conditions for an efficient merge-sort on arrays, Merge-sort play along at home.
Class 5  ‑ Tue 10‑9‑2013 Object orientation, inheritance, virtual methods: the whole story this time.
Class 6  ‑ Thur 12‑9‑2013 Polymorphism, safe typecasts, etc.
Shallow copies, assignment operators, copy constructors.
Class 7  ‑ Tue 17‑9‑2013 The end of the story. If your classes use inheritance and need a destructor, declare it as virtual. Pure virtual methods. Make object parameters be references, const references, or pointers whenever possible. Accidental aliassing. A single function that can sort just about anything.
Final edition of the running example.
Class 8  ‑ Thur 19‑9‑2013 Hash functions squash a string up into a repeatable number. Bad negative number.
Exploring linear probing for a hash table.
Class 9  ‑ Tue 24‑9‑2013 Empirical statistic gathering for linear probing.
Theoretical statistic gathering for closed addressing (linked lists).
Class 10  ‑ Thur 26‑9‑2013 Mathematical confirmation of experimental results.
Empirical statistic gathering for closed addressing.
Hash tables can grow like vectors: double size and rehash, keeping fullness < 0.5.
Very long hash values for password files, and as digital fingerprints of data files.
Class 11  ‑ Tue 1‑10‑2013 Named Places.
Pet Club: minimising memory use for large data collections, looking at the internal binary representation.
Class 12  ‑ Thur 3‑10‑2013 Properly examining the binary representation of integers bot positive and negative; the two's complement method and why it works.
Saving data in an unformatted binary file to save space and speed up access. our sample code. fopen, fclose, fread, fwrite
Using od as a clumsy tool for examining files.
Class 13  ‑ Tue 8‑10‑2013 Reading data back from a binary file, fseek and ftell.
Computer forensics: decoding a mystery file m.dat, mystery.dat, and discovering the Americas.
Class 14  ‑ Thur 10‑10‑2013 Arrays with more than one dimension are not handled well in C++.
Reading the whole file at once, and see the "mistake warning" inside this link.
Real graphics: displaying the map under windows. Getting things to look nice doesn't require too much effort.
Class 15  ‑ Tue 15‑10‑2013 Simple graph representation: an adjacency matrix.
Exploring a graph recursively by pretending it is a tree. Problem is that depth first search gets stuck in loops and doesn't get everywhere.
Taking control, recreating the effect of recursion with our own stack. Now that we are in control, we can change the way the stack behaves.
Break
Class 16  ‑ Tue 22‑10‑2013 Recruiting announcement.
The graph and a tree.
A normal recursive tree-printer programmed without recursion, using our own stack instead.
Replace the stack with a queue, and it still works, but gives us a breadth-first search instead of the usual depth-first one.
Doing the same thing to our graph exploring program works for that too, giving us a reliable function that doesn't get stuck in loops.
Class 17  ‑ Thur 24‑10‑2013 The procedure can be simplified if we don't try to follow the recursive plan so closely.
Finding shortest distances in an unweighted graph is now easy.
A weighted graph, how do we handle that?
Class 18  ‑ Tue 29‑10‑2013 Pre-test reminders.
Considering the design and implementation of the data structures for a road-map graph.
The need for a Priority Queue, which is different from an ordinary queue, and considering the options for implementation, none of which seemed very good.
Class 19  ‑ Thur 31‑10‑2013 Test Day.
Class 20  ‑ Tue 5‑11‑2013 The heap as an efficient priority queue implementation - all operations are logarithmic.
Heaps (and other full trees) living in arrays, no pointers needed. Heap-sort: in-place, guaranteed NlogN.
Class 21  ‑ Thur 7‑11‑2013 Emergency Guide!.
Old C string functions (see /usr/include/string.h).
A perfectly ordinary tree with an ordinary print function, and something that can reconstruct the tree from the print.
Parsing is easy if the input is well-designed.
Prefix (pre-order) and postfix (post-order) traversals. Polish and Reverse polish notation: easy evaluation of expressions.
An irregular quadrilateral, and making the computer draw it: picture
Class 22  ‑ Tue 12‑11‑2013 Lessons from the test.
Bit-arrays and the sometimes very useful bitwise operations & | ~ << >>.
Class 23  ‑ Thur 14‑11‑2013 Imperfect Orogeny.
Hashing in cryptography (ignore pages 2 and 3).
The Data Encryption Standard.
Class 24  ‑ Tue 19‑11‑2013 permutations.
RC4
numbers
Diffie-Hellman
Class 25  ‑ Thur 21‑11‑2013 Man-in-the-middle attacks.
RSA, maybe more readably, (older typed version).
Break
Class 26  ‑ Tue 3‑12‑2013 Test day.
Class 27  ‑ Thur 5‑12‑2013 Full-fledged recursion elimination: A strange and alarming function, and its non-recursive equivalent.
Weekend pre-exam review session (in lab room if possible):
        Saturday 7th, 3 - 5 pm.
Class 28  ‑ Tue 10‑12‑2013