Florida Tech, Fall 2002 - Aug. 27 to Dec. 5 - Tues. and Thurs., 12:30-1:45 PM, room S112
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, or experience in at least one other programming language (preferably Java).
How is my teaching? Review this course anonymously at TeacherReviews.com.
Code examples from the book
Introduction to C++ (The short version)
C++ Reference (The long version)
Guidelines for Object Oriented Programming
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.
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.
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 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/
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/
Compile and run the "hello world" program on page 1 using g++. Add comments as described above.
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.
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.txtThen the output should be
1 a 1 and 1 is 1 test 2 this 1 tooA 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.
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
This is a test.Then the command
reverse input.txt output.txtwill create a new file called output.txt with the contents:
test. is a ThisPrint 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 exceptionFor 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"
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, comparisonFor 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.
Hints:
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.
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.
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.
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 a.out
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.
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