CSE2050 Syllabus
Programming in a Second Language (C++)

Instructor: Matt Mahoney, mmahoney@cs.fit.edu or matmahoney@yahoo.com

Syllabus

Textbook: Accelerated C++, Koenig and Moo, Addison Wesley, 2000

Code examples from the book
Introduction to C++ (The short version)
C++ Reference (The long version)
Guidelines for Object Oriented Programming

Homework

Homework must be submitted by email by midnight of the due date. Late penalty: 20% per day. Send ONE plain text .cpp file as an attachment, or as inline text if your email does not support attachments. Lines should not exceed 80 characters in length. Do not submit executables. All programs should have as comments:

Assignment 1

Due Tues. Jan. 18, 2005. (5 pts). Compile and run the "hello world" program on page 1 using g++ under UNIX. Add comments as described above. If you are not familiar with UNIX, see http://www.emba.uvm.edu/CF/basic.html for a description of basic commands.

Assignment 2

Due Tues. Jan. 25, 2005 (10 pts). Write a C++ program like the one in chapters 1 and 2, except that it prints a right triangle around the greeting instead of a rectangle as shown below. There should be no limit on name length.

Please enter your first name: Matt

  *********************
    *                 *
      *  Hello, Matt! *
        *             *
          *           *
            *         *
              *       *
                *     *
                  *   *
                    * *
                      *

Be sure your documentation describes the program completely, including exactly how many stars are on each side as a function of the length of the name. You have some flexibility here, but your program must do exactly what your analysis says it does.

Assignment 3

Due Tues. Feb. 15 (25 pts). Write a program nword.cpp that takes as arguments a number n and a list of file names. Your program should print a list of words (sorted alphabetically) that occur at least once in exactly n of the files. For example, if you have the following files:

      file1                       file2                     file3
      This is a test.             This is                   THIS IS YET
                                  another test!             ANOTHER
                                                            TEST YET AGAIN!!!

  nword 1 file1 file2
  a
  another

  nword 2 file1 file2 file3
  another

  nword 3 file1 file2 file3
  is
  test
  this

  nword 1 file3 file2
  again
  yet

  nword 1 file3
  again
  another
  is
  test
  this
  yet

Note that if a word (like YET) occurs twice in one file, it is counted only once. A word is defined as a sequence of one or more letters (a-z) and does not include punctuation, digits, spaces, or other characters. Case is not signficant.

Assignment 4

Due Tues. Mar. 22 (30 pts). Write a program tcalc.cpp that evaluates expression involving both real numbers and time values of the form hh:mm or hh:mm:ss, ranging from 00:00:00 to 23:59:59. If n is a number and t is a time object, then the following operations are valid and produce a result with the type shown:

  n+n -> n    t+t -> t
  n-n -> n    t-t -> t
  n*n -> n    n*t -> t    t*n -> t
  n/n -> n    t/n -> t    t/t -> n
Arithmetic on numbers has its normal meaning. Arithmetic on time is computed modulo 24 hours and rounded to the nearest second. Your program should input an expression on a single line and then print the answer, repeating until a blank line is entered. An expression may be arbitrarily long and contain parenthesis. Precedence order should be the same as C++. For example:
  tcalc
  12:30+13:35:02
  2:05:02
  9:05 * 3
  3:15
  1:00/5.0
  0:12
  1:00/-1.0
  23:00
  3:00/2:00
  1.5
  0:01:00/14
  0:00:04
  1:00 * 3 + 2:00/4.0
  3:30
  (1:00+2:30)*2-0:10-0:01
  6:49

Your program should give an appropriate error message but continue running after bad input such as:
  1:00*2:00             Type mismatch
  3+4+*)                Syntax error
  3+a                   Invalid input
  2:30/(3*2-6)          Division by 0
  24:60:61              Time out of range
Your program should use object oriented techniques. Write a class called Time. Overload operators as appropriate.

Hint: write a recursive descent parser. Throw exceptions to handle errors. For an example, see the solution to Spring 2004 assignment 5.

Assignment 5

Due Tues. Apr. 19, 2005 (30 pts). Write a program to sort a file using a sorted queue. Your program should work as a pipe:

  sort method < input > output
should work exactly like the UNIX or MSDOS sort program, sorting line by line in ASCII order. Your program should take one argument, method, consisting of a lowercase letter, either m (map), q (priority queue), v (sorted vector), or h (heap). Whichever method is used, your program must run in O(n log n) time and produce exactly the same output.

Write an interface, SortedQueue<T> with four derived implementations corresponding to each of the four methods. Your interface should have the following public members:

  insert(x) - inserts an object x of type T
  size() - returns number of objects stored, initially 0
  remove() - removes and returns the smallest x if size() > 0
For example, to sort:
  SortedQueue<string>* sq;
  switch (argv[1][0]) { // method
    case 'm': sq = new MapQueue<string>; break;
    case 'q': sq = new PriorityQueue<string>; break;
    case 'v': sq = new VectorQueue<string>; break;
    case 'h': sq = new HeapQueue<string>; break;
    default: // handle error
  }
  string s;
  while (getline(cin, s))
    sq->insert(s);
  while (sq->size() > 0)
    cout << sq->remove() << "\n";
  delete sq;
Your four implementations should be as follows:

MapQueue

Objects are stored as keys in a map<T, int>, where the value is the number of copies of objects with the same key.

PriorityQueue

Objects are stored in a priority_queue<T>. You will need a templated comparison function to reverse the sort order.

VectorQueue

Objects are stored in a vector<T>. The vector should be sorted as needed, but not more often. In this program, it would be sorted only once. Do not use any auxiliary functions to tell it when to sort.

HeapQueue

Objects are stored in a heap, a balanced binary tree in which each vertex is smaller than its two children (the heap property), with leaves filled left to right.

The root is the next item to remove. After removal, replace the root with the last leaf node. If the new root is larger than either child then swap it with the smaller child, continuing down the tree until the heap property is restored.

To insert an item, add a leaf node, then while it is smaller than the parent, swap it, working upward until the heap property is restored.

The heap should be represented as a vector without pointers: element i has children 2i+1 and 2i+2, and parent (i-1)/2. Element 0 is the root.

                2
               /  \          +---+---+---+---+---+---+
              /    \         | 2 | 4 | 7 | 9 | 5 | 8 |
             4      7        +---+---+---+---+---+---+
            / \    /           0   1   2   3   4   5
           9   5  8

             A heap viewed as a tree and as an array

Have the program print (to cerr) the execution time using clock(). Test on a large file. Which method is fastest?

Past Exams and Homework

Spring 2005 Exam solutions

Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Fall 2004 Homework and Exam solutions

Fall 2004 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Spring 2004 Homework and Exam solutions

Spring 2004 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Fall 2003 Homework and Exam Solutions

Fall 2003 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Spring 2003 Homework and Exam Solutions

Spring 2003 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Fall 2002 Homework and Exam solutions:

Fall 2002 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Spring 2002 Homework and Exam solutions:

Spring 2002 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Fall 2001 Exam solutions:

Fall 2001 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.

Spring 2001 Exam solutions:

Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.