CSE2050 Spring 2005 Exam #1, open book, open notes. Name __________________

1.  What do the following print (5 pts each)?
                                                        ANSWERS
  cout << int(10 < 20 < 5);                             1   (because (10<20)==1 and 1<5)
  cout << -10 % 3;                                      -1
  int a=10, b=20; cout << ((a=b) ? ++a : ++b+5);        21  (a=b sets a=20 and converts to true)
  vector<int> v(4); v.push_back(8); cout << v.size();   5

2.  Given the following declarations:

  string::iterator p;
  string::const_iterator cp;
  const string s("abcde");

Which statements are legal (YES or NO)?  (3 pts each)

                  ANSWERS                                     ANSWERS
  p = s.begin();  no (s is const)       *cp = *p;             no (assignment to const)
  cp = p;         yes                   ++cp;                 yes
  p = cp;         no (*cp is const)     ++*p;                 yes
  p < cp;         yes                   cout << p - cp;       yes
  *p = *cp;       yes                   cout << *s.begin();   yes

3.  The function perm(a, b) should take two strings, a and b, and return
true if and only if it is possible to reorder the characters in one string
to exactly match the other.  Write perm() in perm.cpp so that it can
be called from main() in testperm.cpp (below), and write an appropriate
header file, perm.h, included from both .cpp files.  Show the g++
command to compile and link the program.  For perm(), use the most
appropriate parameter passing methods.  Your function should
run no slower than O(n log n).  (50 pts)

  // testperm.cpp
  #include "perm.h"
  int main() {
    const string s = "abcc";
    if (perm(s, "cacb") && !perm("abbc", s) && !perm(s, "ABCC"))
      cout << "It works\n";
    return 0;
  }

  // ANSWER #1.  Sort the characters, then compare.  We use pass by value
  // so that we get a copy we can sort, then discard.

  // perm.cpp
  #include "perm.h"
  bool perm(string a, string b) {
    sort(a.begin(), a.end());  // O(n log n)
    sort(b.begin(), b.end());  // O(n log n)
    return a==b;               // O(n)
  }

  // perm.h
  #include <iostream>   // for main()
  #include <string>
  #include <algorithm>  // sort()
  using namespace std;  // for main()
  bool perm(string, string);

  To compile: g++ perm.cpp testperm.cpp

  // ANSWER #2.  Count all the a's, b's, c's, etc.  Compare the counts for the 2 strings.
  // This runs in O(n) if the counts are stored in a vector, or in O(n log n) if stored
  // in a map.  If using a vector, we need 256 elements, one for each possible character.
  // A char is usually signed (-128 to 127) but could be unsigned (0 to 255) depending
  // on the environment.  The code below will work in either case.  We don't modify
  // the arguments, so we pass by const reference.

  // perm.cpp
  bool perm(const string& a, const string& b) {
    vector<int> va(384), vb(384);
    for (int i=0; i<int(a.size()); ++i)
      ++va[a[i]+128];
    for (int i=0; i<int(b.size()); ++i)
      ++vb[b[i]+128];
    return va==vb;
  }

  // perm.h
  #include <iostream>
  #include <string>
  #include <vector>
  using namespace std;
  bool perm(const string&, const string&);

  To compile: g++ perm.cpp testperm.cpp  (unchanged)