EEN318, Programming III, Autumn 2009

Assignments

     1    Due 29 Sept.    Make an interpreter for a simple programming language along the lines discussed in class. The language must include at least expressions involving addition, subtraction, and parentheses, an assignment statement and a print statement. Your interpreter should be capable of parsing a whole program, printing its representational tree, and running it.
E-mail it directly to me, not to grader. Send me a sample run along with your program. 		    
     2    Due 30 Nov.    assignment, DEM files, alphaplaces. Remember I need screen-shots too.     
     3    Due 13 Dec.    Make your programming language useful. It needs loops and conditionals and statements for input and output. It should be something that is actually useful to have around. It needs to have a symbol-table implemented as a hash table. Send me a good demonstration run as well as your program.     
     4    Due 13 Dec.    Improve your map assignment. The user should be able to zoom in or out, select two locations, and be shown the shortest route between them using major roads. Convenient driving instructions should also be provided in text.
Here are the road and intersection data sets.
Remember I want screen shots as well as your code. 		    

Class History

     Class 1    Thurs‑27‑8‑2009  General introductions, what more could there be to learn about programming?     
Class 2 Tues‑1‑9‑2009 Designing a nice self contained object to simplify input with complex structure.
Class 3 Thurs‑3‑9‑2009 The problem of parsing: producing a tree that repreents the structure of an expression.
Class 4 Tues‑8‑9‑2009 Separate compilation (.cpp, .h, and .o files). Beginning an object oriented parser for a programming language.
Class 5 Thurs‑10‑9‑2009 The basic plan for reading and executing programs.
Class 6 Tues‑15‑9‑2009 A summary of today's developments. Sequences of statements, assignments, parentheses, etc.
Class 7 Thurs‑17‑9‑2009 Review of constructors, pointer creation, new, delete, etc.; considering conditional statements and the full variety of operator priorities.
Class 8 Tues‑22‑9‑2009 Considering the map object. Class diagrams (UML), using "protected" to allow invisible implementation changes, the Hash function, unsigned, the problem with -231, introducing Hash Tables.
Class 9 Thurs‑24‑9‑2009 Probabilities for hash tables, Poisson distribution, collisions, the need for collision resolution; linear probing is not too good, hash table is array of linked lists; resizing table when overfull gives fast constant average access time.
Class 10 Tues‑29‑9‑2009 Programming at a lower level: C strings, strcpy, strlen, etc, Scratchy notes.
Seeing where things are in memory, the experiment.
Class 11 Thurs 1‑10‑2009 Complicated pointer type-casts, objects in memory, accidents with arrays and pointers, the pointer to anything type "void *", the conformity clause. Today's example. Details of the floating point representation.
Class 12 Tues 6‑10‑2009 Inheritance, no duplicated code, "pointer to anything", constructor call sequence, static members, virtual methods.
Pet Club.
(Wed‑7‑10‑2009 Academic alerts due)
Class 13 Thurs 8‑10‑2009 Virtual methods for tree nodes.
Pure virtual, what ** can mean in C++, variable parameter lists, macros are evil.
Class 14 Tues 13‑10‑2009 The Missing Day.
Class 15 Thurs 15‑10‑2009 Getting sense and value from virtual methods: today's developments.
Class 16 Tues 20‑10‑2009 Defining terms, and the technicalities of various constructors and operators.
Today's notes, considerably enhanced.
Class 17 Thurs 22‑10‑2009 Investigating a non-text file. od, fopen, printf, fprintf, fgetc, fclose.
The experimental program, and the data files.
Class 18 Tues 27‑10‑2009 Expect on the test: Parsing, Hash tables, C strings ptrs etc, Inheritance etc.
Binary unformatted files: open, read, write, close. classroom scratchings, also see here.
special notes for windows/visual studio.
Class 19 Thurs 29‑10‑2009 Mid Term Test.
Class 20 Tues 3‑11‑2009 Dealing with large inter-connected data sets, starting to think about shortest-path algorithms.
Negative Nebraska, Positive Nebraska.
Class 21 Thurs 5‑11‑2009 What we learned from the test.
Class 22 Tues 10‑11‑2009 Shortest path by treating a graph as a tree, recursive depth-first search with branch-and-bound.
Class 23 Thurs 12‑11‑2009 A good shortest path algorithm (breadth first), a priority queue. Survey of attitudes towards life-long learning.
Class 24 Tues 17‑11‑2009 Take-home mini-test, due next Tuesday.
The D algorithm for everywhere-to-everywhere shortest path calculation in cubic time, and example of Dynamic Programming.
Class 25 Thurs 19‑11‑2009 Dynamic Programming and Memoisation. The combinatoric function.
Class 26 Tues 24‑11‑2009 (the first take-home mini-test is due today)
Second take-home mini-test, due 3rd December. Review of sorting methods, especially radix and merge sort, and their historical importance.
Class 27 Tues 1‑12‑2009 The trouble with mergesort or arrays. Quicksort, pivot choice, time and memory analysis.
First thoughts on keeping data secret. The exclusive-or scheme.
Class 28 Thurs 3‑12‑2009 (the second take-home mini-test is due today)
Cryptographic methods, one time pads, the R.S.A. algorithm, ABmodN quickly.