CSE1502 - Introduction to Software Development with C++

Matt Mahoney

Instructors

Textbook

C++, How to Program, 5th Ed., Deitel

Additional Course Material

Introduction to C++ (The short version)
C++ Reference (The long version)
Guidelines for Object Oriented Programming
Code examples from the book

getnum.cpp (parsing strings)
reverse.cpp (vectors)
unique.cpp (vector search)
table2d.cpp (2-dimensional vectors)
sieve.cpp (computing prime numbers)
sortword.cpp (sort, iterators)
isort.cpp (stable_sort, functions, overloading, pass by reference)
dict.cpp (map)

Schedule (Fall 2006)

Mon., Wed., and Fri., 9:00-9:50 AM, 10:00-10:50 AM, or 11:00-11:50 AM. Room: Olin EC228/229 (combined rooms). There is no 8:00-8:50 class. You may switch sections if space is available.

Aug. 21 - Matt Mahoney, introduction.
Aug. 23, 25, 28, 30, Sept. 1, 6, 8, 11 - Matthew Eisenbraun.
Sept. 13 - Matt Mahoney, guest lecture, instructor evaluation.
Sept. 15, 18, 20 - Matthew Eisenbraun.
Sept. 22 - Matt Mahoney, guest lecture.
Sept. 25, 27 - Matthew Eisenbraun, exam #1.
Sept. 29 - Matt Mahoney, guest lecture.
Oct. 2, 4, 6, 11, 13, 16, 18 - Lajos Nagy.
Oct. 20 - Matt Mahoney, guest lecture, instructor evaluation.
Oct. 23, 25, 27, 30, Nov. 1, 3 - Lajos Nagy, exam #2.
Nov. 6, 8, 13, 15, 17, 20, 27, 29, Dec. 1, 4, 6 - Matt Mahoney, exam #3.
Dec 11, 8:00-10:00 AM - final exam for 11:00 class.
Dec 12, 8:00-10:00 AM - final exam for 10:00 class.
Dec 13, 8:00-10:00 AM - final exam for 9:00 class.
You may take your final exam on any of the 3 days above, regardless of which class you are in.

Grading policy

There will be three instructors. Each instructor will teach for one third of the semester (about 5 weeks) with an exam at the end. Each instructor will have his own policy for homework and grading. Your final grade will depend equally on the grades assigned by each instructor except for the final exam. I (Matt Mahoney) will be the instructor in charge, will grade the final exams, and will have final responsibility for your grades. Please email me if you have a conflict with your other instructors that you cannot resolve with them.

Your final grade will be based on 50% homework and 50% exams. Your homework grade will be the sum of the grades assigned by each of the 3 instructors, weighted equally. Each instructor will award up to 100 homework points. Each instructor will also give one exam at the end of his 5 week segment, graded on a scale of 0 to 100. In addition, there will be a final exam on a scale of 0 to 100. Your final grade is calculated as follows:

Final grade = (sum of homework)/6 + (sum of best 3 exams)/6.

90-100=A, 80-89=B, 70-79=C, 60-69=D, 0-59=F.

The lowest exam grade is dropped. Thus, you may opt to skip the final exam if you are satisfied with your grade to that point. There are no makeup exams for any reason. If you miss an exam, then that is your drop.

You are expected to know the CS department policy on academic honesty.

Mailing list

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 C++ or your homework here, because other students might have the same questions.

Policy for Matt Mahoney

The following applies only to the last third of the semester taught by me. Each instructor will have his own policy.
Policy for Lajos Nagy
Policy for Matthew Eisenbraun (no website yet)

Exam Policy

Exam #3 and the final exam will be open book and open notes. You may not use a computer or electronic devices. For examples of what to expect, see my CSE 2050 class. Exam #3 will be Dec. 4, 2006.

Exam #3 solution (PDF)
Final exam solutions (4 versions, distributed randomly to students): a b c d

Homework Policy

You may use any C++ compiler on any computer to write your code. Homework must be submitted by email by midnight of the due date. Late penalty: 20% per day. Send ONE plain text .cpp file as an attachment, or as inline text if your email does not support attachments. Lines should not exceed 80 characters in length. Do not submit executables. All programs should have as comments:

