EEN218 (Programming 2) Spring 2010
Tue Thur 2:00-3:15 in MM112

Examinations:

Assignments:

  1. Due Friday 19th February: Self-sorting dual vector
  2. Due Friday 26th March: Sort a linked list of strings
  3. Due Thursday 1st April: Perfect your answer to question 2 of the mid-term, making it into a complete working program.
  4. Due Sunday 18th April: Fast tree-based sorting algorithm.
  5. Due Wednesday 12th May: An exciting adventure game.

Some older notes on relevant topics:

Class History, etc.:

Last year's web site
Last semester's Programming I site

Class 1  Tues 19‑1‑2010   Reviewing essential material, part 1.
Mid-terms from Programming I: first, second.
Class 2  Thurs 21‑1‑2010 Reviewing essential material, part 2.
Analysing recursive functions to work out what they do.
Class 3  Tues 26‑1‑2010 Compile-time (static) vs. Run-time (dynamic) operations,
The exact nature of references, pointers, and const pointers,
Investigating memory allocation for variables.
Class 4  Thurs 28‑1‑2010 The re-use of memory for local variables,
What goes wrong when you return an array from a function; argc and argv,
Using new solves the problem, delete for recycling,
What happens if you miscalculate an array index; introducing good old printf,
Beginning to create an error-proof array.
Class 5  Tues 2‑2‑2010 The missing big picture, why flexible data storage depends on pointers.
Implementing an array that can't be misused, and automatically grows as needed ("vector").
Class 6  Thurs 4‑2‑2010 Object oriented programming: functions that belong to objects
class, public:, protected:, members, constructors, destructors, the assignment operator.
Class 7  Tues 9‑2‑2010 Speed/efficiency analysis (details here),
Vectors become very efficient if growth is by multiplication not increment.
Class 8  Thurs 11‑2‑2010 Big O() notation, and considering the consequences of linear, quadratic, cubic, exponention, and logarithmic algorithms.
C++ is not good with two dimensional arrays, solving the problem with our own matrix class.
Class 9  Tues 16‑2‑2010 Shallow copying causes problems with new and delete: a solution with references and many consts.
An alternative with a deep copying assignment operator isn't quite enough.
Class 10  Thurs 18‑2‑2010 The copy constructor, why objects are best passed as const references.
multi-dimensional arrays, not just in C++.
Introducing linked lists.
Class 11  Tues 23‑2‑2010 Heap management for new and delete.
Object orientation for linked lists: separate objects for single links and whole lists.
Class 12  Thurs 25‑2‑2010 The update problem: never have multiple copies of the same data.
Linked lists of pointers to objects: objects in more than one list; ideas for generalised find method.
Class 13  Tues 2‑3‑2010 Generalised operations on linked lists: an inflexible version using functions, then a better version using worker objects. Introducing inheritance.
Class 14  Thurs 4‑3‑2010 Topics for the test and hints for handling it.
Putting things at the end of a linked list, removing items from anywhere.
Class 15  Tues 9‑3‑2010 Mid-Term Examination.
Class 16  Thurs 11‑3‑2010 Reminding ourselves of the basic sorting algorithms (selection, insertion, bubble), working out their speeds, and considering their applications to linked lists.
Spring Break
Class 17  Tues 23‑3‑2010 Fun and games with Sam and Mike.
Class 18  Thurs 25‑3‑2010 Some test review. Inventing the two-pointered version of a linked list that is designed to support the binary chop search.
Class 19  Tues 30‑3‑2010 Binary trees: data structure, insert and search methods, expected speed of access.
Class 20  Thurs 1‑4‑2010 Complete analysis of the recursive full biary tree printing method, and the simplicity attained with recursive insert using references to pointers.
Class 21  Tues 6‑4‑2010
Class 22  Thurs 8‑4‑2010 Practical experiments: measuring search time for perfect, random, and worst-case data in a binary tree.
Class 23  Tues 13‑4‑2010 Using the unix debugger. Output buffering delays printing on cout: fflush(). Separate compilation for libraries: .cpp, .h, and .o files.
Class 24  Thurs 15‑4‑2010 More experience with trees: saving a tree so that its structure can be rebuilt exactly, realising that binary trees can easily be adapted to create a useful representation of arithmentic expressions.
Class 25  Tues 20‑4‑2010 End-Term Examination.
Class 26  Thurs 22‑4‑2010 Analysing mergesort: literally millions of time faster than basic sorting methods.
Mergesort is very easy for linked lists.
Class 27  Tues 27‑4‑2010 The absolute need for delete or bypassing repeated news for linked-list sorting. Merge-sort for arrays: all operations are easy, except that it can't be done using only the original array. The merge operation needs an additional temporary array.
Class 28  Thurs 29‑4‑2010 Test review. Effective non-recursive merge-sort for arrays. A short hint of quicksort.