Matt Mahoney
Fall 2007
http://www.cs.fit.edu/~mmahoney/cse1502/
Aug 21-Dec 5, 2007. No classes Sept. 3, Oct 8-9, Nov. 12, Nov. 21-23. Final exam Dec. 13.
Lectures: Tues. and Thurs, 2:00-3:15 PM, room 118EC (Olin auditorium) by Matt Mahoney.
Labs: Wed., and Fri., 9:00-9:50 AM, 10:00-10:50 AM,or 11:00-11:50 AM, depending on your section. Labs will be taught by the lab instructors. Room: Olin 228/229EC (combined rooms). You may switch sections if space is available.
C++, How to Program, 5th Ed. or 6th Ed., Deitel. Read chapters 1-8, skipping the optional sections at the end of each chapter. (Chapters 1-8 are the same in both editions). Also read the tutorial and Introduction to C++.
All students are expected to join the CSE 1502 mailing list. You are responsible for material posted to this list by instructors. You are also encouraged to post questions or answers about your homework or about C++ in general here, because other students might have the same questions.
To post a message, send email to cse1502@lists.fit.edu. Remember that when you reply to a post, it goes to the whole class unless you manually change the "to" address. Do not send your homework to the list.
Fall 2006 exams
Exam 3
Final exam
Spring 2007 exams
Exam 1
Exam 2
Exam 3
Final
Your lab instructor(s) will be responsible for assigning and grading your labs and establishing grading policy. The lab computers have g++ and Visual Studio installed. You will need a TRACKS password to use the computers.
Homework assignments will be longer programming assignments graded manually for correct design, function, documentation, and neatness. Partial credit is given based on my subjective opinion of how well you understand and describe the problem in comments (the specification), your approach (design), and testing (whether it works or gives appropriate error messages for unusual or unexpected inputs). Grading depends on human readability as well as machine readability. Code should be indented using the style in the book. Major sections should be commented. Variable names should be self documenting or their purpose should be commented as appropriate. Your homework should include your name and email address in the comments.
Homework must be submitted by email by midnight of the due date. Late assignments are penalized 20% per day. I encourage you to submit homework early for me to comment on, and submit revised versions later without penalty. I will grade only the best version.
You must cite all sources of outside help in your comments, including help received from other students or the Internet. Copying code or allowing your code to be copied is not allowed. Group assignments are not allowed. You are expected to know the CS department policy on academic honesty. Penalties for cheating can range from a zero on the assignment to expulsion from the university. I report incidents of cheating to the department head.
Final grade = (average of top 3 exams) * 0.4 + (lab grades)
* 0.3 + (average of homework grades) * 0.3.
90-100=A, 80-89=B, 70-79=C, 60-69=D, 0-59=F.
Fall 2006 syllabus and
Spring 2007 syllabus with homework and exam solutions.
You will need a C++ compiler for your home computer. You may use any standard ANSI C++ (released since 1999) compiler under any operating system (Windows, UNIX, Linux, Mac). I recommend (but don't require) MinGW g++ for Windows or GNU g++ for other operating systems. All of the following are free under Windows:
MinGW g++. This runs from a command window only. Download and run the installer (MinGW_Toolbox_Setup.exe, 23 MB). Add C:\mingw\bin to your PATH.
Visual Studio 2005 Pro or Standard. You will need a TRACKS account and be registered for this class to download it. This has a GUI and lots of features. The Pro version download is 2.8 GB (DVD image). Not recommended for older machines or slower connections. To install, download the 4 .rar files, unrar e *.rar, then burn a DVD from the .iso file or use the provided program to mount the .iso to disk and run vs\autorun.exe as administrator.
Borland C++ 5.5. This runs from a command window only. Works on old machines. Click on "compiler", register, and download the installer (8.7 MB). After installing, add C:\Borland\BCC55\bin to your PATH and create the file C:\Borland\BCC55\bcc32.cfg exactly as shown below:
-I"c:\Borland\Bcc55\include" -L"c:\Borland\Bcc55\lib"
Digital Mars C++ Compiler 8.49. This runs from a command window only. Works on old machines. Unzip stlport.zip (2 MB) and dm849c.zip (3 MB) in C:\ to install in C:\dm and add C:\dm\bin to your PATH.
Be sure to test your compiler by writing a simple program, compiling, and running it, e.g.
// Paste this file into notepad and save as hello.cpp
// To compile from a command window:
// MinGW: g++ -Wall hello.cpp -o hello.exe
// Borland: bcc32 hello.cpp
// Mars: dmc hello.cpp -IC:\dm\stlport\stlport
// To run: hello
//
// In Visual Studio: create new project, select Win32 console application,
// uncheck "precompiled headers", delete the supplied code, replace with this code
// and click Build project, Debug/Start debugging.
//
#include <iostream>
using namespace std;
int main()
{
cout << "Hello world\n";
return 0;
}
Due Tues. Sept. 11, 2007 at midnight (20 out of 100 homework points). Write a calculator program. The program should prompt the user to enter an expression of the form number operator number such as 5.2 x 3, then print the answer (15.6) and ask if the user wants to enter another problem. If the user answers y (for yes), then prompt for another problem. If the user answers n (for no), then exit. If the user enters any other letter, then repeat the question. Operators may be + - x or /. Numbers may have decimal points and/or a leading - sign. You may assume the user enters a space between the numbers and operator. For example (bold is user input):
Enter a problem: 3 + 10.5 13.5 Another problem (y/n)? y Enter a problem: -2 / 3 -0.66666 Another problem (y/n)? z Another problem (y/n)? a Another problem (y/n)? y Enter a problem: -2 - 3.1 -5.1 Another problem (y/n)? n
Submit one plain text source code (.cpp) file as an attached file by email to Matt Mahoney at mmahoney@cs.fit.edu or matmahoney@yahoo.com Do not send executables, project files, etc.
I will test your program with g++. If you use Visual Studio, be sure when you create a new project to select "Win32 console program" and uncheck the box "use precompiled headers". VS will create a new project with some initial code that you should delete. You should not have any code that looks like this:
#include "stdafx.h"; // no, this is not a standard header file int _tmain(int argc, TCHAR* argv) // no, int main() with no parameters
Be sure that your program includes a specification - about a paragraph of comments at the beginning that describe what the program does, even if it is different from the description above. The specification does not say how the program works. It describes the input and output from the user's point of view, and does not mention anything about the code. The specification is 20% of your grade.
Also be sure to put your name in the comments.
Due Oct. 4, midnight (20 points). Write a calculator like homework 1 that can add and subtract nonnegative integers with an arbitrary number of digits. The answer must be exact, with no overflow or loss of precision, no matter how big the numbers. Print the result (which may be negative) without leading zeros.
Your program does not have to multiply or divide. It does not have to accept negative numbers or numbers with decimal points. However, the input expression might or might not have any number of spaces between the numbers and operator. Your program should work in either case. For example:
Enter a problem: 1000000000000 - 3 9999999999997 Another problem (y/n)? y Enter a problem: 99-103 -4 Another problem (y/n)? y Enter a problem: 1 + 999999999999999999999999999999 1000000000000000000000000000000 Another problem (y/n)? y Enter a problem: 25- 25 0 Another problem (y/n)? n
Hint: you cannot use an int or double because they have limited range and precision. Use a string or vector of digits instead. You will need to add or subtract digits one at a time.
Due Thurs. Oct. 25, midnight. This assignment is only for students who scored less than 20 points on homework 2 and want to redo it for a new grade. It is worth 20 points. If you choose to do this assignment and get a higher grade than before, then it becomes your new grade. If it is lower, then you keep your old grade, so there is no penalty for an attempt.
Extend the calculator program for multiplication and division (10 points each). Note that the solutions used in the Spigot examples will not work because the operands can be arbitrarily long, e.g.
Enter a problem: 100000000000000000000000000000 / 111111111111 9000000000009000000 Another problem (y/n)? y Enter a problem: 111111111111*111111111111 12345679012320987654321 Another problem (y/n)? n
You may use and modify the solution I posted above, or your own code.
Due midnight Thurs. Nov. 1, 2007 (20 points). Write a time calculator. The program will input expressions of the form time op time where op is + or -, and time has the form hh, hh:mm, or hh:mm:ss meaning hours, minutes and seconds in the range 0 to 23, 0:00 to 23:59, or 0:00:00 to 23:59:59. The output should always have the form h:mm:ss in the range 0:00:00 to 23:59:59, with 2 digits for minutes and seconds. If the result is outside this range, then add or subtract 24 hours. After each problem, ask if the user wants another. For example:
Enter a problem: 5:15 + 23 4:15:00 Another problem (y/n)? y Enter a problem: 4-12:01:59 15:58:01 Another problem (y/n)? n
Use a class Clock with the following public members.
class Clock
{
public:
Clock(string); // accepts the forms "h", "h:mm", or "h:mm:ss"
void add(Clock); // adds to self
void subtract(Clock); // subtracts from self
void print(); // prints in format "h:mm:ss"
};
You can use any private implementation you wish. The class should work as in the following example:
Clock c("3:00");
c.add(Clock("1:05:30")); // 4:05:30
c.subtract("23"); // implicit conversion to Clock("23")
c.print(); // prints 5:05:30
Due midnight Dec. 5, 2007 (40 points). You will write a program that reads a text file and builds a dictionary that associates each word with its frequency -- the number of times it occurs in the input. The program will take two command line arguments: a file name and a number n. Your program will then list the dictionary contents in decreasing order of frequency in the format "k: word" where k is the frequency. If more than one word has frequency k, then print them all on the same line in alphabetical order separated by single spaces. If there are m words with frequency k and m > n, then print the first n words followed by "(m words)". Do not print any blank lines in this list. For example, if the input file contains "a test a test and a test" and n = 2, then the output is:
3: a test 1: andOr if n = 1,
3: a (2 words) 1: and
After printing this list, print a blank line and the following information:
If n is omitted from the command line, then it should default to 10. If the file name is omitted, then print a help message explaining to the user how to run the program. Print an appropriate error message if the user specifies a file name that does not exist. Your program should not read any input from the keyboard.
A word is defined as a sequence of ASCII letters A-Z and a-z, with no punctuation or digits. Treat upper and lower case as equivalent. You may assume that the last character of the file is not a letter. You may assume the file is plain text (not binary).
For example, suppose that file.txt contains:
This is a test. THIS is ANOTHER test!!! and this is yet another test... test1-test2-test 3.You might create a dictionary that would look like this:
a 1 and 1 another 2 is 3 test 6 this 3 yet 1If the name of your program is hw4.cpp, it would run as follows:
hw4 file.txt 6: test 3: is this 2: another 1: a and yet file.txt has 17 words. The dictionary has 7 words. The average word length in file.txt is 3.70588. The average word length in the dictionary is 3.42857. hw4 file.txt 1 6: test 3: is (2 words) 2: another 1: a (3 words) file.txt has 17 words. The dictionary has 7 words. The average word length in file.txt is 3.70588. The average word length in the dictionary is 3.42857. hw4 foo File foo not found. hw4 Usage: hw4 filename [n]
Do not assume that the longest word will be less than a billion letters long. Do not assume there will be less than a billion words or that any word will occur less than a billion times. Do not assume the input file has more than zero letters.
Your program must not take more than one second to run on a modern computer given alice.txt as input. The output should be as follows:
hw4 alice.txt 1642: the 872: and 729: to 632: a 595: it 552: she 545: i 513: of 462: said 411: you 398: alice 369: in 357: was 315: that 263: as 247: her 218: t 211: at 201: s 193: on 182: all 180: with 178: had 170: but 153: for they 151: so 148: be 145: not 144: very 141: what 134: this 128: little 127: he 117: out 108: is 104: one 102: down 100: up 99: there 96: his if 94: about then 90: no 88: know them 85: like were 83: herself went would 82: again 81: do 80: have 79: when 77: could or 75: queen 74: thought 73: off 71: time 68: how me 67: into see 63: can did king m well who 62: your 61: don 60: now 59: turtle 58: began by my 57: an ll 56: hatter its mock way 55: quite 54: are gryphon 53: think 52: just say their 51: first here much rabbit some 50: go head only 49: more thing which 48: never voice 46: come get 45: got looked oh 44: mouse must ve 43: after him 41: duchess round such 40: came dormouse other over tone two why 39: any back great 38: been before re 37: cat 36: from 34: march nothing once we 33: large last will 32: found long looking right tell 31: hare moment put things 30: door heard made next white 29: d day dear eyes look replied 28: caterpillar might three 27: going good make poor seemed should 26: course too upon without won 25: away rather shall soon while yet 24: same sure than took 23: added felt half 22: another getting jury let take 21: find hand minute till wish words 20: anything cried ever however sort 19: being curious even feet old please tea tried 18: court eat end enough house something soup table use wonder 17: asked bill perhaps question sat side spoke talking 16: am bit doesn garden hastily high indeed ran turned under 15: air arm because called done face gave idea low mad (15 words) 14: anxiously baby beginning better both certainly didn dinah everything footman (24 words) 13: always beautiful begin behind cats change close cook dance dodo (29 words) 12: afraid among best chapter deal else finished give hands hardly (18 words) 11: ask book child glad gloves growing hurried hurry keep makes (22 words) 10: birds bottle box children conversation creatures either explain fan foot (37 words) 9: against angrily answer believe butter call coming continued couldn croquet (34 words) 8: appeared asleep beg bright changed distance dry each eagerly everybody (54 words) 7: adventures begun bread business cheshire chin deep draw dream drink (61 words) 6: almost along arms between broken chimney chorus dreadfully e ear (63 words) 5: across ah aloud altogether angry asking become case clock confusion (91 words) 4: age alas alone animals ann answered arches argument bats beat (144 words) 3: above advance advantage alive allow anxious around attending bank bat (228 words) 2: absurd accident addressed advice advisable afterwards ago agree alarm already (395 words) 1: abide able absence acceptance accidentally account accounting accounts accusation accustomed (1122 words) alice.txt has 27331 words. The dictionary has 2576 words. The average word length in alice.txt is 3.93937. The average word length in the dictionary is 6.10481.