Homework 1

Due Mon. Nov. 27, 2006, midnight (40 points). This will be 40% of your homework grade for this third of the course. There will be one more assignment due Dec. 6 worth 60%.

Write a program that prompts for and reads characters from standard input up to EOF. Then for each letter that occurs at least once, it prints the letter followed by a colon and the number of occurrences. Finally, it prints the letter that occurs most frequently. (In case of a tie, pick either one). For example:

  Enter some text, followed by EOF
  This is a TEST!!!
  ^Z
  a: 1
  e: 1
  h: 1
  i: 2
  s: 3
  t: 3
  The most frequent letter is s

The program should consider upper and lower case letters as equal, and print the result using lower case letters. The table should list the letters alphabetically as shown. All other input characters should be ignored.

The program will have three parts, two of which are given below. You should supply only the third file. Your program will be compiled as follows:

  g++ yourprogram.cpp main.cpp
where yourprogram.cpp is the file you send to me by email. (You can name it how you like). The other files are given below and may be cut and paste to your computer for testing. (Do not send them to me. I already have them). They are named textanalyzer.h and main.cpp
// textanalyzer.h
class TextAnalyzer
{
public:
  TextAnalyzer();       // Initialize counters to 0
  void countChars();    // Read input and count letters
  void printResults();  // For each letter, print its count
  char mostFrequent();  // Return the letter (lowercase) that has the highest count
private:
  int count[26];        // Counts for a-z
};


// main.cpp
#include <iostream>
#include "textanalyzer.h"
using namespace std;

int main()
{
  TextAnalyzer t;

  cout << "Enter some text, followed by EOF\n";
  t.countChars();    // Read input until EOF
  t.printResults();  // Print counts for each letter
  cout << "The most frequent letter is " << t.mostFrequent() << endl;
  return 0;
}

Your program should be organized as suggested in the comments in textanalyzer.h. Also be sure to comment each of the member functions (as a whole, not line by line) and to indent appropriately. Neatness and readability count.

You may submit homework early for comments and a chance to make corrections before I grade the final version. There is no guarantee I can do this if you give it to me the day before it is due, and I won't if you give it to me on the due date.

Solution

Homework 2

Due Dec. 6, 2006, midnight (60 points). Write a program that inputs a text file and outputs the following information.

For this program, a word is considered a sequence of letters from a-z, but does not include digits, punctuation, or any other characters. Upper and lower case are equivalent. For example, if the input is "This is a test -- this is ANOTHER test.", your output might be:
  is      2
  test    2
  this    2
  a       1
  another 1

  There are 8 words.
  There are 5 unique words.
  There are 2 words that occur once.
  The longest word "another" has 7 letters.
Your program should be all in once source code file. Include comments that describe what the program does at the top of your program. These comments should be more detailed than the assignment described here. They should also include details that I have omitted and you have assumed. For example, how does the user specify the source of the input? In what order do you list words with equal counts. If two words have the same length, how do you choose? How is the output formatted? What happens if there are no words in the input? Are there any limits on the number of words, length of the longest word, size of the input file, etc.? You can make these decisions how you like, but you must document them. Giving an example helps. I recommend doing this before writing any code.

As usual, you may submit homework early for comments. If you do, be sure to include the documentation, not just code.

Solution

Extra Credit

Extra credit is due midnight Dec. 6, 2006 (50 points). There is no partial credit for late papers (unlike regular assignments which have a 20% late penalty per day). As usual, you may turn in programs early for comments. I will only grade the final version.

The assignment is to write a program to sort a list of dates, one per line. A date has the form month day year, where the month may be abbreviated to 3 or more letters or could be a number from 1 to 12, the day is 1 or 2 digits, and the year is 4 digits. There might also be various punctuation characters and spaces within, before, or after the date, but no other letters or digits. Any line containing a valid date of this form should be copied unchanged to the output in correct order. Any other line should be discarded. For example, if the input is:

  Jan. 1, 2006
   Nov. 22, 1963
  October 12 1492
  Not a date
  This program is due Dec. 6, 2006 at midnight.
  SEP 11 2001
  febr 02 2006
  12/31/2005
