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/
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 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.
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 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.
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 1999Note 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.
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: programThe 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.
Hashtable<bool> dict; dict["hello"] = true; if (dict["bye"]) // falseAdd 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; #endifYour 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?
m words occur n times: word1 word2 ... wordmin 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.
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.
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.
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!=qThe 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:
Solution by Nathan Moreau, who won 10 extra credit points for having the fastest program when tested on a large (6 MB) text file.