EEN511 (Software Engineering) Spring 2005

• Book: Applied Data Structures with C++, Peter Smith, pub. Jones and Bartlett, ISBN 0-7637-2562-5.
• Mid-Term: To Be Announced.
• Final Examination ???.
• IMPORTANT: Set up mail forwarding.
• 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
• There are six main areas of study for this class, they are informally:
  1. Advanced and Tricky C++: See items 1, 2, and 3 in notes for Class 1
  2. Object Orientation: Inheritance structures, polymorphism, and all that.
  3. Algorithms and Analysis: See item 4 in notes for class 1
  4. Data Structures: See item 2 in notes for class 2
  5. Software Management: See item 1 in notes for class 2
  6. Fundamental Things: See item 3 in notes for class 2
• Assignments: Not all required. The first one has a due date, and the project is also required. The second one was mostly a make-up for anyone who did not do a great job of the first. Of the reaminder (those marked with a *), you should pick one and do a REALLY really good job of it, OR pick two and do a credit-worthy job of them both.
  1. Due 10th Feb Write a program that uses HTML and CGI to provide a professional-looking windowsy interface, solving the Knapsack Problem by dynamic programming. You may assume that all the inputs are integers, and that the desired sum is not over-huge. The solution should show which of the inputs are used to make the optimal solution.
  2. Due sometime Write a program that solves the Travelling Salesman problem (find minimum cost route that visits each of a number of cities exactly once, returning to start point at the end), for a VERY SMALL data set (no more than 10 cities is necessary). CGI/HTML again, make it look good, but of course I'll look at initial text-mode experiments and give comments.
  3. * 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, preferably using graphics. BUT you DO need to use an efficient algorithm. Depth-first search is not good enough. Breadth first search is barely good enough.
     (Sample data files, 110 cities and 181 roads, available here).
     (Dynamic creation of graphics files in CGI is covered here).
  4. * 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.
  5. * 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.
  6. * 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.
  7. Project Implement a user-friendly C++ AWT (Abstract Windows Toolkit) using all the good and useful features of object oriented programming. (introductory code sample), (enlarged button sample).
• Class History:
  • Class 1 (18-1-2005) General introductions (part 1): Advanced and tricky C++, Algorithms and Analysis; (notes).
  • Class 2 (20-1-2005) General introductions (part 2): Software management, Data structures, Fundamental Things; (notes).
  • Class 3 (25-1-2005) Four Similar Problems: Boolean Satisfiability, Knapsack, Travelling Salesman, Matrix Chain Multiplication; (notes).
  • Class 4 (27-1-2005) Dynamic programming samples: Matrix chain multiplication, Knapsack. (blank tables), (notes, revised).
  • Class 5 (1-2-2005) CGI programming for dynamic web pages without special tools. (notes).
  • Class 6 (3-2-2005) Investigating the Combinatoric function C(n,r): what dynamic programming really is. (notes).
  • Class 7 (8-2-2005) Solving the weekend brain-teaser (notes), Time comparisons (chart).
  • Class 8 (10-2-2005) Motivating and Reintroducing Object Orientation (expanded notes).
  • Class 9 (15-2-2005) Inheritance, Polymorphism, Run-time Type Identification, and Virtual Methods (part 1) (notes).
  • Class 10 (17-2-2005) Inheritance, Polymorphism, Run-time Type Identification, and Virtual Methods (part 2) (executable sizes).
  • Class 11 (22-2-2005) Object Oriented Design Considerations (old notes) (today's notes) (executable sample).
  • Class 12 (24-2-2005) Complicated declarations, Flexarrays/Vectors for any-type contents.
  • Class 13 (1-3-2005) FlexArray implementation, templates, analysis of efficiency (notes).
  • Class 14 (3-3-2005) Introducing Enumerators via Brute-Force All-Combinations; observations on programming style.
  • Class 15 (8-3-2005) More enumerators: integers, permutations, rationals (unedited notes), (gcd proof); what an enumerator really is, and why they are interesting.
  • Class 16 (10-3-2005) Object Oriented design of a Windows programming toolkit. (notes to appear).
  • Spring Break
  • Class 17 (22-3-2005) The Shortest Path problem: basic solution quadratic time and space. (notes to appear).
  • Class 18 (24-3-2005) Improving Shortest Path: Sparse matrix, Proper implementation of linked lists, need for Priority Queue.
  • Class 19 (29-3-2005) Abstract design of Priority Queue; implementation of tree or PQ in array without pointers.
  • Class 20 (31-3-2005) Graph vs Tree vs List; Ordered Binary Trees for searching; Discovering Heap-sort.
  • Class 21 (5-4-2005) Watching cartoons (not my own creations).
  • Class 22 (7-4-2005) Heap sort, Qounting sort, Quick sort, introduced.
  • Class 23 (12-4-2005) Quicksort fully implemented and analysed.
  • Class 24 (14-4-2005) Recursion Elimination applied to quicksort (extra notes: Recursion, An animation of some recursive functions).
  • Class 25 (19-4-2005) Radix sort, times compared; Start of Competitive Strategies and Game Playing.
                      Shortest path notes: Updated.
  • Class 26 (21-4-2005) Game playing expanded: Minimax strategy, Heuristics, Depth restrictions, depth-first, breadth-first, and best-first search.
  • Class 27 (26-4-2005)
  • Class 28 (28-4-2005)