EEN218 (Programming 2) Spring 2011
Tue Thur 5:00-6:15 in MM215

Examinations:

Assignments:

  1. Due Tues. 8th February, Implement Selection Sort and Bubble Sort and measure their performance
  2. Due Tues. 1st March, Supercalculator (Part 1): able to add, subtract, multiply, etc. numbers that are thousands of digits long.
  3. Due Fri. 8th April, Supercalculator (Part 2): negatives, comparisons, full multiplications, and divisions.
  4. Due Fri. 29th April, Linked-List Database.
  5. Due Sun. 8th May, Two-Tree Search Engine.

Some older notes on relevant topics:

Class History, etc.:

Last semester's web site
Class 1  Tues 18‑1‑2011   Introductions, thinking analytically about some familiar algorithms, seeing linear, quadratic, and logarithmic running times.
Class 2  Thurs 20‑1‑2011   Getting refamiliarised with unix, generating random strings as preparation for some sorting and timing.
Class 3  Tues 25‑1‑2011   Reminder of Quadratic sorting algorithms: which is which?
Our development of insertion sort, Debugging.
Class 4  Thurs 27‑1‑2011   More debugging. Making the sorting program verify itself. Making it time itself too. Real engineering: experimental verification of our theoretical conclusion that insertion sort is quadratic in time. Logarithmic Graph Paper - you can download it and print it here.
Class 5  Tues 1‑2‑2011   Making an array that can grow, so you never have to worry about how big to make it. Beginning to consider the trade-offs when the array is enlarged: double the size - fast but wastes memory; add 1 to the size - no wasted memory but very slow.
Class 6  Thurs 3‑2‑2011   Bits and bytes and ints and pointers. Where things are in memory.
Class 7  Tues 8‑2‑2011   The mathematics of making an array grow. Resizing by increment (cap=cap+1) means quadratic time, resizing by scale (cap=cap*2) mean linear time. Using ftp and pine.
Class 8  Thurs 10‑2‑2011   A problem with a nice clear solution, which turns out to be a horrible cubic algorithm, and Part 2 of the notes: a nice linear algorithm.
Class 9  Tues 15‑2‑2011   An exponential algorithm (1, 2), Time.
Thinking about implementing very large numbers.
Class 10  Thurs 17‑2‑2011   Detailed thoughts on the big numbers: many simple functions working together for a complicated result.
Class 11  Tues 22‑2‑2011   Object Orientation. Constructors, Methods (functions inside structs), Members (variables inside structs), protected: and public:.
Class 12  Thurs 24‑2‑2011   Object oriented example: an easy-to-use matrix.
Class 13  Tues 1‑3‑2011   Some language comparisons: C++, C, Pascal, BCPL, Algol.
Introducing linked lists.
Class 14  Thurs 3‑3‑2011   More Linked Lists.
Class 15  Tues 8‑3‑2011   Test Day.
Class 16  Thurs 10‑3‑2011   More linked lists - searching, measuring.
payroll database - a linked list of structs.
Spring Break
Class 17  Tues 22‑3‑2011   We should have used pointers - the payroll database revisited.
Splitting a linked list into two halves. Recombining the two halves back into one list.
Class 18  Thurs 24‑3‑2011   Inserting a new item in the correct place in an already ordered linked list. Accidentally discovering insertion-sort for linked lists.
Class 19  Tues 29‑3‑2011   start here. The very special way to sort a linked list: split the list into two equal parts, sort those parts separately, merge to two sorted parts into a sorted whole again.
Class 20  Thurs 31‑3‑2011   start here. Complete development of merge-sort, and seeing why its time is N×log(N), and just how fast that really is.
Class 21  Tues 5‑4‑2011   More merge-sort. For arrays, it can't be "in place", it needs an additional temporary array to work in.
Class 22  Thurs 7‑4‑2011   Introducing the ideas behind Binary Trees: like a linked list modified to support binary chop search; each link (node) has two "next" pointers.
Class 23  Tues 12‑4‑2011   Tree functions: searching, inserting new data, and the recursive print-everything. More inductive reasoning to see why it works.
Class 24  Thurs 14‑4‑2011   (The vector example (program, firstnames, lastnames)
A simple recursive tree insertion method, and the recursive print function again.
Sun 17‑4‑2011   Voluntary review session with Mike the Lab Guy, 3:00 p.m. in EB 216.
Class 25  Tues 19‑4‑2011   A link and a list are not the same thing, so don't use the same struct to represent both. Add to front and add to end both become easy, but remove from end remains unpleasant.
Class 26  Thurs 21‑4‑2011   Test Day.
Class 27  Tues 26‑4‑2011   A binary tree is always one of two things: either NULL or a peice of data attached to two other trees. In most cases that picture makes function design easier. Many tree function examples, making a tree draw itself.
Introducing Quicksort.
Class 28  Thurs 28‑4‑2011   Which is the fastest sorting algorithm?
The original publication of Quicksort, and implementation part 1, part 2, and The computers it was tested on.
The perils of poor pivot choice. Really working out the three-partition Quicksort algorithm.