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

Florida Tech, Fall 2002 - Aug. 27 to Dec. 5 - 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 (on Dec. 11, 3:30 PM). 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 2002 Exam solutions:

Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Finel Exam solution.

Spring 2002 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 supoort 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 Tues. Sept. 3, 2002. (5 pts). Obtain an FIT system-wide 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 cs.fit.edu/wds/labs/openlabs/. Also, you may want to obtain an account on zach.cs.fit.edu (another UNIX machine with g++). See http://www.fit.edu/acs/userservices/apply_account.htm 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. 10, 2002 (10 pts). Write a C++ program like the one in chapters 1 and 2, except that it prints a diamond around the greeting instead of a rectangle. For instance:

Please enter your first name: Matt

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

Be sure your documentation describes the program completely, including how you handle the case where the greeting can't be centered exactly.


Assignment 3

Due Tues. Sept. 24 (15 pts). Write a C++ program that reads a text file from standard input and prints in two columns an alphabetical list of the words in the file preceded by the number of times the word occurs. For instance, if the file test.txt contains

  This is a test--and
  this too.
And if you run your program, wordcount.cpp, as follows:
  wordcount < test.txt
Then the output should be
  1 a
  1 and
  1 is
  1 test
  2 this
  1 too
A word is a sequence of one or more letters, not including punctuation, digits, spaces, or any other characters. Words should be converted to lower case before being counted or printed.

Suggestions: You may want to write a function returning the next word of input as a string. Don't use cin >> to read words because it would read "test--and" or "too." as one word. Store all the words in a map<string, int> or a sorted vector<string> before printing the list.

Solution using a vector or map.

Assignment 4

Due Tues. Oct. 8 (15 pts). Write a C++ program that reads lines of text from a file and prints them in reverse order to another file. The input and output files should be specified on the command line. For instance, if input.txt contains

  is a
Then the command
  reverse input.txt output.txt
will create a new file called output.txt with the contents:
  is a
Print an appropriate message to standard error (cerr) if the input file cannot be read or output file cannot be created.

Your program should define a class Stack with the following public interface:

  Stack st;      // Initially empty stack of strings
  st.push(s);    // Push string s onto Stack st
  s = st.pop();  // Pop and return string s.  If empty, throw an exception of type Stack::Error
  st.empty();    // True if empty
  Stack::Error;  // A typedef or a class with no members to be used as an exception
For instance, the following would print the contents of the stack in the reverse order in which the items were pushed.
  Stack st;
  // Push some items using st.push(...);
  while (!st.empty())
    cout << st.pop() << endl;
However, instead of testing for empty(), arrange for your program to demonstate throwing and catching an exception without affecting the behavior as specified above. Describe in your comments how you will do this.

Solution using a vector<string> implementation of Stack.

See also this solution using a templated linked list (although it does not throw exceptions).

A linked list stack implementation with iterators and implementing the "rule of 3"

Homework 5

Due Thurs. Oct. 24 (15 pts). Write a templated class Seq<T> representing a fixed sequence of numbers. Its constructor should take 3 parameters: a size (int, default 0), a starting value (T, default 0), and a step (T, default 1). It should have an index operator returning the i'th element of the sequence, or throw out_of_range if i < 0 or i >= size. The elements are fixed; they cannot be assigned to, although assignment to a Seq of the same type is allowed.

A Seq<>should also define types iterator and const_iterator, both of which are input iterators, and begin() and end() with their usual meanings. You could also have *p throw out_of_range if p does not point to a valid element (e.g. .end()).

  Seq<T>(size, start, step) x;    // Has elements start ... start+step*(size-1)
  Seq<T>(size, start) x;          // step 1
  Seq<T>(size) x;                 // start is 0
  Seq<T> x;                       // size is 0
  x[i];                           // Has const value start + (step*i), 0 <= i < x.size()
  x.size();                       // Returns the size as an int
  x.begin();                      // Input iterator pointing to first element
  x.end();                        // Points 1 pasts last element
  Seq<T>::iterator p;             // Return type of x.begin(), x.end()
  Seq<T>::const_iterator q;       // Same as iterator
  ++p                             // Point to next element, return new p by reference
  p++                             // Point to next element, return old p by value
  *p                              // One element (const)
  p=q, p==q, p!=q                 // Assignment, comparison
