CSE1502 Home

Current assignment

Examples

getnum.cpp (parsing strings)
reverse.cpp (vectors)
unique.cpp (vector search)
bubble.cpp (bubble sort)
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)

CSE1502 Suggested Exercises

This homework is not graded or collected. Its purpose is to prepare you for the exams and graded assignments. You will need to know how to solve similar problems to pass the course. The dates in the headings are the dates assigned. It is suggested you do these problems before the following class.

Jan 17

Compile and run guess.cpp.

Read the code and try to understand what each statement does.

Insert braces for the inner while loop in guessGame() and the if and if-else statements in isCorrect(). Make sure the program still compiles and runs. When inserting braces, use the style in the book where each brace is on a line by itself and lines up with the left edge of the code outside the block.

Modify the program to pick a number between 1 and 10 (instead of 1000).

Try replacing all the using std::... statements with just using namespace std (after the last #include statement).

In the statement

  answer = 1 + rand() % 10;
what is the precedence order of + and % ? Place parenthesis around the part of the expression that is evaluated first and run the program again. Make sure the program never picks 0 and sometimes picks 10.

What is the difference between = and == ?

What does the following code print? Check your answers by inserting them into a program.

  int i;

  i = 1;
  while (i < 10)
  {
      cout << i << "\n";
      i = i + 1;
  }


  i = 1;
  do
  {
      cout << i << "\n";
      i = i + 1;
  } while (i < 10);


  i = 0;
  while (i <= 100)
  {
      if (i % 10 == 0)
      {
          cout << i << "\n";
      }
  }

Write a program that prints all the even numbers from 2 to 100.

Write a program that prints 20 random numbers (rand()) using a loop. Run it several times. Is the sequence always the same?

The statement in guess.cpp

  srand( time( 0 ) );
which is commented out, is supposed to seed the random number generator with the system clock, so that the random sequence is different each time. Look up the functions rand(), srand(), and time(). How does it work? Modify your program so that it prints 20 random numbers, but different each time.

Jan. 24

Read chapters 1, 2, and 4 in "C++, How to Program" by Deitel.

Convert the following numbers from binary to decimal: 110, 101110, 11111111
Convert from decimal to binary: 15, 255
Convert from hexadecimal to decimal: FF, ABC, 10000
Convert from decimal to hexadecimal: 15, 255

Write a program to check your hexadecimal answers. In C++ you can write numbers in hexadecimal by appending "0x" to the front. For example, to print ABC (hexadecimal) as a decimal number you can write:

  cout << 0xABC << endl;
You can't write binary numbers in C++, but you can use bin2dec.cpp to check your answers. Compile it and do so.

Modify bin2dec.cpp to convert base 3 to decimal. For example, if the input is 2012, then the output should be 59.

Write a program to input two ints and add them, e.g.

  int number1, number2;
  cin >> number1 >> number2;
  cout << number1 + number2 << "\n";
What happens when you add very large numbers (over 2 billion)? Change the numbers from int to double and repeat the experiment.

Repeat the experiment using multiplication for int and double.

Repeat again with division. What happens when you divide by 0? What is the rule for dividing integers when there is a remainder? Try this for both positive and negative numbers.

What are each of the following? Write a program to check your answer.

  5 / 3
  5.0 / 3
  5 / 3.0
  5.0 / 3.0
  -5 / 3
  -5.0 / 3
  5 / -3
  -5 / -3

Jan 29

Read the Introduction to C++ up through the secton on strings.

What does the following print? Write a program to check your answers.

  string s = "a string";
  cout << s << "\n";
  cout << int(s.size()) << "\n";
  cout << s[3] << "\n";
  cout << s.substr(3, 2) << "\n";
  cout << s.substr(3) << "\n";
  cout << "this is "+s << "\n";
  cout << s+"\n";
  cout << s+s << "\n";

  for (int i = 0; i < int(s.size()); ++i)
    cout << s[i] << "\n";

  for (int i = int(s.size())-1; i >= 0; --i)
    cout << s[i] << "\n";

  for (int i = 0; i < int(s.size()); ++i)
    s[i] = toupper(s[i]);  // in <cctype>
  cout << s << "\n";

  s = "";
  for (char c = 32; c <= 126; ++c)  // see ASCII table
    s += c;
  s += char(10);  // '\n'
  cout << s;

  cout << 'c' << "\n";
  cout << "c" << "\n";
  cout << int('c') << "\n"; // convert to int by ASCII code
  cout << 'c'+1 << "\n";    // implicit conversion to int
  cout << char('c'+1) << "\n";

Write two programs to read in chars one at a time and print them out. How do these differ?

  char c;

  while (cin >> c)
    cout << c << "\n";

  while (cin.get(c))
    cout << c << "\n";

Write two programs to read strings one at a time and print them out. How do these differ?

  string s;

  while (cin >> s)
    cout << s << "\n";

  while (getline(cin, s))
    cout << s << "\n";

Create a text file with a few lines of text. Run the above programs with input redirected to this file using program < filename on the command line.

Write a program that reads a text file and prints the length of the longest word.

Feb 7

Parsing

The following code parses its input into words separated by whitespace and prints each word on a separate line.

  string s;
  while (cin >> s)
    cout << s << "\n";

It is equivalent to the pseudocode below, which reads one character at a time.

  while not end of input
    read a character c
    if c is not a space, tab, or newline
      append c to string s
    else if s is not empty
      output s
      set s empty

Write a program to print each word on a separate line as in the code above, but reading one character at a time (using cin.get(c)). Run the program with the input redirected to a text file. Verify the output is the same. What happens if the file ends with a printable character (not a newline)? Correct the pseudocode and your program to handle this case.

Modify your program to parse the input into words consisting only of letters and digits (a-z, A-Z, 0-9) ignoring punctuation. Thus, "it's" is 2 words. Test your code.

Modify your program so all output is converted to lower case. Modify to convert to all upper case. Modify your program so that words contain letters only (no digits).

vectors

Read the Introduction to C++ section on vectors.

What is the contents of v after executing the following code? What does this print? Write a program to check your answer.

  vector<int> v(3);
  v.push_back(5);
  v[1] = 2;
  cout << int(v.size()) << "\n";
  for (int i=0; i<int(v.size()); ++i)
    cout << v[i] << "\n";

What is the size and contents of w after the following code? Write a program to check your answer.

  vector<string> w;
  w.push_back("hi");
  w.resize(4);
  w[2] = "hello";
  w.push_back("world");

Suppose that w has a size of 10. What is the valid range of indexes (i in w[i])?

Write a program that parses the input into uppercase words as above, but instead of printing them immediately, push them onto a vector. Then print the contents of the vector in forward and reverse order. Test your program with a large text file as input.

Modify your program to print all the words of length 3.

Modify your program to search w for the longest word. Print the word and it's length.

Modify your program to search for each word before appending it to w. Add the word only if you don't find a match.

fstreams

Read the section on fstreams.

The following is supposed to open an input file named in.txt. What is wrong with it?

  string filename = "in.txt";
  ifstream in(filename);

Is this code correct?

  ifstream in("in.txt");

Write a program that prompts the user for a filename and tests whether the file exists or not.

Modify the program so that if the file exists, the entire contents is copied to the screen. Do this reading

Write a program that creates a file (ofstream) named hello.txt containing just the text "Hello world" and a newline.

Modify the program to prompt for the output file name.

Feb 28

Read 6.1-6.3, 6.14, and the section on functions in the introduction to C++.

Explain the difference between pass by value, pass by reference, and pass by const reference. For each one,

Suppose you wanted to write a function to print a string. Which form below would you use? Which form would you use to write a function to input a string?

  void f1(string s);
  void f2(string& s);
  void f3(const string& s);
Which of the following are legal?
  f1("hello");
  f2("hello");
  f3("hello");

Which of the standard library functions below uses pass by reference?

  cin.get(c);
  getline(cin, s);
  s.substr(i, j);
  atoi(s.c_str());
  exit(i);

Write the functions shown below. Pass v by reference or const reference as appropriate. The program should read some text (words separated by whitespace), then print the number of words, the words in reverse order, and the longest word, for example:

  This is a test!!!
  There are 4 words
  test!!!
  a
  is
  This
  The longest word is test!!!


  int main()
  {
    cout << "Enter some text, then EOF\n";
    vector<string> v;
    readWords(v);           // each element gets one word of input
    cout << "There are " 
         << getSize(v)      // returns the number of elements
         << " words\n";
    reverse(v);             // reverses the order of the elements
    printWords(v);          // prints each element on a separate line
    cout << "The longest word is "
         << longestWord(v); // returns longest word in v as a string
         << endl;
    return 0;
  }

Modify the bubble sort program to read a list of integers (not doubles), sort them by the last digit, and print them. For example:

  7 52 94 32 56 123 1000
  1000
  52
  32
  123
  94
  56
  7
(Hint, compare the elements mod 10).

Modify the program so that the bubble sort is done by a separate function (taking a vector passed by reference). The program should read the input, call the function to sort, then print the output.

Run sieve.cpp (a program to print prime numbers up to some limit). What is the largest limit you can enter for which the program will still work? Read the code. Search the Internet for "sieve of Eratosthenes" to understand how it works. How could you make the program faster?

Run table2d.cpp and read the code. The program makes a 2 dimensional vector. How would you make a 3 dimensional vector?

Mar. 15

First read chapter 3 (skipping the optional section).

Separate compilation

Often on large projects with more than one programmer, it is common to split a program into separate source code files. The purpose of these exercises is to learn how to combine them into a single executable program.

A C++ program consists of a set of functions, one of which must be main(). Each function can be compiled in a separate file. However, this will cause errors unless the caller knows the name of the function, the types of its parameters, and its return type. This is normally done with a function prototype, as if the function was defined after it was called. For example, the following will not compile because print() was called before it was declared.

  // Print "hello world"
  #include <iostream>
  #include <string>
  using namespace std;

  int main()
  {
    print("hello world");  // ERROR: print undefined
  }

  void print(string s)
  {
    cout << s << endl;
  }
We could fix the problem by reordering the functions, but another fix is to use a function prototype like this:
  // Print "hello world"
  #include <iostream>
  #include <string>
  using namespace std;

  void print(string);  // prototype

  int main()
  {
    print("hello world");  // OK
  }

  void print(string s)
  {
    cout << s << endl;
  }

We have the same problem if we put print() and main() in separate files, because the compiler only looks at one file at a time.

  // file1.cpp
  #include <iostream>
  #include <string>
  using namespace std;

  int main()
  {
    print("hello world");  // ERROR: print undefined
  }

  // file2.cpp
  #include <iostream>
  #include <string>
  using namespace std;

  void print(string s)
  {
    cout << s << endl;
  }

We could fix the problem by putting a function prototype for print() in file1.cpp. But the preferred method is to put the prototype into a separate header file and include it from both files. A header file by convention has a .h extension. Also, any other common code (like the shared standard library files) can be written only once in the shared header, like this:

  // file1.cpp
  #include "file3.h"
  int main()
  {
    print("hello world");  // ERROR: print undefined
  }

  // file2.cpp
  #include "file3.h"
  void print(string s)
  {
    cout << s << endl;
  }

  // file3.h
  #include <iostream>
  #include <string>
  using namespace std;

  void print(string s);

Note that in #include "file3.h", that the file name is enclosed in "quotes" instead of <angle brackets>. This tells the compiler to look in the current directory. To compile, put all 3 files in the same directory and:

  g++ file1.cpp file2.cpp
Note that you do not include file3.h in the command. It will be inserted when file1.cpp and file2.cpp are compiled. The executable will be named a.exe. You can rename it in the usual way (e.g. to hello.exe):
  g++ file1.cpp file2.cpp -o hello.exe
What happens here is g++ compiles each file to a separate object file (file1.obj and file2.obj) containing executable code (but not a complete program). Then the two object files are linked (along with the library) to produce an executable program.

   file1.cpp      file2.cpp
       |              |
       | compile      | compile
       |              |
       v              v             C++
   file1.obj      file2.obj      libraries
         \            |            /
           \          |          /
             \        |        /
               \      |      /  link
                 \    |    /
                   \  |  /
                     \|/
                  hello.exe
You can run each step separately. The -c option says to compile without linking. To link, pass the .obj file to g++:
  g++ -c file1.cpp
  g++ -c file2.cpp
  g++ file1.obj file2.obj -o hello.exe
Note that if you change file1.cpp there is no need to recompile it as long as you have the .obj files. If the files are very large, this is faster because it saves a step.
  (edit file1.cpp)
  g++ file1.cpp file2.obj -o hello.exe
Or in 2 steps:
  (edit file1.cpp)
  g++ -c file1.cpp
  g++ file1.obj file2.obj -o hello.exe

Exercises

1. How would you compile and link an ordinary program (only one file) in two separate steps? What intermediate file is produced? Do this with the first version of the "hello world" program above.

2. Copy file1.cpp, file2.cpp and file3.h (above), compile, link and run the program. Do the compile/link in 1 step and in 3 steps.

Note: in Visual Studio, read the documentation on how to do this. You want all files to be in the same project. "Build all" is equivalent to compiling everything.

3. Split GuessNumber.cpp into 3 separate files (one for each function), create a header file (with the #include, using statements, and function prototypes), compile, and run it. Note that the function prototypes are already written. Compile and link in 4 steps.

4. Modify guessGame() so that it guesses between 1 and 10 instead of 1 to 1000. Since you have only modified one file, compile just it and link again.

5. In main() the line:

  // srand( time( 0 ) ); // seed random number generator
is commented out. Uncomment it. You will also have to modify the header to add using statements for srand and time. When you modify a header, which files need to be recompiled?

classes

C++ allows you to define new types in addition to the built in types (int, bool, double, etc.) and standard library types (string, vector, ifstream, etc). The mechanism for this is to write a class. A class packages together a set of member functions and a data representation. Normally only the member functions are public, or visible to the user. Once you have written a class, you can then declare objects of that class in the same way you declare objects of existing types.

In the declaration:

  int x = 3, y = x + 2;
int is a type, x and y are objects, and 3 and x + 2 are expressions (constant objects). Identify the types, objects, and expressions in the following statements. What are cout and endl?
  string hi = "hello";
  vector<double> v(4);
  void print(string s)
  {
    cout << s << endl;
  }
List the operations supported by the following types:
  int (for example: +, =, ==, output)
  string (for example ==, .size())
  double
  vector<double>
The notation object.function() is called a member function call. For example, v.size() calls the member function size(), which is a member of the type vector<double>. Which types above have operations that take the form of member functions? Name some other types that do or do not have operations of this form (e.g. bool, char, vector<int>).

The global objects cin and cout are objects of type istream and ostream, respectively. What operations do these types support that have the form of member functions. What operations do these support that have the form of operators (like <<).

Compile and run fig03_01.cpp. What is GradeBook (a type, object, or member function)? What is myGradeBook? What is displayMessage()?

What is the purpose of public? What happens if you remove it?

Compile and run fig03_03.cpp. What type of function is getline (member or standalone)? What type of function is main? What type of function is displayMessage?

Write a program that creates two GradeBook objects, then calls displayMessage on each one.

Compile and run fig03_05.cpp. Modify the program to create two GradeBook objects and give each one a different coursename. Then call displayMessage() on each one.

What does "private" mean? Does the program still work if you change it to public? What effect does this have on the following code:

  cout << myGradeBook.courseName;
  cout << myGradeBook.getCourseName();
Change the "public" to private" and try to compile it. Explain the errors you get.

Compile and run fig03_07. Insert the following line of code after the declarations in main(). What does this do?

  gradeBook1 = gradeBook2;
Is this legal?
  if (gradeBook1 == gradeBook2)
What is a constructor? Modify the constructor in the original program to take no arguments and initialize the course name to "CSE1502". Compile and run.

Add a member function eraseCourseName() that sets the course name to an empty string. Write some test code in main() to test it.

Add (and test) a member function appendToCourseName(s) that appends string s to the course name.

Add (and test) a member function getCourseNameLength() that returns the length of the course name.

Separate compilation of member functions

Member functions, like standalone functions, can be compiled separately. The idea is to replace the member functions in the class with their prototypes and put the rest of the class into a header file as in GradeBook.h. The code for the functions is moved to GradeBook.cpp. Note how each function name has the form class::function to identify what class it belongs to. The functions are called from main() in fig03_17.cpp

Compile and run this program.

Compile and link in 3 separate steps.

Break GradeBook.cpp into 2 files with two member functions each (so you have 4 files total), then compile, link and run.

Combine all the files into one file, but do not put the member function code back into the class. (Concatenate the files with the .h file first, then collect include and using statements at the top and remove duplicates). Compile and run.

When the code for a member function appears inside a class (rather than a prototype), we say the code is inlined. All of the examples up until this one used inlined member functions. When a member function is inlined, the compiler takes this as an optimization hint to expand the code each time the function is called, rather than jumping into the code and back. The effect is that the code runs a little faster but the executable program gets bigger. Ideally, you would want to inline small functions (one or two lines of code), but not longer functions. In GradeBook.cpp, setCourseName is fairly long so we would not want to inline it. The other 3 member functions are fairly short so they could be inlined. Make these changes (still all in one file), then compile and run.

Split the program back into 3 files as before, but leave the inlined member functions in GradeBook.h. GradeBook.cpp should contain only GradeBook::setCourseName().

Apr 4

Read through chapter 8 in the book, skipping the optional sections. Also finish reading the introduction to C++, in particular the sections on maps, algorithm, arrays, command line arguments (in functions) and a new section under fstreams about binary files. This will be all of the reading for the semester.

Binary files

How many bytes will be in the file named out.txt? Examine the file in Notepad. Repeat the experiment using a text file instead of a binary file. (Note: the cygwin g++ compiler in the labs uses binary files by default).

  ofstream out("out.txt", ios::out | ios::binary);
  out << "hello\n";
  out << "world\n";

Command line arguments

Write a program that prints its arguments (as in the example in the introduction to c++).

Write a program that takes 2 file name arguments, an input file and an output file, and copies input to output. Use the program to copy a non-text file (such as a .exe, .jpg, .mp3, .zip, etc). Compare the input and output using the fc/b command. Repeat the experiment using both text files and binary files.

What happens when you run the program with no arguments? Make sure your program handles this with an error message (rather than crashing), e.g. check the value of argc.

Modify the program so that the output is 2 copies of the input. For example if the input is

  This is
  a test.
then the output is
  This is
  a test.
  This is
  a test.
To do this you need to rewind back to the beginning of the input file, e.g.
  in.clear();  // clear EOF condition
  in.seekg(0); // go to position 0 in file
(or see sec. 17.4-17.5 in book).

maps

What does the following print?

  map<int, double> m;
  map<int, double>::iterator p;
  m[3] = 5.2;
  m[5] = 75;
  m[1] = m[5];
  cout << int(m.size()) << "\n";
  for (p = m.begin(); p != m.end(); ++p)
    cout << p->first << " " << p->second << "\n";

  for (int i=0; i<10; ++i)
    cout << m[i] << "\n";
  cout << int(m.size()) << "\n";
  for (p = m.begin(); p != m.end(); ++p)
    cout << p->first << " " << p->second << "\n";

  p = m.find(75);
  if (p == m.end())
    cout << "75 not found\n";
  else
    cout << p->first << " " << p->second << "\n";

  p = m.find(4);
  if (p == m.end())
    cout << "4 not found\n";
  else
    cout << p->first << " " << p->second << "\n";

  m.erase(p);
  m.erase(8);
  cout << int(m.size()) << "\n";
  m.clear();
  cout << int(m.size()) << "\n";

Which statements are legal?

  p->first = 0;
  p->second = 0;
  p = 0;

What does the following code do?

  map<string, bool> m;
  string s;
  while (cin >> s)
  {
    if (m[s])
      cout << s << "\n";
    m[s] = true;
  }
What is the output of the above code with the following input?
  this is a test
  this is another test
Write code to print all the words in m.

What does the following code do?

  map <char, int> m;
  map <char, int>::iterator p, q;
  int c;
  while ((c = cin.get()) != EOF)
    ++m[c];

  q = m.begin();
  for (p = m.begin(); p != m.end(); ++p)
  {
    cout << p->first << " " << p->second; << "\n";
    if (p->second > q->second)
      q = p;
  }
  cout << "the most common letter is " << q->first << "\n";

Modify the above code to print the number of times the most common letter occurs.

Modify the above code to find the second most common letter and its count. (Hint, set q->second = 0 and scan m again).

Write code to print the count for every letter in order from most frequent to least frequent. (Hint, write an outer loop that repeats until q->second is 0).

The program above crashes if there is no input (the first character is EOF). Why? How can this be fixed?

Modify the above code to count words instead of letters (separated by white space).

Modify the above code to count words consisting of letters only. (Use the parsing code from homework 2, but without conversion to upper case).

Modify the code to stop after the first 128 words.

Modify the code to save the words in a vector<string> instead of printing them. Then print the vector to test your code.