Instructor: Matt Mahoney, mmahoney@cs.fit.edu or matmahoney@yahoo.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
// Set i to first zero element in v, or to N if not found int i; for (i=0; i<N; ++i) { if (v[i]==0) break; }
Due Tues. Jan. 18, 2005. (5 pts). Compile and run the "hello world" program on page 1 using g++ under UNIX. Add comments as described above. If you are not familiar with UNIX, see http://www.emba.uvm.edu/CF/basic.html for a description of basic commands.
Due Tues. Jan. 25, 2005 (10 pts). Write a C++ program like the one in chapters 1 and 2, except that it prints a right triangle around the greeting instead of a rectangle as shown below. There should be no limit on name length.
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 Tues. Feb. 15 (25 pts). Write a program nword.cpp that takes as arguments a number n and a list of file names. Your program should print a list of words (sorted alphabetically) that occur at least once in exactly n of the files. For example, if you have the following files:
file1 file2 file3 This is a test. This is THIS IS YET another test! ANOTHER TEST YET AGAIN!!! nword 1 file1 file2 a another nword 2 file1 file2 file3 another nword 3 file1 file2 file3 is test this nword 1 file3 file2 again yet nword 1 file3 again another is test this yet
Note that if a word (like YET) occurs twice in one file, it is counted only once. A word is defined as a sequence of one or more letters (a-z) and does not include punctuation, digits, spaces, or other characters. Case is not signficant.
Due Tues. Mar. 22 (30 pts). Write a program tcalc.cpp that evaluates expression involving both real numbers and time values of the form hh:mm or hh:mm:ss, ranging from 00:00:00 to 23:59:59. If n is a number and t is a time object, then the following operations are valid and produce a result with the type shown:
n+n -> n t+t -> t n-n -> n t-t -> t n*n -> n n*t -> t t*n -> t n/n -> n t/n -> t t/t -> nArithmetic on numbers has its normal meaning. Arithmetic on time is computed modulo 24 hours and rounded to the nearest second. Your program should input an expression on a single line and then print the answer, repeating until a blank line is entered. An expression may be arbitrarily long and contain parenthesis. Precedence order should be the same as C++. For example:
tcalc 12:30+13:35:02 2:05:02 9:05 * 3 3:15 1:00/5.0 0:12 1:00/-1.0 23:00 3:00/2:00 1.5 0:01:00/14 0:00:04 1:00 * 3 + 2:00/4.0 3:30 (1:00+2:30)*2-0:10-0:01 6:49Your program should give an appropriate error message but continue running after bad input such as:
1:00*2:00 Type mismatch 3+4+*) Syntax error 3+a Invalid input 2:30/(3*2-6) Division by 0 24:60:61 Time out of rangeYour program should use object oriented techniques. Write a class called Time. Overload operators as appropriate.
Hint: write a recursive descent parser. Throw exceptions to handle errors. For an example, see the solution to Spring 2004 assignment 5.
Due Tues. Apr. 19, 2005 (30 pts). Write a program to sort a file using a sorted queue. Your program should work as a pipe:
sort method < input > outputshould work exactly like the UNIX or MSDOS sort program, sorting line by line in ASCII order. Your program should take one argument, method, consisting of a lowercase letter, either m (map), q (priority queue), v (sorted vector), or h (heap). Whichever method is used, your program must run in O(n log n) time and produce exactly the same output.
Write an interface, SortedQueue<T> with four derived implementations corresponding to each of the four methods. Your interface should have the following public members:
insert(x) - inserts an object x of type T size() - returns number of objects stored, initially 0 remove() - removes and returns the smallest x if size() > 0For example, to sort:
SortedQueue<string>* sq; switch (argv[1][0]) { // method case 'm': sq = new MapQueue<string>; break; case 'q': sq = new PriorityQueue<string>; break; case 'v': sq = new VectorQueue<string>; break; case 'h': sq = new HeapQueue<string>; break; default: // handle error } string s; while (getline(cin, s)) sq->insert(s); while (sq->size() > 0) cout << sq->remove() << "\n"; delete sq;Your four implementations should be as follows:
The root is the next item to remove. After removal, replace the root with the last leaf node. If the new root is larger than either child then swap it with the smaller child, continuing down the tree until the heap property is restored.
To insert an item, add a leaf node, then while it is smaller than the parent, swap it, working upward until the heap property is restored.
The heap should be represented as a vector without pointers: element i has children 2i+1 and 2i+2, and parent (i-1)/2. Element 0 is the root.
2 / \ +---+---+---+---+---+---+ / \ | 2 | 4 | 7 | 9 | 5 | 8 | 4 7 +---+---+---+---+---+---+ / \ / 0 1 2 3 4 5 9 5 8 A heap viewed as a tree and as an array
Have the program print (to cerr) the execution time using clock(). Test on a large file. Which method is fastest?
Spring 2005 Exam solutions
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.
Fall 2004 Homework and Exam solutions
Fall 2004 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.
Spring 2004 Homework and Exam solutions
Spring 2004 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.
Fall 2003 Homework and Exam Solutions
Fall 2003 syllabus and homework
Exam 1 solution.
Exam 2 solution.
Exam 3 solution.
Final Exam solution.
Spring 2003 Homework and Exam Solutions
Spring 2003 syllabus and homework
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.
Final 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.