EEN318, Programming III, Autumn 2006
Assignments
- (Due Tues 12th Sept) Investigate the Mystery File. Find a way to
meaningfully, usefully, and conveniently display its contents. Email your program (just
the source .cpp file) grader318@rabbit.eng.miami.edu.
- (Due Thurs 28th Sept) To your perfectly working display program for the now decoded mystery
file, add the ability to accept two place names typed by the user, find their geographical
coordinates in the alphaplaces file, show their locations
correctly on the map, and compute the distance between them.
Note: The alphaplaces file has been modified to remove the annoying "city", "CDP",
and other suffixes to place names. If you want the old unmodified file, it is
here.
- Turn in dates for items 4, 5, and 6 are
- Tuesday 31st October,
- Sunday 12th November, and
- Tuesday 21st November.
but you choose which order you do them in.
- (Due on one of the above three dates, Group Project) Combine/integrate the alphaplaces.txt, majorroads.txt, and locations.txt files
(all found here) so that for any names city the roads that connect to it can
be found, and for any road the places that it connects can be quickly found.
- (Due on one of the above three dates, Group Project) Add a zoom-in, zoom-out, pan-west, pan-east, pan-north, and
pan-south mouse-clickable feature to your display. You must be careful to work out correctly which
map file is needed at each stage.
- (Due on one of the above three dates, Group Project) Interactive interative road renderer. The user enters a location,
then the computer gives a menu of all roads connected to that location. The user selects one, that road is drawn
onto the map, its "other" end becomes the user located location, and the process repeats.
- (Due Tuesday 5th December, Group Project) Navigation. User enters two place names, program finds a path
path between those two places, and displays the whole route in a user-friendly fashion.
Class History
- Class 1 (24-8-2006) Expert programming is more than expertise with a programming language. Examples
of speeding up disc file searches. Beginning of binary file processing.
- Class 1½ (29-8-2006) Cancelled for imaginary hurricane.
- Class 2 (31-8-2006) Creating a binary file (docs), sizes of types.
The mystery file.
- Class 3 (5-9-2006) Graphics samples:
one,
two. Fast file searching (part 1)
US places dictionary.
- Class 4 (7-9-2006) Binary chop search of a file. Data item access methods (part 1).
- Class 5 (12-9-2006) Getting large amounts of data into memory; effective and efficient access.
- Class 6 (14-9-2006) Array of objects vs. array of pointers.
Reminder of the purpose of "new". STL and vectors.
- Class 7 (19-9-2006) Comparing linked list techniques: adding pointer to object, link object, list and link objects,
enumeration assistance.
- Class 8 (21-9-2006) Protected classes, template functions, template classes, the need for enumeration objects.
- Class 9 (26-9-2006) Motivating example: A little web server. int fd vs. FILE *f. String processing.
- Class 10 (28-9-2006) Tokenising a string in C (strtok) and C++ (istringstream) and with hand-made functions.
- Class 11 (3-10-2006) Organisation of memory in a running program, why new is really needed.
- Class 12 (5-10-2006) The standard C string functions. Implementing a C++ string from scratch.
- Class 13 (10-10-2006) Completing the string implementation, making it into a genric vector, reference results, copy constructors.
- Class 14 (12-10-2006) Serious object orientation, tricky templates. todays samples.
- Class 15 (17-10-2006) Inheritance, Abstract Methods, Abstract Classes, Polymorphism, bit operations.
- Class 16 (19-10-2006) The need for polymorhpism and virtual methods, today's examples
- Class 17 (24-10-2006) The rules and reasons behind virtual and polymorhpism, today's examples
- Class 18 (26-10-2006) Unix/Windows compatibility, reading a directory. Separate compilation: .h and .o files.
- Class 19 (31-10-2006) time(), stat(), final virtual/polymorphism sample.
- Class 20 (2-11-2006) Mid-Term Test.
- Class 21 (7-11-2006) Encryption and security 1: exclusive-or codes, cracking them, one-time pads, fake pads.
- Class 22 (9-11-2006) Going through the test and learning the lessons with Roger.
- Class 23 (14-11-2006) One way hash, RSA, digital signatures: part 1,
part 2
- Class 24 (16-11-2006) Public-key/Private-key schemes, digital certificates, certification authorities, key exchange, session keys.
Diffie Hellman,
- Class 25 (21-11-2006) Adapting linked lists to binary chop search: binary search trees, creation, searching, insertion.
- Class 26 (28-11-2006) Recursive tree functions. Demonstrating correctness by induction. Designing recursion from induction.
- Class 27 (30-11-2006) Exploring graphs, basic shortest path. (Nebraska: pos, neg)
Last year's class history
From the following, you can see what the class is all about, and get a good idea of what to expect.
Although you should understand that things do change from year to year, if they didn't, we would all get very bored.
Class History 2005:
- Class 1 (25-8-2005) No class due to hurricane.
- Class 2 (30-8-2005) Introductions, what we're going to be doing, etc, etc, etc.
- Class 3 (1-9-2005) Examining the problem of fast data searches: binary chop, hash table.
- Class 4 (6-9-2005) Hash tables and linked lists in a non-object-oriented style.
- Class 5 (8-9-2005) C stuff: low level memory accesses; Memory-mapped pixel graphics operations; Project statement.
- Class 6 (13-9-2005) (today's C++ stupidity);
Defining GUI component objects:
(working introductory sample)
(enlarged button).
- Class 7 (15-9-2005) (HLS and RGB application, method); Making derived classes; Inheritance.
- Class 8 (20-9-2005) No class, another hurricane day.
- Class 9 (22-9-2005) (secret spam-sending example) More inheritance, constructor rules, polymorphism, virtual methods.
- Class 10 (27-9-2005) Formalising the rules of object orientation in C++, especially for polymorphism.
- Class 11 (29-9-2005) Inheritance for GUI components; Encapsulation - private hides details, for maintainable programs.
- Class 12 (4-10-2005) Part 2 of project; Function variables; Containers and Layout.
- Class 13 (6-10-2005) (today's sample) Abstract methods and classes; Java's Object; templates.
- Class 14 (11-10-2005) Efficiency analysis: linked list create and access are linear, growable array access is constant, create is quadratic (with increment) or linear (with scale).
- Additional reference material:
Linked List template; C++ strings
introduction and
reference.
- Class 15 (13-10-2005) Bioloigical taxons: building and exploring a tree.
- Class 16 (18-10-2005) C file and string processing; Shortest path algorithm, part 1: constructing the data structures.
- Class 17 (20-10-2005) (Nebraska: pos, neg)
A true shortest path algorithm; starting the army-of-ants simulation.
- Class 18 (25-10-2005) Another hurricane day.
- Class 19 (27-10-2005) Another hurricane holiday.
- Class 20 (1-11-2005) Completing shortest path algorithm (to find the actual path), and analysing its efficiency.
- Class 21 (3-11-2005) Off-screen bitmaps; friends; constructors as type converters.
- Class 22 (8-11-2005) (ammonites cpp, exe)
Copy constructors, assignment operators, destructors, const references, memory leaks.
- Class 23 (10-11-2005) Traceable value-holding types; An ordered linked list, lack of advantages; Mergeing lists;
(mistake).
- Class 24 (15-11-2005) "Mid"-term.
- Class 25 (17-11-2005) Fast sort of a linked-list based on halving and merging.
- Class 26 (22-11-2005) Just how fast merge-sort is, and why; why it isn't so great for arrays.
- Class 27 (29-11-2005) More on low-level C string and file operations: (data files here).
- Class 28 (1-12-2005) The idea behind Quicksort; Ordered Binary Trees: how and why they work, building them O(NlogN), searching them O(logN).
- Class 29 (6-12-2005) Separate compilation: cpp, o, and h files; Implementing binary trees; Ordered scan through contents of tree.
- Class 30 (8-12-2005) Final Examination.
- Class 31 (13-12-2005) Project Demonstrations.
