Exam 3 will be on Wednesday, June 26. Practice questions are available. Solutions to the practice questions are also available.
This is a computer programming course using C++. See the syllabus for details.
You should make a habit of working most of the self-test exercises in the book, and checking your answer against the answer in the book. That will help you remember the material.
The following are sample C++ programs with some commentary.
[5/21/02] We began reviewing the basics of C++. We talked about variables, types, assignment statements and expressions. We briefly covered input and output using cin and cout. This material is covered in Sections 2.1 to 2.3 of the text.
[5/22/02] We went over Boolean expressions, if-statements and while-statements. We began looking at how to design loops.
[5/23/02] We looked briefly at nested loops and then turned to designing loops using action-oriented designs and data-oriented designs. We did examples of computing the sum of the first n positive integers and computing powers, where the power is a positive integer.
[5/24/02] We began looking at functions. We looked briefly at the mechanism used to invoke a function. The computation is done on the side, and then the caller is resumed.
Each function can be looked at in two ways. The external view tells WHAT the function does, and is the view used when you want to use the function. The internal view tells HOW the function works, and is the view used when writing the function. Every function should have a contract, which describes the external view of the function.
[5/28/02] We did more examples of functions. We also looked at procedures (functions that do not return a value) and call-by-reference. This material is in chapter 4 of the text, and you should read that chapter.
[5/29/02] We discussed recursion, and did some examples of recursion. This material is in chapter 12 of the text.
[5/30/02] We looked at some more examples of recursion. Then we turned to chapter 5 of the text, which is on elementary object-oriented programming and on input and output. We discussed how to make use of the cin object.
[5/31/02] We looked at using the iostream library to read and write files using objects.
[6/3/02] We began looking at creating classes. A class is a type of object. An object is a collection of variables and methods. We started with structures, which objects that contain only variables, not methods. Then we saw how to bring methods into the structure, creating a genuine object.
[6/4/02] We looked at examples of classes that describe objects with methods inside them. We looked at a class to store and manipulate dates, and another to store and manipulate rational numbers.
[6/5/02] We looked at copy constructors in classes. Then we turned to arrays, and covered how to create an array and how to index into an array.
[6/6/02] Exam 1.
[6/7/02] We began talking about arrays, and did some examples. Typically, each array has a physical size that tells the total amount of available space, and a logical size that tells how much of the available space is actually in use. We defined a null-terminated string, which is an array of characters that contains a null character to mark its end. You can tell the logical size of a null-terminated string by counting how many characters occur before the null character.
Arrays are discussed in chapters 9 and 10 of the text.
[6/10/02] We talked about some general issues on contracts, writing functions and testing. Regression tests are tests that can be run automatically by a script. Then we continued with arrays. We did another example, a function to copy a null-terminated string. We introduced do-loops and for-loops. For-loops are especially useful for dealing with arrays.
[6/11/02] We did more examples using arrays, including linear search and binary search.
[6/12/02] We started talking about sorting, and wrote two functions to sort an array. The first used the Exchange Sort algorithm, and the second used the Insertion Sort algorithm. Both algorithms take time proportional to n2 to sort an array of size n.
[6/13/02] We derived and wrote the quicksort algorithm. It breaks the array up into to two large parts and one small part. It uses itself recursively to sort the two large parts. On the average case, quicksort takes time proportional to n log2(n).
We noted that, if you start at n and successively halve the number that you have, it takes about log2(n) steps to reach 1.
[6/14/02] We discussed two dimensional arrays and arrays of structures. We discussed using named constants for array sizes.
[6/17/02] We went over solutions to the practice questions for the second exam.
[6/18/02] Exam 2
[6/19/02] We began discussing pointers and memory management. See chapter 11 of the text.
[6/20/02] We continued discussing pointers. We discussed the relationship between pointers and arrays, and did an example using dynamic arrays.