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

Florida Tech, Spring 2003 - Jan. 9 to Apr. 24 - Tues. and Thurs., 12:30-1:45 PM, room S112

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

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

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 (on Apr. 30, 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.

Spring 2003 Exam Solutions

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

Documentation

All programs should have as comments:

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. Jan. 16, 2003. (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 Thurs. Jan 23, 2003 (10 pts). Write a C++ program like the one in chapters 1 and 2, except that it prints a pentagon 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 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. Feb. 6 (15 pts). Write a C++ program that reads text from standard input and prints all the integers found in the input in sorted numerical order. A integer is any sequence of one or more decimal digits with an optional leading - sign. For instance, if the file test.txt contains

  I re-installed Windows-3.1 over Win98-R2 on
  2/05/1999 at 12:07PM on my $299.00 486-100.
Then your program would run like this:
  a.out < test.txt
  -100
  -3
  0
  1
  2
  2
  5
  7
  12
  98
  299
  486
  1999
Note that "Windows-3.1" contains two integers, -3 and 1, Win98-R2 contains 98 and 2, "12:07PM" contains 12 and 7, "re-installed" does not contain a 0, etc.

Solution

Assignment 4

Due Thurs. Feb. 20 (15 pts). Write a spell checking program. Your program will take two file names as arguments. The first will be a text file to be checked. The second will be a dictionary file, for instance, /usr/dict/words. For each word that occurs in the first file but not the second, your program should print one line of output containing the line number of the misspelled word, a colon, and the word. Line numbers start with 1. A word consists of any sequence of upper or lower case letters (A-Z, a-z). For purposes of comparison, differences in case are not significant, but the word should be printed in its original case. For example, if test.txt is your test file as follows:

  This is a test of
  my computer's program.
Then your program output is:
  a.out test.txt /usr/dict/words
  2: computer
  2: program
The words "computer" and "program" do not appear in /usr/dict/words. Note that the "'s" is not part of the word "computer" and the "." is not part of "program". Also, "this" (but not "This") appears in /usr/dict/words, so your program should not print "This".

If empty.txt is an empty text file, then, your output would be as follows:

  a.out test.txt empty.txt
  1: This
  1: is
  1: a
  1: test
  1: of
  2: my
  2: computer
  2: s
  2: program

  a.out empty.txt test.txt      (no output)

  a.out test.txt test.txt       (no output)

Your program should print an appropriate error message if there are not exactly two file name arguments or if either file cannot be read. It should run reasonably fast on files containing tens of thousands of words.

Solution

Assignment 5

Due Mar. 13, 2003 (20 points). Modify your spell check program from assignment 4 to use a hash table instead of a map for its dictionary. Your hash table should be a templated class and have an operator [] like a map<string, T>, where the value type T is a template parameter. The key is always a string. If T is numeric, it should default to 0. If bool, it should default to false. For example,
  Hashtable<bool> dict;
  dict["hello"] = true;
  if (dict["bye"])  // false
Add preprocessor directives so that compiling with -DHASH causes your program to use a hash table instead of a map. Here is one way to do that.
#ifdef HASH
  Hashtable<bool> dict;
#else
  map<string, bool> dict;
#endif
Your program should run at least as fast when compiled with -DHASH as without when tested on large files such as /usr/dict/words. I will test this. There should be no limit on the number of items that can be stored, or on the length of a string (given enough memory).

Be sure to use good object-oriented techniques (private data, etc). Be sure to document both the public and private sections of your class. How do you use the class? How is it implemented?

Solution

Assignment 6

This assignment will be in 3 parts for a total of 35 points. You will implement a map as a binary tree, and write a test program. Your program will read a text file (named in the first command line argument) and print a frequency histogram for the words in that file. The output will be in the form:
  m words occur n times: word1 word2 ... wordm
in decreasing order of n. At the end, print the total number of word instances and the number of different words (total of m). For example,
  more < test
  This is a test.  This is another test.
  This and this and this too.

  ./a.out test
  1 word occurs 5 times: this
  3 words occur 2 times: is test and
  3 words occur 1 time: a another too
  test has 14 instances of 7 words.
If m > 5, then print any 5 words followed by "...", e.g.
  8 words occur 2 times: cat dog horse worm bird ...
If the program is given a word as the second argument, then print just the number of times that word occurs, followed by the overall statistics for the file as before.
  ./a.out test THIS
  this occurs 4 times.
  test has 14 instances of 7 words.

  ./a.out test foo
  foo occurs 0 times.
  test has 14 instances of 7 words.
Words are any sequence of one or more letters (a-z) and do not include any punctuation, digits, or other characters. Upper and lower case are equivalent. Output is lower case. For example, "P2P" is 2 instances of the word "p".

You will implement your program using binary trees. For part 1, you will use maps rather than trees to get the test code working. For part 2, you will substitute Tree<K,V> for map<K,V> and implement just the [] operator and size() method. For part 3, you will also implement iterator (as a forward iterator), begin(), end() and find(). Your code should use all of these features to demonstrate that they work.

Part 1, due Apr. 1 (10 points)

Implement your program using maps. For example, you might use the following:
  map<string, int> count;  // count["this"] = 4
  map<int, vector<string> > hist;  // hist[2] = {"is", "test", "and"}
The number of different words is count.size(). When looking up s = argv[2], use count.find(s) rather than count[s] so as not to increment the size if the word is not found.

You may wish to use another data structure for hist. For example you do not have to save all m words, just the first 5, so you might use:

  struct HistInfo {
    vector<string> words;  // maximum of 5
    int m;  // actual number of words
    HistInfo(): m(0) {}
  };
  map<int, HistInfo> hist;

It is recommended that your program use all of the features described in part 3. Otherwise you will have to change your test code later. Save a copy of this program, because you are going to remove some of the test code for part 2, then put it back for part 3.

Solution

Part 2, due Apr. 10 (10 points)

Instead of using a map as in part 1, use a sorted binary tree. (It does not have to be balanced). It should implement operator[] and size() just like a map, and your code should show me that they work. For example:
  Tree<string, int> count;
  string s;
  while (getword(s))  // read a word, convert to lower case
    ++count[s];
  ...
  cout <<  count.size() << "words.\n";

Your program only needs to work for the case where it is given two arguments. For example:

  ./a.out test foo
  foo occurs 0 times.
  test has 14 instances of 7 words.
Since you have not yet implemented find(), you will need to use count[s] to look up a word and adjust the output of your program to account for the size increase when a word is not found.

Be sure to include a destructor for Tree. You may use a private copy constructor and assignment operator to disallow them and leave them unimplemented, or you may implement them as public methods.

Solution

Part 3, due Apr. 24 (15 points)

Write the program as described in the introduction, using Trees rather than maps. Add a public type Tree::iterator representing a forward iterator. Implement the complete program as in part 1, and write it in such a way as to test all of the following operations. They should behave just like in a map.
  tree[key]    // from part 2
  tree.size()  // from part 2
  tree.begin()
  tree.end()
  tree.find(key)
  Tree<K,V>::iterator p=tree.begin(), q;  // initialized or not
  q=p;  // assignment
  ++p   // pre/post increment
  p++
  *p    // contents
  p->first  // read-only
  p->second // writeable
  p==q  // comparison
  p!=q
The histogram is keyed on n, which is supposed to be printed in reverse order. The obvious implementation is to iterate through hist backwards. This could be done one of the following ways: However there is a much simpler solution, which you could implement in either part 1 or part 3. If you think of it first, post your solution to the class mailing list.

Solution by Nathan Moreau, who won 10 extra credit points for having the fastest program when tested on a large (6 MB) text file.