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

• Official Book:
  • Algorithms in C++ parts 1 to 5, Robert Sedgewick, pub. Addison-Wesley, ISBN 0-201-35088-2 and 0-201-31663-3.
• Alternate Books that you may be interested in:
  • 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.
• 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: Tuesday 27th March.
  • Final Examination: Tuesday 8th May, 5.00 p.m.
• Assignments:
  1. (due Tuesday 6th February) Implement the Knapsack algorithm by dynamic programming. The inputs to your program should be a simple list of integers; the first is the maximum capacity, the second is the number of "packages", and the remainder are the weights of those packages. The output should be the list of packages to be taken, whose total weight is as close to the capacity as possible without exceeding it. Do not make your array bigger than necessary.
  2. (due Tuesday 13th February) Implement, as proper C++ objects, (1) an enumerator for all possible patterns of N 0s and 1s, and with the minimum of extra coding, (2) an enumerator for all possible combinations of items in an array of ints. Use (1) to solve the Boolean Satisfiability problem for the combinational logic circuit of your choice (at least 6 inputs), and use (2) to produce a brute-force solution to the knapsack problem. (Samples).
  3. (due Tuesday 27th February) Implement an Object, it can contain any data you like, but must have a method called priority() that returns an int. Implement an efficient Heap of objects using an array (you may assume that the maximum number of objects is known in advance). Use your heap of objects to sort a large number of ints in O(n×log(n)) time.
  4. (due Monday 19th March) Using the data in the files "locations.txt" and "majorroads.txt" (available and described here), and by adapting the object and heap created for the previous assignment, write a program that finds the shortest route (by road) from any location to any other. Your program should be fast, and should print the route found in a user-friendly form that could be used as driving instructions (do not repeat useless information).
  5. (due Tuesday 6th March in class) Draw the 2-3-tree that results from a sequence of insertions chosen by you.
  6. (due Tuesday 10th April in class) Research your randomly assigned software engineering topic and make a ten minute in-class presentation.
  7. (due Sunday 29th April) "Logo".
• Class History:
  • Class 1 (16-1-2007) Improving slow algorithms with memoisation and dynamic programming.
  • Class 2 (18-1-2007) The knapsack problem (blank table), Satisfiability, exponential computations in general.
  • Class 3 (23-1-2007) Enumerators, The Shortest Path problem, swarm of ants, analysis. (pictures: pos neg).
  • Class 4 (25-1-2007) Better shortest path algorithm using a heap, Heaps, Heaps living in arrays.
  • Class 5 (30-1-2007) Heapsort complete. Design of objects for shortest path. Reminder of vectors.
  • Class 6 (1-2-2007) Parsing: Lexical analyser, grammar, BNF, expression checker.
  • Class 7 (6-2-2007) Really parsing, constructing a tree and displaying it (recognise.doc).
  • Class 8 (8-2-2007) Evaluator for parse trees, terminology, adding commands, language design problems.
  • Class 9 (13-2-2007) Enumerators for all natural numbers (not limited to 32 bits), all strings, all programs, all rational numbers.
  • Class 10 (15-2-2007) Impossibility of an enumerator for reals, what it all signifies.
  • Class 11 (20-2-2007) Review of fast data access part 1. analysing vectors, thinking about hash tables.
  • Class 12 (22-2-2007) Access times for a tree, problems with poor balance, introducing 2-3-tree.
  • Class 13 (27-2-2007) Analysing hash table (formulas), disc indexes, deleting from a tree.
  • Class 14 (1-3-2007) Details of 2-3-tree. Recursion as backtracking in trees. Coding methods for 2-3-trees.
  • Class 15 (6-3-2007) AVL tree algorithms for balancing a binary tree: introduction.
  • Class 16 (8-3-2007) Solidifying and clarifying our understanding of AVL algorithms.
  • Non-class (13-3-2007) (Spring Break)
  • Non-class (15-3-2007) (Spring Break)
  • Class 17 (20-3-2007) Radix sort. Review and analysis of mergesort, efficient sorting of a linked list.
  • Class 18 (22-3-2007) Counting sort, Review and analysis of quicksort.
  • Class 19 (27-3-2007) Mid-term test.
  • Class 20 (29-3-2007) Recursion elimination, enumerators for binary trees.
  • Class 21 (3-4-2007) Failure to remove something from a 2-3-tree. Further recursion elimination.
  • Class 22 (5-4-2007) no class today.
  • Class 23 (12-4-2007) Your presentations (part 1):
    • John: Halstead's Software Science
    • Kevin: JSD
    • Abdulaziz: Dataflow Analysis and Testing
    • Luis: COCOMO
  • Class 24 (17-4-2007) Your presentations (part 2):
    • Mike: Formal Methods
    • Ashley: VDM
    • Gonzalo: Design Patterns
    • Juan: Chief Programmer Teams vs. Extreme Programming
  • Class 26 (19-4-2007) Declarative programming: the aqpplicative/functional style, lazy evaluation.
  • Class 27 (24-4-2007) Godel's incompleteness theorem, The halting problem, Turing's thesis and computability.
  • Class 28 (26-4-2007) Logic programming, Software metrics, Cobol.