For example,
  Seq<int> a(5, 10, 2);           // {10, 12, 14, 16, 18}
  cout << a[2];                   // 14
  Seq<double> b(4, 1.0, 0.1);     // {1.0, 1.1, 1.2, 1.3}
  cout << b.size();               // 4
  cout << b[1];                   // 1.1
  Seq<char> s(26, 'a');           // "abc...z"
  cout << s[25];                  // 'z'
  s[10]='x';                      // Error, elements are const
  Seq<char> t=s;                  // OK
  *s.begin()='x';                 // Error, elements are const

  for (Seq<char>::const_iterator p=s.begin(); p!=s.end(); ++p)
    cout << *p;  // Print the alphabet

  vector<char> v;
  copy(s.begin(), s.end(), back_inserter(v));  // Copy to v

  try {
    cout << s[26];          // throw out_of_range
    cout << *s.end();       // Optional: throw out_of_range
  catch (out_of_range x) {
    cerr << x.what();

Be sure to document your class, both the interface (including whether your iterators throw exceptions or not) and the implementation (which is up to you). Turn in just a header file, seq.h. You will need to write test code, but do not turn that in. I will test it by including your header in some test programs similar to (but more extensive than) the examples above. Use good data abstraction techniques (private data and methods) so as not to expose any implementation details.


Solution computing elements as needed from the original constructor elements. This solution is more memory efficient, but requires writing your own iterators.

Solution using precomputed elements stored in a vector. This uses more memory, but is simpler because you can use vector<T>::const_iterator as your iterator types.

Homework 6

Your assignment is to write a calculator that works in Roman numerals. It has two parts.

Part 1 - Analysis and design, due Tues. Nov. 5 (10 points)

Describe precisely what your program will do (analysis) and how it will work (design). Your analysis should be detailed enough so that if I give it any input (including invalid data), I know exactly what the output will be. Ideally you should include some examples of what the user would do and see.

Your design should describe any classes or functions you will write, and their interface and implementation. Ideally each step in your design should translate to no more than 10 lines of code.

Your grade will depend on how complete and precise your analysis and design are, not on how complicated or clever your program is. I have been deliberatly vague about what I want your program to do. It is up to you to supply the details. Be sure to divide your paper into two sections labeled "Analysis" and "Design", and not mix them up. I recommend you keep both of them as simple as possible, so as not to give yourself too much work later on.

Post your homework to the class list at fit-cse2050@yahoogroups.com Feel free to post questions or comments about other student's analyses. As usual, I encourage turning in your homework early so that problems can be worked out before the due date.

Part 2 - Code, due Tues. Nov. 12 (10 points)

Your program will be graded according to how well it agrees with your analysis and design. You may change these as needed. Turn in to me (not the class list) your revised analysis and design (even if there are no changes) as comments in your program.


Homework 7

Due Tues. Dec. 3, 2002 (20 points). A problem with numeric types in C++ such as int and double is that they have limited range and precision. An int can typically only represent numbers in a range of about + or - 2 billion, or possibly as small as -32738 to 32767. A double can only represent numbers with about 14 significant digits, and only up to about 10308.

Your assignment is to write two number classes that remove these restrictions. Class Integer will represent integers with unlimited range. Class Real will represent decimal numbers with unlimited range and in addition, any specified precision (number of places after the decimal point), defaulting to 20 decimal places, e.g.

  Integer a=1e12; a=a*a;  // 1000000000000000000000000 exactly
  Real b=1; b/=3;         // 0.33333333333333333333
  Real c(12.5, 4);        // 12.5000
  Real d;                 // 0.00000000000000000000

Both types should default to 0. Both types should allow arithmetic ( + - * / ), comparison ( == != < <= > >= ), assignment ( = += -= *= /= ), input ( >> ), and output ( << ). For arithmetic and comparison expressions that mix int, double, Integer, and Real, the following rules should apply.

In other words, the order of promotion from lowest to highest is int to double to Integer to low precision Real to high precision Real. Before any operation, we promote the lower type to that of the higher type.

Assignment of one Real to another changes the precision (as well as the value) of the left operand to that of the right operand. When an assignment is combined with an arithmetic operator, the result has the precision of whichever operand had the higher precision, just as with ordinary arithmetic. Assignment of Real to Integer is allowed only with an explicit conversion.

  c += d;          // 12.50000000000000000000
  a = Integer(c);  // 12, drop the fractional part

You may use any standard library types to implement your classes if you wish. You may also wish to use inheritance to simplify the problem. What would be the base class?

Your program should not have a main(). I will link test code to your program to make sure everything works. Turn in a .h file and a .cpp file with just the two class definitions and related code. Use your first initial and last name for the two file names, all lower case without spaces, e.g. mmahoney.cpp and mmahoney.h. I will have a test program something like this (but longer):

  // test.cpp
  #include <iostream>
  #include "mmahoney.h"  // substitute your .h file here
  using namespace std;
  int main() {
    cout << Integer(8) / Real(3, 5) << endl;   // 2.66666
    return 0;
Then I will compile and link like this:
  g++ test.cpp mmahoney.cpp

Extra Credit

Try to make your operators as fast as possible. I will run a benchmark program that times all the different operations (arithmetic, comparison, conversion, and assignment) in about equal proportions using about 1000 significant digits for both types. I will be using both a PC and a UNIX machine, compiling with g++ -O (optimization on) for the timing tests. The fastest 3 programs (shortest total run time) will receive 15, 10, and 5 extra credit points. I will announce the winners on Dec. 4.

You may wish to show me early versions so I can give you suggestions to make your code faster. In fact, this will be much easier to do if you show me (or post) an analysis and design before you write any code.

Deadline Extended

The due date has been extended to midnight Thurs. Dec. 5. However you must turn in the work you have done so far by Tues. Dec. 3. to be eligible for this extension. This is so that I can comment on it to save you work later on. Be sure that your progress report includes documentation so that I can understand your approach.

If your project is not finished, then include a main() in your .cpp file with test code, and comments explaining what works and what doesn't so I can give you partial credit without guessing. If everything works with bench.cpp (above link) then do not include main(). I will link to it instead.

Solution: mmahoney.h and mmahoney.cpp. To compile and run with the benchmark program above:

  g++ -O bench.cpp mmahoney.cpp
  time a.out 10