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

http://cs.fit.edu/~mmahoney/cse2050/

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

Instructor

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.

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

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.

Documentation

All programs should have as comments:

Name
Email address
Compiler and version number (for example, g++ 2.7.2) List all that apply. (Use g++ -v to get the version for g++).
Your operating system (Windows 98, Solaris 2.7, etc.) List all that apply. (In UNIX, use uname -a)
An analysis or users manual, describing what your program does from the point of view of a novice user who has not read the assignment. It should tell the user what your program is for, what it does, i.e. why he/she should bother to download it from your website. Be specific: I should be able to supply input to your program, without errors, and predict what the output should look like. As a general rule, you should have one line of analysis for every 3-5 lines of code. The analysis must appear before the first line of code.
Comments describing the major sections of code: classes, functions, loops, and important variables. Use descriptive names instead of comments if possible. Do not comment every line.
Use white space and indentation to show program structure, as in the examples in the book.
Give references where appropriate, including help received from other students. Copying code or allowing your code to be copied is not allowed.

Compilers

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
  a
  another

  nword 2 file1 file2 file3
  another

  nword 3 file1 file2 file3
  is
  test
  this

  nword 1 file3 file2
  again
  yet

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:

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

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