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.

  • Assignment 1
  • Assignment 2
  • Assignment 3
  • Assignment 4
  • Assignment 5
  • Assignment 6
  • Assignment 7
  • Assignment 8
  • Assignment 9
  • Assignment 10
  • Assignment 11
  • Assignment 12
  • 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.
  • Exercise set 1
  • Solutions to exercise set 1
  • Practice questions for exam 1
  • Solutions to practice questions for exam 1
  • Practice questions for exam 2
  • Solutions to practice questions for exam 2
  • Practice questions for exam 3
  • Solutions to practice questions for exam 3
  • 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.
  • A simple main program
  • A program using a function
  • A program using an if statement
  • A program using a loop
  • Lecture summaries

    1. [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.

    2. [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

      1. Action-oriented design. Here, you think primarily about the actions that you want to do over and over.

      2. 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.

    3. [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.

    4. [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.

    5. [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. [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.

    7. [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.

    8. [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.

    9. [7/4/00] Holiday.

    10. [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.

    11. [Thursday, 7/6/00] Exam 1.

    12. [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.

    13. [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.

    14. [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.

    15. [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.

    16. [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.)

    17. [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.

    18. [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

      1. Replace a character by another character.
      2. Insert a character.
      3. 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.

    19. [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.

    20. [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.

    21. [7/20/00] Exam 2.

    22. [7/21/00] We went over the exam, and worked more on the basics of pointers, including allocating arrays and creating arrays of strings.

    23. [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.

    24. [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.