Florida Tech, Fall 2001 - Aug. 28 to Dec. 13, 12:30-1:45 PM, room S-112
http://cs.fit.edu/~mmahoney/cse2050/
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, experience in at least one other programming language.
How is my teaching? Review this course anonymously at TeacherReviews.com.
C++ Reference
Guidelines for Object Oriented Programming
Based on 100 points. 90-100=A, 80-89=B, 70-79=C, 60-69=D, 0-59=F
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 2001 exam solutions:
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.
Assignments will be graded 60% on documentation and readability and 40% on whether it actually works. Programs turned in late will be penalized 20% per day, including non-class days, weekends, and holidays. Programs turned in by email are due at midnight.
I prefer that you send me one text file by email, 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.
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. The following is a partial list:
All students are encouraged to join the mailing list for this class for the semester. The group is for questions about C++ and homework assignments, and for class announcements. To post messages, mail them to fit-cse2050@egroups.com
Compile and run the "hello world" program on page 1 using g++. Add comments as described above.
Due Thurs. Sept 13, 2001 (10 pts). Write a C++ program like the one in chapters 1 and 2, except that it prints a hexagon (with all sides equal) around the greeting instead of a rectangle. For instance:
Please enter your first name: Matt
******
* *
* *
* *
* *
* Hello, Matt! *
* *
* *
* *
* *
******
Be sure your documentation (60% of your grade) describes the program completely, including how you handle the case where the greeting can't be centered exactly.
Due Thurs. Sept. 20 (10 pts). Write class Complex as described in class (but without a destructor). Overload operators +, -, *, and << (output). Insert into the code below and test.
// Your documentation here...
#include <iostream>
using namespace std;
// Your code here...
int main() {
Complex a(1, 2), b(3.5), c;
const Complex i(0, 1);
cout << a + b * i << endl; // 1 + 5.5i
cout << Complex(10, 1) + 4 - i * 3 + c << endl; // 14 - 2i
a = a * a; // Why not a *= a ?
cout << a << endl; // -3 + 4i
return 0;
}
(10 pts). Problem 5-1 in the book. Analysis is due Thurs. Sept 27. Completed program (with revised analysis) is due Thurs. Oct. 4.
Due Thurs. Oct. 18. (10 pts). The sort() function can only sort sequences that have random iterators, such as vector, string, and arrays. Random iterators are required to implement the fastest sorting algoritms (O(n log n)), such as quicksort, merge sort, and heap sort. However, slower (O(n2)) algorithms such as bubble sort can be implemented using bidirectional iterators.
Your assignment will be to write a generic (template) sort function called bi_sort() taking two bidirectional iterators. For instance:
list<string> a; // Put some elements in a... bi_sort(a.begin(), a.end()); // Sort list of words
Do not use list.sort(), as your funtion must be generic. For instance:
int a[10] = {5,3,6,7,2,4,0,9,5,6};
bi_sort(a, a+10); // {0,2,3,4,5,5,6,6,7,9}
Write a program to demonstrate bi_sort() by reading words (separated by white space) from standard input into a list<string>, sorting the characters in each word using bi_sort(), then sorting the words using bi_sort(), and printing them out. For instance, if your program is called bisort.cpp, then
echo this is a test | bisort a estt hist is
I recommend that you start by writing bi_sort() to take two iterators of type list<string>::iterator, then generalize it to type T using a template.
Due Thurs. Nov. 15. This assignment will have 2 parts and be worth a total of 25 points. I will not assign a due date for part 1, but I expect you to turn it in early enough to complete both parts by the due date. I won't assign a grade until the due date.
Part 1 is to write a program to find the word that occurs most frequently in a text file, then print the word and the number of times it occurs. If there is a tie, then pick any word and print it, but also print how many words are tied for the highest count. A word is defined as any sequence of 1 or more non whitespace characters (as read using >> ).
The program should take a filename argument. Test your program on the UNIX files /usr/dict/words and /usr/man/man1/csh.1 (or their equivalent if they are stored in a different place like /usr/share/man/sman1). The first file contains an alphabetical list of words. The second is the man page for csh in nroff format. For instance:
mostword /usr/dict/words There are 25143 words and 25143 different words. The most frequent word is "10th" occurring 1 times. 25143 word(s) occur 1 times. mostword /usr/share/man/sman1/csh.1 There are 10779 words and 3232 different words. The most frequent word is "the" occurring 721 times. 1 word(s) occur 721 times.
Use a map<string, int> to store a count for each word, from which you can compute the results you need. To test the run time performance of your map, add an optional second argument n to your program to make n passes through the file (default 1). Each pass should open the file, read the words, add them to the previous counts, and close the file. Thus, all counts (and the run time) will be increased by a factor of n. For example:
time mostword /usr/share/man/sman1/csh.1 100 There are 1077900 words and 3232 different words. The most frequent word is "the" occurring 72100 times. 1 word(s) occur 72100 times. 24.94u 0.20s 0:25.99 96.7%
Time your program using the UNIX time command, as in the example above. Adjust n until it takes several seconds to run in order to determine how long it takes to make one pass through the file (251.4 ms in this example). Report the times (user, system, wall) and the value of n you used for each of the two files above.
// Like map<string, T>
template <class T> class MapString {
public:
typedef MapStringIterator iterator;
iterator begin() const;
iterator end() const;
iterator find(const string&) const;
T& operator[](const string&);
int size() const;
};
Your class MapStringIterator should point to a pair<const string, T>. It should be at least a forward iterator, supporting ++, *, ==, and !=. Assuming you did not use any const maps in your program, you should not have to change any code except to change declarations for map<string, int> to MapString<int>.
Extra credit (5 pts). Implement const_iterator, and const and non-const versions of begin(), end(), and find(). Test your code by passing your MapString by const reference to a function (for instance, to print the output).
pi 20 3.14159265358979323846
Note that type double only gives you 14 decimal places of precision, so you will need to create your own numeric type. Implement your program by defining a class Number to represent fixed precision numbers to the required number of decimal places. Overload whatever arithmetic operators you need. You can find algorithms for calculating p by searching the Internet. One good source of fast algorithms is "The Quest for Pi" by Bailey, Borwein, and Borwein. Your program should be fast enough to print a few hundred decimal places in under a minute.
Progress report. By Nov. 27 you should have
Extra credit part 1 (10 pts). Use two different algorithms and have your program compare the results and verify that they are identical (or print the difference, if any). This is the method required if you are claiming a world record (currently about 200 billion digits, computed in 4 days on a 1 teraflop supercomputer).
Extra credit part 2 (15, 10, and 5 pts) for the first, second, and third fastest programs to calculate and print 1000 decimal places (timed on my computer). If you are also doing part 1, you can speed it up by printing the output of the first algorithm before computing by the second method and comparing.
Additional assignments and their solutions will be posted here at http://cs.fit.edu/~mmahoney/cse2050/