EEN511 (Software Engineering) Spring 2004

• Book 1: Algorithms in C++, Sedgewick, Addison-Wesley, 1992 edition, 0-201-51059-6.
• Book 2: Effective C++, Meyers, Addison-Wesley, second edition, 1998, 0-201-92488-9.
• Unix, C, and C++ Functions Quick Reference.
• Mid-Term: To Be Announced.
• Final Examination on Thursday 6th May, 5:00 pm.
• IMPORTANT: Set up mail forwarding.
• Assignments: You pick which ones to do (minimum number will be announced), make then web accessible (CGI) and make them look reasonably good.
  1. Knapsack (1): solving the knapsack problem with dynamic programming: Given the weights of a variable and potentially large number of packages, and a maximum total weight that may be less than the sum of the package weights, work out which subset of the packages has the maximal total weight without exceeding the maximum.
  2. Knapsack (2): solving the knapsack problem for limited inputs with brute force (try all combinations) method.
  3. Knapsack (3): solving the modified knapsack problem: each package has independent weight and value; there is a maximum total weight that can not be exceeded, but you must find the maximum total value within that constraint.
  4. Minimum Edit Distance: Given two strings, which may be quite long, produce a numeric measure of how similar they are by working out the minimum number of simple editing operations that would be required to change one string into the other. Operations are insert some character at cursor position, and delete character to right of cursor position. The cursor may be moved to the right any number of times without it counting as an editing operation.
  5. Minimum Spanning Tree: Given a description of some nodes (maybe cities) and the costs of constructing direct links between various pairs of them (the input data may be provided in any reasonable format), work out the minimum cost of constructing a network in which every node is connected to every other node, at least indirectly (it doesn't matter how many other nodes must be traversed).
  6. Shortest Path: Given a description of some nodes (maybe cities) and the cost of travel between any pairs of nodes, find the cheapest route from any one node to any other node. Display the route in some user-friendly form, but you do not need to use graphics. BUT you DO need to use an efficient algorithm. Depth-first search is not good enough. Breadth first search is barely good enough.
  7. Game Playing: Invent a moderately simple game like "noughts-and-crosses"/"tick-tack-toe" or draughts/chequers or chess (but nothing like as complicated as chess itself), and make a program that plays the game against a human player. Use a best-first search with limited depth so that the program will play a reasonably good game, not just looking one move ahead each time.
  8. Tree Drawing: Given a sequence of short strings or of numbers, create an ordered binary tree containing those numbers, and draw it (using graphics of course) in the traditional form, showing the root at the top, and with lines showing connections between parent and child nodes, with the child nodes positioned below and to the left or right of their parents. The challenge is in the drawing; no points for just writing a program that builds a tree; that is well-known stuff.
  9. Super Calculator: A program that evaluates expressions involving the standard arithmetic operations (plus, minus, times, divided by) on integers, but has no limit on the sizes of the inputs or of the outputs. This is not the same as the simpler assignment you may have done for an earlier class. You must not make any limit at all on the number of digits in a number. The only limits should be those imposed by the amount of memory the computer has available. You will need to make fairly efficient use of memory; a linked list or vector of digits is OK as the underlying implementation, but you must get destructors working properly to ensure memory is released properly when it is no longer in use. You may use either infix or "reverse polish" notation for the computations (i.e. to compute 200*37+6*93, you can make the user enter (200*37)+(6*93) or 200,37,*,6,93,*,+); it is your choice, but remember that parsing is not a trivial problem, and reverse polish removes the need for parsing.
  10. Generic Enumerator: (It does not make sense to give this one a web interface, so just make it a normal program) Using all the aspects of good object oriented programming style, create a generic Enumerator class and a number of Enumerable "container" classes (including at least OrderedBinaryTree, HashTable, and LinkedList), make it so that every object of an enumerable type has a GetEnumerator method which returns an enumerator for its contents. Your containers should all be general purpose (e.g. Linked List of Anything, rather than Linked List of Ints). Do not use templates to "solve" the problem.
• For Reference:
  • Complete example (with explanation) of interactive CGI programming
  • Complete example (with explanation) of creating graphics for display by CGI programs
• Class History:
  • Class 1 (20-1-2004) General introductions; what the class is about; different sorting algorithms.
  • Class 2 (22-1-2004) Some polynomial algorithms (e.g. sorting, searching, matrix multiplication) and some exponential ones (e.g. optimum matrix chain multiplication, knapsack packing); what the difference really means; tractable vs. intractable vs. uncomputable.
  • Class 3 (27-1-2004) Ackerman's function; the knapsack problem brute force and by dynamic programming.
  • Class 4 (29-1-2004) What really is dynamic programming? The combinatoric function with factorials, addition only, memo function, and finally dynamic programming.
  • Class 5 (3-2-2004) Seeing recursive solutions when the problem doesn't seem naturally recursive; Maximal-sum contiguous subsequence.
  • Class 6 (5-2-2004) How to do CGI programming; How close are two strings? Minimum Edit Distance.
  • Class 7 (10-2-2004) Greedy algorithms; difference between change-giving and knapsack (none); Minimum Spanning Tree.
  • Class 8 (12-2-2004) Time complexity of M.S.T.; a greedy algorithm for it; Demonstrating its Correctness; Introducing Heaps.
  • Class 9 (17-2-2004) Heaps: insertion and removal; Heaps and balanced binary trees implemented as arrays; Heapsort is O(n×logn) and in-place.
  • Class 10 (19-2-2004) The official object oriented view: linked lists; special container classes; remembering members and methods.
  • Class 11 (24-2-2004) Strange C++ things: special constructor form; inline; nested classes; member and method pointers; static.
  • Class 12 (26-2-2004) Container classes continued: linked lists the right way round; the need for and complexity of const declarations; pseudo-constructor static methods.
  • Class 13 (2-3-2004) Redefining operators; reference variables and results; accidentally shared structures; accidental destruction; assignments are complicated.
  • Class 14 (4-3-2004) Full set of essential methods: default constructor, copy constructor, assignment operator, destructor; avoiding accidental destruction; reference counts; multi-file compilations (how to use CC, .cpp, .h, and #include properly).
  • Class 15 (9-3-2004) Graph exploration; any path, shortest path, branch and bound. Game playing, exploring trees that don't exist; minimax; task list.
  • Class 16 (11-3-2004) (Test handed out) Minimax searches; task list control of non-recursive graph exploration.
  • Class 17 (23-3-2004) (Test due in today). Demonstrations: Depth-first and Breadth-first search without recursion; introducing best-first search with priority queue.
  • Class 18 (25-3-2004) Generic graph-search algorithm; relevant data structures; adjacency matrix; vectors; templates.
  • Class 19 (30-3-2004) Priority Queues, enhancement of minheap to optimise implementation.
  • Class 20 (1-4-2004) "Vector of anything"; inheritance, polymorphism, and all related topics.
  • Class 21 (6-4-2004) Hash tables: speed, implementation, usefulness.
  • Class 22 (8-4-2004) Ordered Binary Trees; just linked lists with two nexts.
  • Class 23 (13-4-2004) Recursion compared to loops for tree operations; Recursion Elimination.
  • Class 24 (15-4-2004) (Today's notes) Better recursion elimination; Enumerators; Bijection is complete test for set-size equality.
  • Class 25 (20-4-2004) Size of integers is measure of infinite sets; set enumerable means no bigger than integers; #ints = #rationals = #strings = #programs = .
  • Class 26 (22-4-2004) Why is the smallest infinite set; Integer Decision Functions, and why they are not enumerable; and bigger infinities; uncomputable functions, sets, and numbers, insoluble problems.
  • Class 27 (27-4-2004) The Halting Problem, Turing's Thesis; Can't detect infinite loops, can't predict run-time errors, can't verify initialisation of variables.
  • Class 28 (29-4-2004) Hilbert, Godel, Turing; Even infinite computers must be incapable of self-analysis; The 30 minute MBA.