CSCI 2610/2611
Summer 2000
Last modified 7/26/00
Announcements
Practice questions for exam 3 are available below under
self-test exercises. Solutions are also available.
Syllabus
This is a computer programming course using C++. See the
syllabus for details.
Assignments
Please follow the new instructions on
handing in assignments.
Self-test exercises
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.
Additional exercises, with solutions, are as follows.
Computers
For the lab, we will use the computers in Austin 320. They
are dual boot computers, running either Windows NT or Solaris 2.x.
We will use Solaris for the assignments. Solaris is a brand of Unix.
Each of you will receive an account. You account is usually
your first initial followed by your last name, up to a total of
eight characters. So if you name is Milton Stanikowski, your
id is mstaniko. In some cases it is necessary to choose other
names. Your password is probably the last 6 digits of your
social security number.
The first day of laboratory, you should try your account. A
brief tutorial on Solaris will also be given.
Notes on using Solaris are available.
Note. The most pleasant text editor to use for software
development under Unix is Emacs. The notes on Solaris discuss
how to use Emacs.
Notes on writing programs, and how programs are graded
Please read the notes on grading programs.
Small scale software development notes
Please read, over time, the
notes on small-scale software development.
Sample C++ programs
Here are a few sample programs.
Lecture summaries
- [6/22/00] We went over the basics of C++, including basic types,
variables, assignment statements, expressions and input/output
statements. Material covered is in sections 2.1, 2.2 and 2.3
of Savitch.
- [6/23/00] We discussed the orthogonality rule for expressions.
(Any expression can occur where any other expression can, as long
as the value of the expression makes sense in that context.)
We covered flow of control, including if-statements
and while-loops. We talked about tactics for designing loops.
The two main tactics are
- Action-oriented design. Here, you think primarily about
the actions that you want to do over and over.
- Data-oriented design. Here, you think primarily about
the values that you want to compute, and let the actions follow
later.
This material is mostly in sections 2.4 and 2.5 of Savitch.
- [6/26/00] We discuss more on loops and introduced do-loops
and for-loops. We began discussing functions. Material on functions
is in Savitch, sections 3.1 to 3.3.
- [6/27/00] We continued to discuss functions, including
local variables, void functions and calling modes.
The available calling modes
are call-by-value and call-by-reference. See sections
3.4-3.5 and 4.1-4.2 of Savitch for this material.
- [6/28/00] We discussed recursion. It is covered
in chapter 12 of Savitch. (12.1 and 12.2 should be readable.
Section 12.3 uses arrays in an example, which we have not
yet covered.
- [6/29/00] We looked at the Towers of Hanoi puzzle as an
example of recursion. We studied objects from the outside,
using the input and output stream objects as examples. This
material is in chapter 5 of Savitch.
- [6/30/00] We began looking at objects from the inside.
We implemented some functions on rational numbers, using a
procedural style and a structure. This material is covered
in section 6.1 of Savitch.
- [7/3/00] We will look at object-oriented computing.
An example class Date was written, where a Date object holds
a date and some operations that manipulate dates.
- [7/4/00] Holiday.
- [7/5/00] We went over questions on the practice exam, and
continued to explore object-oriented programming. We partially
completed an implementation of rational numbers in an object-oriented
style. Note: We have not talked about inheritance. That
is an important concept of object-oriented programming, but is
beyond the scope of this class.
- [Thursday, 7/6/00] Exam 1.
- [7/7/00] We looked at breaking a program into
separate modules. We also picked up a little more C++, including
break and continue statements and switch statements. This is
in Savitch, chapter 7. You should read that entire chapter.
- [7/10/00] We introduced arrays. An array is a collection of
variables that are referred to not by their names but by their
position, or index, in the array.
We did a few examples using arrays, including finding the maximum
value in an array, adding up all of the values in an array and reversing
an array.
Each array has two different sizes. The physical size is the
total number of variables in the array. It tells how much memory
is available. The logical size is the number of those variables that
are actually in use. The logical size is usually smaller than the
physical size. (Think of the array as the tables in a restaraunt.
The physical size is the total number of tables. The logical size
is the number of tables that are occupied.)
When an array is passed to a function, it is always passed by
reference. You do not use an & symbol; call-by-reference is
automatic.
When you pass an array to a function, you usually also pass the
logical size of the array as a separate parameter.
- [7/11/00] We examined null-terminated strings. This is a widely
followed convention of using a null character ('\0') as an
end marker in strings. The string "abc" is stored in
an array of characters as the characters 'a', 'b' and 'c' followed
by a null character to mark the end. Standard library function
strlen returns the length of a null-terminated string, and
strcpy(A,B) copies string B into string A.
We also began to look at the problem of sorting an array.
We implemented the exchange sort algorithm. To sort an array of
size n, exchange sort does n(n-1) comparisons in the worst case.
- [7/12/00] We implemented and analyzed the insertion sort
algorithm. It does about n(n-1)/2 comparisons, in the worst case,
to sort an array of size n.
We looked at the ideas behind the quicksort algorithm.
- [7/13/00] We implemented quicksort, including the partition
algorithm. We also analyzed quicksort, finding that it takes about
n log2n steps on the average. Its worst case is still
about n2/2, which is quite slow. (There do exist
methods for sorting arrays that take about n log2n steps
even in the worst case.)
- [7/14/00] We looked at searching arrays. Linear search
(searching the entire array) takes time proportional to n to search
an array of size n, in the worst case. Binary search is another
algorithm that can only be used on an array that is already sorted.
It compares the value being sought with the middle value in
the array, and then does a recursive call to search either the
first half or the second half. It takes time proportional to
log2(n) to search an array of size n.
We also looked at two-dimensional arrays. See section 10.2 of Savitch.
- [7/17/00] We continued to look at two-dimensional arrays, and
noticed that the compiler needs to be told the physical number
of columns in order to make use of a two-dimensional array.
We derived an algorithm for the edit distance problem, but did
not write C++ code for it. The edit distance problem is to find
the smallest number of basic edit operations that are needed to
convert one string into another. The basic edit operations are
- Replace a character by another character.
- Insert a character.
- Delete a character.
This algorithm is intermediate difficulty. It is more difficult to
derive than any that we have done before this, but is still quite
manageable, once you see how to solve the problem.
- [7/18/00] We finished the edit distance problem, and
begnn looking at the computer's memory, and how to make more
effective use of it. We introduced pointers.
- [7/19/00] We did review for the exam, and looked some more
at pointers and operations on pointers. Pointers are discussed
in chapter 11 of Savitch.
- [7/20/00] Exam 2.
- [7/21/00] We went over the exam, and worked more on the
basics of pointers, including allocating arrays and creating
arrays of strings.
- [7/24/00] We looked more at pointers. at how pointers are used with
structures and objects, heading toward linked lists. We looked at linked
lists, and saw how to build a linked list, and how to compute the
length of a linked lists. Linked
lists are discussed in chapter 14 of Savitch.
- [7/25/00] We studied how to use linked lists, including
computing the length and list concatenation. We also introduced
the idea of an abstract data type. A list can be viewed in two
ways. The physical view concentrates on pointers and how lists
are represented in a computer. The conceptual (or abstract)
view concentrates on the intent of a list as a sequence of things.
We introduced the operations of head, tail and cons, and the
constant emptyList. The head of a list is the first member of the
list. The tail of a list L is the list obtained by removing the
first member of L. cons(H,T) is the list whose head is H and
whose tail is T.