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

Florida Tech, Fall 2004 - Aug. 26 to Dec. 9 - Tues. and Thurs., 12:30-1:45 PM, room S112


Syllabus - short version

Course Description

Students will learn to program in C++. Topics include the standard library, object oriented programming (data abstraction, inheritance, polymorphism), implementing data structures, and the UNIX development environment and portability considerations. Prerequisites: CSE2010 (Algorithms and Data Structures) or equivalent, or experience in at least one other programming language (preferably Java).


Matt Mahoney, mmahoney@cs.fit.edu or if that doesn't work, then matmahoney@yahoo.com Office hours are immediately after class.

How is my teaching? Review this course anonymously at TeacherReviews.com.


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

Grading Policy

Based on 100 points. 90-100=A, 80-89=B, 70-79=C, 60-69=D, 0-59=F. Grade = (highest 3 of 4 exams)/6 + (sum of homework grades)/2.

Tests, 50% of grade

There will be 4 tests during the term including the final exam Each will count equally. Your grade will be based on the highest 3 tests after dropping the lowest score. There will be no make-up tests for any reason.

Fall 2004 Exam solutions

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.

Programming assignments, 50% of grade

Assignments will be graded equally on documentation and readability and on whether it actually works. Programs are due at midnight. Programs turned in late will be penalized 20% per day, including non-class days, weekends, and holidays.

Programs must be turned in by email. I prefer that you send me one source code (.cpp) file as an attachment, or in the body of the mail message if your mailer doesn't support attached files. Limit line length to 80 characters. I do not need test cases by email, since I can test it myself. Do not send me executables, zip files, Word files, project files, etc.

You are permitted to receive help from other students or outside sources, however you must cite your sources in your program comments and your work must still demonstrate that you are capable of writing the program yourself. Copying code or allowing your code to be copied by other students is not allowed. See the Florida Tech Computer Science Honor Code for details.


All programs should have as comments:


All programs must be tested with g++ under UNIX (Solaris, Linux, etc.). You may use other systems for development if you wish (Windows or Mac), and then port them. If you do, your C++ compiler should be produced since 1998 so that it supports the standard library. If you prefer to develop under Windoes and port to UNIX, then I recommend DJGPP, available at www.delorie.com. Other free compilers are available at www.cplusplus.com/info/compilers/

Mailing List

All students will be enrolled in a mailing list and will be responsible for announcements posted to this list. You should be enrolled automatically, but I sometimes miss a few people, so if you do not receive an email by the second class letting you know, then you should subscribe by sending a blank email to fit-cse2050-subscribe@yahoogroups.com. You are also encouraged to post questions about C++ or your assignments to this list, and to answer questions posted by other students. To post messages, mail them to fit-cse2050@yahoogroups.com. Archived messages may be found at groups.yahoo.com/group/fit-cse2050/

Assignment 1

Due Thurs, Sept. 16, 2004. (5 pts). Obtain an FIT system-wide TRACKS account (if you don't already have one) from the Help Desk in the Quadrangle, room Q7. This will allow you to use all the student machines (UNIX, Windows, and Windows NT) in the Olin Engineering and Life Sciences buildings and in rooms A110 (Aeronautics bldg.) and S210/S220 (Crawford Science bldg). See http://www.it.fit.edu/tracks/. You should be familiar with UNIX to use these systems. If not, see http://www.emba.uvm.edu/CF/basic.html

Compile and run the "hello world" program on page 1 using g++. Add comments as described above.

Assignment 2

Due Tues. Sept 21, 2004 (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.

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 Thurs. Oct. 7 (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

  nword 2 file1 file2 file3

  nword 3 file1 file2 file3

  nword 1 file3 file2

Your documentation should describe what the program does with enough detail that a user can predict what it will output for any given input. Do not assume that the user is familiar with the assignment. You should define precisely what a "word" is (case sensitive?, punctuation?, is "it's" one word or two?, etc). This includes describing how errors are handled (file not found, invalid or missing n, etc).

Assignment 4

Due Thurs. Nov. 4 (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:
  9:05 * 3
  1:00 * 3 + 2:00/4.0

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 Dec. 9, 2004 (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))
  while (sq->size() > 0)
    cout << sq->remove() << "\n";
  delete sq;
Your four implementations should be as follows:


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


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


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.


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 | 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?