EEN511 (Software Engineering) Spring 2006, Tue Thur 5:00 - 6:15

• Book:
  • Applied Data Structures with C++, Peter Smith, pub. Jones and Bartlett, ISBN 0-7637-2562-5.
  • or Introduction to Algorithms, Thomas Cormen, pub. MIT press, ISBN 0-07-013151-1 or 0-262-03293-7.
  • or Algorithms in C++ (1992 edition), Robert Sedgewick, pub. Addison-Wesley, ISBN 0-201-51059-6.
  • or Algorithms in C++ parts 1 to 5, Robert Sedgewick, pub. Addison-Wesley, ISBN 0-201-35088-2 and 0-201-31663-3.
• For Reference:
  • Introductory Guide to Using Unix
  • Unix, C, and C++ Functions Quick Reference.
  • Introduction to, and documentation of, C++ strings.
  • Graphics Library downloads and documentation
  • Complete example (with explanation) of interactive CGI programming
  • Complete example (with explanation) of creating graphics for display by CGI programs
  • Graphics library downloads and documentation and Visual C++ how-tos
• Examinations:
  • Mid-Term Examination: Thursday 9th March.
  • Final Examination: Thursday 4th May, 5:00 p.m.
• Assignments:
  1. Solve the knapsack problem using dynamic programming. Details.
  2. Design and implelement your own programming language.
     1. Plans and lexical analyser due Tuesday 7th March.
     2. Parser and tree printer due Thursday 6th April.
     3. Ability to run moderately simple programs due Thursday 13th April.
  3. Choose any three from this list:
     1. Make your nice graphical U.S.A. shortest route finder efficient by using a heap instead of a plain array. If you were not in 318 and do not want to create the basic graphical program, I will give you one to work with.
     2. Make an efficient implementation of 2-3-trees. Make it test itself with a large amount of data. This may be taken from a large file, or generated randomly. Check that it really is working efficiently.
     3. Make an efficient implementation of AVL trees. Make it test itself with a large amount of data. This may be taken from a large file, or generated randomly. Check that it really is working efficiently.
     4. Satisfiability tester (see class 2 for reminder). Write a program that accepts a combinational logic (written as a formula) as input, for example X=((A and not B) or (B and not A)) and (not A or not B) and lists all combinations of the input variables that result in the formula being true.
     5. Make a graphical demonstration of heapsort and a couple of simpler sorts for educational comparison. The data in the array is shown as a bar graph (height of bar i is proportional to value of item i), which is redrawn after each operation, to illustrate progress.
     6. Make a disc-resident B-tree or hash table as an index into a large data set. here are some sample data sets.
     7. Make your programming language support function definition and call.
     8. Create a dynamic programming solution for the missile defense system problem described here.
• Class History:
  • Class 1 (17-1-2006) Introductions and Plans.
  • Class 2 (19-1-2006) Satisfiability, Knapsack, Expensive Computations; (Notes); Enumerations.
  • Class 3 (24-1-2006) Completing Knapsack (blanks: pdf, doc), Combinations, start to general form of dynamic programming.
  • Class 4 (26-1-2006) True nature of dynamic programming: tabular elimination of recursion and repetition; discovering underlying recursive definitions; introducing Minimum Edit Distance.
  • Class 5 (31-1-2006) Finishing minimum edit distance (notes); Introducing Parsing (samples).
  • Class 6 (2-2-2006) Continuing parsing: ungetc, line buffering, etc; handling variables; algebraic printing.
  • Class 7 (7-2-2006) Happy friendly recursion: (pylon.cpp, pylon.exe, trees.cpp, trees.exe); Executing simple programs.
  • Class 8 (9-2-2006) Standard parsing techniques: priority of operations and proper parentheses. (the printf trick).
  • Class 9 (14-2-2006) Sophisticated parsing for real languages; grammars. (v6), (parsing v7).
  • Class 10 (16-2-2006) Statements; B.N.F.; direct mapping to parser; language design; executor.
  • Class 11 (21-2-2006) More enumerations: Natural numbers (without size limit), knapsack solutions, strings, C++ programs.
  • Class 12 (23-2-2006) Tidied enumerations; the possibility of an undecidable set; sizes of infinities.
  • Class 13 (28-2-2006) Heaps: definition, theory, implementation in a cost-free array.
  • Class 14 (2-3-2006) Application of heaps to shortest path, speedup obtained; analysis, implementation details. (speed-demo, data1, data2).
  • Class 15 (7-3-2006) Doing things with binary trees.
  • Class 16 (9-3-2006) Mid-term test.
  • Spring Break
  • Class 17 (21-3-2006) Printing a tree; Non-recursive tree printing; Enumerator for tree content (sample code).
  • Class 18 (23-3-2006) Partial exam review; Linearising a tree.
  • Class 19 (28-3-2006) Hash tables; Dynamic hashing for true constant time access; introducing 2-3-trees.
  • Class 20 (30-3-2006) Language design in conjunction with parser design; a little more about 2-3-trees.
  • Class 21 (4-4-2006) 2-3-trees finalised, implementation methods: red-black trees; intro to AVL trees.
  • Class 22 (6-4-2006) Analysis of 2-3-trees and AVL trees. Completion of AVL algorithm/rotations.
  • Class 23 (11-4-2006) Disc-resident index files; Relative efficiency, loops/recursion, for/while, if-sequence/switch.
  • Class 24 (13-4-2006) Implementing local variables and functions; Efficiency - when paging bites you.
  • Class 25 (18-4-2006) Optimisation: array vs linked list efficiency; new/delete node-stash; string vs. char*.
  • Class 26 (20-4-2006) Decision procedures; The Entscheidungsproblem; logic is incomplete; Turing's thesis; Impossibility of Omniscience.
  • Class 27 (25-4-2006) Management of Software Projects; teams, cost estimation, business programming models.
  • Class 28 (27-4-2006) The future of programming: implementing specifications, eliminating syntax and complex semantics.