EEN218, Programming II, Autumn 2010
Tue Thur 2:00-3:15 in MM117

Examinations:

Assignments:

  1. due Tues 31st August before class: Log into rabbit, enter and run a C++ program.
  2. due Tues 21st September: a nice little database program.
  3. due Mon 4th October: A quick one, adapt your database to use flexibly sized arrays.
  4. due Tues 2nd November: Demonstrate by experiments that merge-sort on long random linked lists is O(N×logN).
  5. due Thurs 11th November: Perfect answer to question 1.

Assistance:

Class History, etc.:

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

Class 1  Thurs 26‑8‑2010   Usual introductions, what the class is really about, reminders about using unix.
Class 2  Tues 31‑8‑2010 Remembering objects and arrays of objects. How much memory do we expect data to occupy? introducing old C strings and printf.
Class 3  Thurs 2‑9‑2010 A database application that really would benefit from the use of pointers.
Class 4  Tues 7‑9‑2010 Pointers and references are the same concept, but C++ treats them differently. Experimentally discovering the four regions of memory allocated to a program: code, globals, heap, and stack. How we would change our database program to make use of pointers.
Class 5  Thurs 9‑9‑2010 Lots of pointers, NULL, ->, new and delete, arrays of pointers. Constructors and methods (functions that belong to objects).
Class 6  Tues 14‑9‑2010 (tell them about script, ftp, and hw submission). Introducing pointers to arrays as a way of effectively resizing an array.
Class 7  Thurs 16‑9‑2010 Dynamic creation of arrays and plugging the memory leak.
Class 8  Tues 21‑9‑2010 Implementing the Resizable Array, also known as a Flex-array, and which will soon become a C++ vector.
Class 9  Thurs 23‑9‑2010 A fool-proof array, protected and public, analysis of the time efficiency of our algorithms.
Class 10  Tues 28‑9‑2010 Full analysis of vector efficiency: incrementing the size is slow, multiplying the size is fast. Remembering the Quadratic sorting algorithms (selection sort, bubble sort, insertion sort) and introducing the mathematical magic of merge sort.
Class 11  Thurs 30‑9‑2010 Big-O Rationale, Examination of Binary Chop Search, it is O(log N). Merge Sort is O(N log N), an example of an exponential problem (satisfiability), and worse. Consequences
Class 12  Tues 5‑10‑2010 Introducing linked lists. A link object has a pointer to a real data object and a pointer to another link and nothing else. A list is made by chaining link objects together. Adding to the end of a linked list is naturally inefficient and often pointless. Adding to the beginning is easy and fast.
Class 13  Thurs 7‑10‑2010 Linked lists again: A link is not the same thing as a list, Keep separate structs for List and Link. Adding, removing, printing, searching, reversing.
Class 14  Tues 12‑10‑2010 Advanced linked list operations: removing from anywhere, adding to the end the easy way.
Class 15  Thurs 14‑10‑2010 Splitting a linked list into two; Combining two linked lists into one, preserving any order they have. A simple recursive function for sorting linked lists, and a proof by induction that it must work.
Class 16  Tues 19‑10‑2010 Random people and timing programs. Deduction, induction, abduction, modus ponens, modus tolens. Solving the recurrence relation T(n)=2n+2T(n/2).
Class 17  Thurs 21‑10‑2010 Binary trees: linked lusts with two tails. Creation, insertion, searching.
Class 18  Tues 26‑10‑2010 Binary trees: contrasting different insertion methods. The recursive "print everything" function, its inductive correctness, and the potential for it becoming a sorting algorithm.
Class 19  Thurs 28‑10‑2010 Test day.
Class 21  Thurs 4‑11‑2010 Review of pointers, pointers to arrays, vector and string implementations, references.
Class 22  Tues 9‑11‑2010 More pointers and thoughts about linked lists.
Class 23  Thurs 11‑11‑2010 Before there were pointers and structs: pointers are just indexes into the big array of memory, new ask the system to give you a position in the array that you can use.
Class 24  Tues 16‑11‑2010 Slowly looking for the end of a list. Pointers to pointers when you can't use references. Quick big O calculations.
Class 25  Thurs 18‑11‑2010 Testlet: Pointers, Vectors, Linked Lists.
Class 26  Tues 23‑11‑2010 Amusements with trees: one, two, three, four.
Class 27  Tues 30‑11‑2010 Testlet: Big O, Trees. and Solutions.
Class 28  Thurs 2‑12‑2010 Lots of review.