EEN511 (Software Engineering) Spring 2003

• Seeing that brute force all combinations is exponential (23-1-2003)
• Simple Inheritance, Polymorphism, and Virtual Methods (13-2-2003)
• The need for virtual in C++ (components example 11-2-2003)
• The mysterious allocation error mystery (11-2-2003)
• Binary Trees, Recursion Elimination, and Enumerations
• Animated Illustration of Recursion Elimination
• Some more animated (mostly sorting) algorithms, by someone else
• Things that have been assigned, Anything to be graded must be received on or before Monday 5th May:
  1. Algorithm Collection
     first hand-in Tuesday 18th February, electronic submission as hw1.
     Webbify your programs, so that they can be accessed form any web-browser, and have a nice clean user-friendly professional-looking interface. Examples, etc., CGI Testing, Meandering Salesman.
     1. Travelling Salesman for tractably-sized data sets.
     2. Rapid Data Access: Dictionary using disc-file hash table.
     3. Knapsack Problem by dynamic programming.
     4. Efficient Priority Queue using a Min-Heap.
     5. Shortest/Cheapest Path (view and download a real data set).
     6. One very-fast sorting algorithm for comparisons.
     7. Sort a linked list efficiently in O(NlogN) time.
     8. Arithmetic on million-digit Integers.
     9. The challenge - make something like this work: cout << format("%2d!=%-10d\n") << n << fact(n);
  2. Implement an AWT (Abstract Windows Toolkit) in C++
     Guidelines for functionality
     Preliminary incomplete version due Thursday 3rd April.
• Unix, C, and C++ Functions Quick Reference.
• Things you should be getting from the two thin books:
  1. Practice of Programming: definitely: 1.*, 2.*; recommended: 4.*, 5.*; coming: 3.*.
  2. Effective C++: nearly everything should now be understandable and useful, except items 7-10 and 28.
• Mid-Term: 3rd to 8th April.
• Final Examination: Tuesday 6th May 2003, 5pm to 7pm.
• Class History:
  • Class 1 (14-1-2003) General introductions; discussion of Effective C++: stdio vs iostream, #define vs const.
  • Class 2 (16-1-2003) Maximum-Sum-Contiguous-Subsequence problem by brute force, seeing it is O(N³); finding max and min ints.
  • Class 3 (21-1-2003) Maximum-Sum-Contiguous-Subsequence problem by dynamic programming, seeing it is O(N); what that really means; seeing that theoretical times are right; friend and private; intro to knapsack problem.
  • Class 4 (23-1-2003) Knapsack problem by Brute-Force All-Combinations; seeing it os O(N2^N); Greedy algorithms: Kruskall's minimum spanning tree works, change-giving doesn't work.
  • Class 5 (28-1-2003) Knapsack problem, partitioning, change-giving all by dynamic programming; Travelling salesman problem.
  • Class 6 (30-1-2003) Merkel-Hellman encryption (based on knapsack problem); introducing "AWT" project.
  • Class 7 (4-2-2003) Generating permutations; co-routines and the need for recursion elimination.
  • Class 8 (6-2-2003) More on "AWT" project; subclassing; virtual methods.
  • Class 9 (11-2-2003) How virtual works (part 1); why virtual requires pointers; why polymorphism is unidirectional.
  • Class 10 (13-2-2003) How virtual works (part 2); deallocation error mystery - danger of assignment operator; copy constructors and operator=.
  • Class 11 (18-2-2003) Type-freedom: designing a liked list of anything (part 1); templates;
  • Class 12 (20-2-2003) Linked list of anything (part 2); templates are bad; using polymorphism; tagged structs; unions;
  • Class 13 (25-2-2003) Hash Tables: giant array indexed by SSN; hashing integers; hashing strings; linear probing is bad; linked lists to resolve clashes; expected lengths of clash lists.
  • Class 14 (27-2-2003) Expected time for hash table retrieval; Fast equality test by hashing; Linear substring search by hashing.
  • Class 15 (4-3-2003) Webbifying your algorithm collection via CGI; start of hashing on disc.
  • Class 16 (6-3-2003) C++ AWT project guidelines and how-to-do-its; disc hash assignment; lseek, fseek, ftell, etc.
  • Spring Break
  • Class 17 (18-3-2003) The next 6 weeks; algorithm assignments; traditional implementation of Vector.
  • Class 18 (20-3-2003) Finishing traditional vector; O(N) or O(N^2); static members and methods; flexible, heirarchical array implementation.
  • Class 19 (25-3-2003) Shortest Path: Dijkstra's all-to-all algorithm; Army-of-Ants one-to-all algorithm; Depth-first with marking algorithm.
  • Class 20 (27-3-2003) Heaps: Min-heap as implementation of priority queue; heap is array; heapsort algorithm.
  • Class 21 (1-4-2003) Alternative to the adjacency matrix; reverse lookup for heap position adjustment; finishing heapsort; analysis of 2-partition quicksort.
  • Class 22 (3-4-2003) Fatal flaw of 2-partition quicksort; 3-partition quicksort O(nlogn) or O(n^2) depending; counting sort; bucket sort; radix sort; all mostly O(n).
  • Class 23 (8-4-2003) (Mid-term due back); why trees need to be balanced; AVL trees; 2-3 trees.
  • Class 24 (10-4-2003) The need for life-long learning; programming language choices and tradeoffs; non-algorithmic languages; logic programming.
  • Class 25 (15-4-2003) Software Metrics 1; Cocomo; software science; function points; business programming style, comparing C and Cobol.
  • Class 26 (17-4-2003) Software Metrics 2: Cocomo2; Cyclomatic complexity/Euler's formula; analysts and programmers; removing the need for programming; functional programming.
  • Class 27 (22-4-2003) Computability 1: Comparing infinite sets; enumerations as measuring stick; ; proof that #rationals = #integers, #functions > #programs×inputs.
  • Class 28 (24-4-2003) Computability 2: Uncomputable functions; Uncomputable real numbers; computable irrational numbers; an enumeration of C++ functions; unprogrammable things; the Halting Problem (Turing).
  • Final Examination Tuesday 6-5-2003 at 5pm in the usual classroom.