The output would be:
  October 12 1492
   Nov. 22, 1963
  SEP 11 2001
  12/31/2005
  Jan. 1, 2006
  febr 02 2006

You may choose the following easier problems for fewer points.

40 pts: You may assume that the input contains only valid dates, such as those that appear in the output of the example above.

30 pts: You may assume that all input has one of two forms:

  Mmm dd yyyy         e.g. Sep 11 2001 or Dec 06 2006
  mm/dd/yyyy          e.g. 09/11/2001  or 12/06/2006
The month will be a number 01-12 or one of exactly Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec

20 pts: You may assume all input has the form Mmm dd yyyy as above.

10 pts: You may assume all input has the form mm/dd/yyyy as above. In all cases, mm is 01-12, dd is 01-31 and yyyy is 0000-9999.

Be sure to comment your program to say which problem you are solving.

Solution

Suggested Homework

Suggested homework is not collected or graded. However, you should do it anyway. You will need these skills to pass the course.

Assigned Nov. 6, 2006

1. Compile and run Fig. 3.5

2. Modify the code in main() to create 2 GradeBook objects, e.g.

  GradeBook gradebook1, gradebook2;
Then write some code to give each GradeBook a different value. Call .dispayMessage() on each GradeBook to verify that the two values are different.

3. What happens if you assign one Gradebook to the other like this?

  gradebook1 = gradebook2;

4. Is it possible to compare GradeBooks, e.g. if (gradebook1 == gradebook2) ?

5. Add a member function to GradeBook that tests whether the course name is a particular value, e.g.

  gradebook1.setCourseName("c++");
  if (gradebook1.hasCourseName("c++"))  // true
    cout << "course name is c++\n";
  if (gradebook1.hasCourseName("java"))  // false
    cout << "course name is java\n";
In other words, the member function hasCourseName() should take a string argument and return bool.

6. Why can't you do this?

  if (gradebook1.courseName == "c++")

Assigned Nov. 8, 2006

Finish reading chapter 3 and start chapter 4.

Compile and run fig. 3.11-13 using your favorite compiler: gradebook.cpp gradebook.h main.cpp

What is the command to compile in g++ in one step?

What are the commands to compile each of the two .cpp files separately, then link them?

For each of the 3 files, what are the commands to compile in the fastest possible way if you change just that one file. (Think about what happens if you change gradebook.h).

In the last homework, you added a member function to test whether a GradeBook has a particular course name, e.g.

  GradeBook gradeBook1("C++ programming");
  if (gradeBook1.hasCourseName("C++ programming"))
    cout << "it works\n";

Repeat this exercise. You will need to add a definition (with no code) to gradebook.h, code for the member function to gradebook.cpp, and some test code to main() (such as above) to check that it works.

Assigned Nov. 13, 2006

Read chapter 4, skipping the optional section at the end.

Compile and run fig. 4.12-14 main.cpp gradebook.cpp gradebook.h

Provide input to make the class average 100, then 99.67.

Remove "<< fixed" from the last cout statement in gradebook.cpp. What happens?

Remove "<< setprecision( 2 )" from gradebook.cpp. What happens?

For each of the following, will the average be rounded to an integer or print exactly? Try it to test your answer.

  average = (total + 0.0) / gradeCounter;
  average = (total + 0) / gradeCounter;
  average = total / (gradeCounter * 1.0);
  average = 1.0 * total / gradeCounter;
  average = total / gradeCounter * 1.0;
  average = 0.0 + total / gradeCounter;
  average = static_cast< double > (total / gradeCounter);

Remove the check for division by 0, then run with no students. What happens?

Rewrite GradeBook::determineClassAverage() so that the program first asks for the number of students, then prompts for each grade, e.g.

  Enter number of students: 3
  Enter grade: 90
  Enter grade: 100
  Enter grade: 80

  Total of all 3 grades entered is 270
  Class average is 90.00

Assigned Nov. 15, 2006

Read chapter 5, skipping the optional section at the end.

Compile and run fig. 5.9-5.11 main.cpp gradebook.cpp gradebook.h

Run the program with the input redirected from a text file containing some grades instead of entering the grades from the keyboard. e.g. create a file grades.txt with Notepad containing some grades:

  abcdf
  A B C D F
  cat
If the executable is a.exe, run like this in the command window and verify the output is the same as you would get if you enter the grades from the keyboard:
  a < grades.txt

Rewrite the switch statement in gradebook.cpp using an if statement. Run the program with the input redirected to grades.txt. Verify the output is the same.

Modify the program so the user can quit by typing q instead of EOF. Run the program interactively (entering grades from the keyboard).

Modify the program to accept either q, Q, or EOF to end the input. Test interactively and from an input file.

Assigned Nov. 17, 2006

Read chapters 6.1-6.8, 6.14, 22.9, and 7.1-7.11.

Write a program to print the ASCII table.

  for (int i=0; i<256; ++i)
    cout << i << ": " << static_cast<char>(i) << endl;

Write a program that inputs a single character, and if it is upper case, converts it to lower case, then print it. Do this using character arithmetic, then using the functions in <cctype>.

Write a program to print 20 random numbers using rand(). Run it twice.

Assigned Nov. 20, 2006

In the Introduction to C++, read the sections on char, string, and vector.

Compile and run getnum.cpp and reverse.cpp.

Modify getnum.cpp to parse words (as discussed in class), where a word is:

Modify reverse.cpp so that v is a vector<string> (instead of int) and the program reads a list of words instead of numbers.

Change the program to print the words in the original order.

Change the program to read a single word and store single letters into a vector<char>. Then print the word by printing the letters one by one. Then write code to test if the word is a palindrome.

Assigned Nov. 29, 2006

Compile and run table2d.cpp. In the last two pairs of nested for loops, replace width and height using .size() and test.

Next, create a triangular table (ignoring width) where row i has size i + 1. For height = 5, the output should look like this:

  0
  0   1
  0   2   4
  0   3   6   9
  0   4   9  16  25

Compile and run sieve.cpp. Experiment with different limits until the program no longer runs. For the largest value that runs, how much memory is used? (In WinXP, use Ctrl-Alt-Del to bring up Task Manager and click on the "processes" tab).

Compile and run sortword.cpp. Test it with a large text file (such as the source code). Change the last for loop to the following and run it again. What does it do?

  for (p = v.end()-1; p >= v.begin(); --p)
    cout << *p;

Change the program to sort whole lines instead of words (use getline).

Change the program to ignore blank lines (s == "").

What does the following do?

  cout << *v.begin();
  cout << *(v.end() - 1);
  cout << *(v.begin() + int(v.size()) - 1);
  *v.begin() = "foo";
  v[0] = "bar";

Rewrite the last for loop using indexes (v[i]).

Compile and run isort.cpp. Create a test file to verify that it sorts case insensitive. Verify that equal strings such as "Cat", "CAT" and "cat" stay in the original order.

(overloading, read sec. 6.17) How does the program know that the statement

  s[i] = tolower(s[i]);
in tolower() is not a recursive call to itself? How does the program know that the calls to tolower() in lessThanCaseSensitive() are calls to the function above and not to tolower() defined in <cctype>?

(pass by reference, read 6.14) What does the & in the following code mean? What happens if you remove it?

  void tolower(string& s)
What happens if you change the parameters in lessThanCaseInsensitive to pass by reference (using &)?

What is the difference between sort() and stable_sort()? (Both can take a third argument to define comparison of elements). Try both. Are equal strings (except for case) still in the original order? For both sorts, what happens if you remove the third argument.

Modify the program to sort in reverse order by changing only lessThanCaseInsensitive(). Modify the program to sort case sensitive. Modify the program to sort by increasing (or decreasing) word length, maintaining the original order of words of equal length. Modify the program to sort by word length, then alphabetically for words of equal length.

Modify the last for loop to print the result using iterators.

(optional, will not be on exam #3). Read the section on maps in the quick reference Compile and run dict.cpp. Study the code. Modify the program to print the number of words that occur exactly once. Modify it to print the word that occurs most frequently. Modify it to print the 10 most frequent words (e.g. you could set the count to 0 after printing each word and repeat 10 times). Modify it to find and print the longest word. Modify it to print the number of unique words (dict.size()). Modify it so that all words are lower case. Modify it so that words consist of only letters.