$24
Homework 4 Solution
The files Sequence.h and Sequence.cpp contain the definition and implementation of Sequence implemented using a doubly-linked list. A client who wants to use a Sequence has to change the typedef in Sequence.h, and within one source file, cannot have two Sequences containing different types.
Eliminate the typedef, and change Sequence to be a class template, so that a client can say
#include "Sequence.h"
#include <string
using std::string;
...
Sequence<int si;
Sequence<string ss;
si.insert(7);
ss.insert("7-Up");
...
Also, change subsequence and interleave to be function templates.
(Hint: Transforming the typedef-based solution is a mechanical task that takes only five minutes if you know what needs to be done. What makes this problem non-trivial for you is that you haven't done it before; the syntax for declaring templates is new to you, so you may not get it right the first time.)
(Hint: Template typename parameters don't have to be named with single letters like T; they can be names of your choosing. You might find that by choosing the name ItemType, you'll have many fewer changes to make.)
(Hint: The Node class nested in the Sequence class can talk about the template parameter of the Sequence class; it should not itself be a template class.)
The definitions and implementations of your Sequence class template and the subsequence and interleave template functions should be in just one file, Sequence.h, which is all that you will turn in for this problem. Although the implementation of a non-template non-inline function should not be placed in a header file (because of linker problems if that header file were included in multiple source files), the implementation of a template function, whether or not it's declared inline, can be in a header file.
There's a C++ language technicality that relates to a type declared inside a class template, like N below:
template <typename T
class S
{
...
struct N
{
...
};
N* f();
...
};
The technicality affects how we specify the return type of a function (such as S<T::f) when that return type uses a type defined inside a template class (such as S<T::N). If we attempt to implement f this way:
template <typename T
S<T::N* S<T::f()
// Error!
Won't compile.
{
...
}
the technicality requires the compiler to not recognize S<T::N as a type name; it must be announced as a type name this way:
template <typename T typename S<T::N* S<T::f() {
// OK
...
}
2. Consider this program:
#include "Sequence.h" // class template from problem 1
class Complex
{
public:
Complex(double r = 0, double i = 0)
m_real(r), m_imag(i)
{}
double real() const { return m_real; }
double imag() const { return m_imag; }
private:
double m_real;
double m_imag;
};
int main()
{
Sequence<int si;
si.insert(50);
// OK
Sequence<Complex sc;
sc.insert(0, Complex(50,20)); sc.insert(Complex(40,10));
// OK
// error!
}
Explain in a sentence or two why the call to the one-argument form of Sequence<Complex::insert causes at least one compilation error. (Notice that the call to the one-argument form of Sequence<int::insert is fine, as is the call to the two-argument form of Sequence<Complex::insert.) Don't just transcribe a compiler error message; your answer must indicate you understand the ultimate root cause of the problem and why that is connected to the call to Sequence<Complex::insert.
Many applications have menus organized in a hierarchical fashion. For example, the menu bar may have File, Edit, and Help menu items. These items may have submenus, some of which may have submenus, etc. Every menu item has a name. When describing the full path to a menu item, we separate levels with slashes (e.g., "File/New/Window"). The following program reflects this structure:
#include <iostream
#include <string
#include <vector
using namespace std;
class MenuItem
{
public:
MenuItem(string nm) : m_name(nm) {}
virtual ~MenuItem() {}
string name() const { return m_name; }
virtual bool add(MenuItem* m) = 0;
virtual const vector<MenuItem** menuItems() const = 0; private:
string m_name;
};
class PlainMenuItem : public MenuItem {
// PlainMenuItem allows no submenus
public:
PlainMenuItem(string nm) : MenuItem(nm) {} virtual bool add(MenuItem* m) { return false; }
virtual const vector<MenuItem** menuItems() const { return NULL; }
};
class CompoundMenuItem : public MenuItem // CompoundMenuItem allows submenus {
public:
CompoundMenuItem(string nm) : MenuItem(nm) {} virtual ~CompoundMenuItem();
virtual bool add(MenuItem* m) { m_menuItems.push_back(m); return true; } virtual const vector<MenuItem** menuItems() const { return &m_menuItems; }
private:
vector<MenuItem* m_menuItems;
};
CompoundMenuItem::~CompoundMenuItem()
{
for (int k = 0; k < m_menuItems.size(); k++)
delete m_menuItems[k];
}
void listAll(const MenuItem* m, string path) // two-parameter overload {
You will write this code.
}
void listAll(const MenuItem* m) // one-parameter overload {
if (m != NULL)
listAll(m, "");
}
int main()
{
CompoundMenuItem* cm0 = new CompoundMenuItem("New"); cm0-add(new PlainMenuItem("Window")); CompoundMenuItem* cm1 = new CompoundMenuItem("File"); cm1-add(cm0);
cm1-add(new PlainMenuItem("Open")); cm1-add(new PlainMenuItem("Exit")); CompoundMenuItem* cm2 = new CompoundMenuItem("Help"); cm2-add(new PlainMenuItem("Index")); cm2-add(new PlainMenuItem("About"));
CompoundMenuItem* cm3 = new CompoundMenuItem(""); // main menu bar
cm3-add(cm1);
cm3-add(new PlainMenuItem("Refresh")); // no submenu
cm3-add(new CompoundMenuItem("Under Development")); // no submenus yet
cm3-add(cm2);
listAll(cm3);
delete cm3;
}
When the listAll function is called from the main routine above, the following output should be produced (the first line written is File, not an empty line):
File
File/New
File/New/Window
File/Open
File/Exit
Refresh
Under Development
Help
Help/Index
Help/About
Each call to the one-parameter overload of listAll produces a list, one per line, of the complete path to each menu item in the tree rooted at listAll's argument. A path is a sequence of menu item names separated by "/". There is no "/" before the first name in the path.
a. You are to write the code for the two-parameter overload of listAll to make this happen. You must not use any additional container (such as a stack), and the two-parameter overload of listAll must be recursive. You must not use any global variables or variables declared with the keyword static, and you must not modify any of the code we have already written or add new functions. You may use a loop to traverse the vector; you must not use loops to avoid recursion.
Here's a useful function to know: The standard library string class has a + operator that concatenates strings and/or characters. For example,
string s("Hello");
string t("there");
string u = s + ", " + t + '!';
// Now u has the value "Hello, there!"
It's also useful to know that if you choose to traverse an STL container using some kind of iterator, then if the container is const, you must use a const_iterator:
void f(const list<int& c) // c is const
{
for (list<int::const_iterator it = c.begin(); it != c.end(); it++)
cout << *it << endl;
}
(Of course, a vector can be traversed either by using some kind of iterator, or by using operator[] with an integer argument).
For this problem, you will turn a file named list.cpp with the body of the two-parameter overload of the listAll function, from its "void" to its "}", no more and no less. Your function must compile and work correctly when substituted into the program above.
b. We introduced the two-parameter overload of listAll. Why could you not solve this problem given the constraints in part a if we had only a one-parameter listAll, and you had to implement it as the recursive function?
a. Suppose we have a list of N users of a social networking site, numbered from 0 to N-1. The two-dimensional array of bool isFriend records who is friends with whom: isFriend[i][j] is true if and only if user i and user j are friends.
Now, for every pair of users i and j, we'd like to determine how many mutual friends they have.
Here's the code:
const int N = some value;
bool isFriend[N][N];
...
int numMutualFriends[N][N];
for (int i = 0; i < N; i++)
{
numMutualFriends[i][i] = -1; // the concept of mutual friend // makes no sense in this case
for (int j = 0; j < N; j++)
{
if (i == j)
continue;
numMutualFriends[i][j] = 0;
for (int k = 0; k < N; k++)
{
if (k == i || k == j)
continue;
if (isFriend[i][k] && isFriend[k][j])
numMutualFriends[i][j]++;
}
}
}
What is the time complexity of this algorithm, in terms of the number of basic operations (e.g., additions, assignments, comparisons) performed: Is it O(N), O(N log N), or what? Why? (Note: In this homework, whenever we ask for the time complexity, we care only about the high order term,
so don't give us answers like O(N2+4N).)
b. The algorithm in part a doesn't take advantage of the symmetry of friendship: for every pair of users i and j, isFriend[i][j] == isFriend[j][i]. We can skip a lot of operations and compute the number of mutual friends more quickly with this algorithm:
const int N = some value;
bool isFriend[N][N];
...
int numMutualFriends[N][N];
for (int i = 0; i < N; i++)
{
numMutualFriends[i][i] = -1; // the concept of mutual friend // makes no sense in this case
for (int j = 0; j < i; j++) // loop limit is now i, not N {
numMutualFriends[i][j] = 0;
for (int k = 0; k < N; k++)
{
if (k == i || k == j)
continue;
if (isFriend[i][k] && isFriend[k][j])
numMutualFriends[i][j]++;
}
numMutualFriends[j][i] = numMutualFriends[i][j];
}
}
What is the time complexity of this algorithm? Why?
a. Here again is the non-member interleave function for Sequences from Sequence.cpp:
void interleave(const Sequence& seq1, const Sequence& seq2, Sequence& result)
{
Sequence res;
int n1 = seq1.size();
int n2 = seq2.size();
int nmin = (n1 < n2 ? n1 : n2);
int resultPos = 0;
for (int k = 0; k < nmin; k++)
{
ItemType v;
seq1.get(k, v);
res.insert(resultPos, v);
resultPos++;
seq2.get(k, v);
res.insert(resultPos, v);
resultPos++;
}
const Sequence& s = (n1 nmin ? seq1 : seq2);
int n = (n1 nmin ? n1 : n2);
for (int k = nmin ; k < n; k++)
{
ItemType v;
s.get(k, v);
res.insert(resultPos, v);
resultPos++;
}
result.swap(res);
}
Assume that seq1, seq2, and the old value of result each have N elements. In terms of the number of ItemType objects visited (in the linked list nodes) during the execution of this function, what is its time complexity? Why?
b. Here is an implementation of a related member function. The call
s3.interleave(s1,s2);
sets s3 to the result of interleaving s1 and s2. The implementation is
void Sequence::interleave(const Sequence& seq1, const Sequence& seq2)
{
Sequence res;
Node* p1 = seq1.m_head-m_next;
Node* p2 = seq2.m_head-m_next;
for ( ; p1 != seq1.m_head && p2 != seq2.m_head;
p1 = p1-m_next, p2 = p2-m_next)
{
res.insertBefore(res.m_head, p1-m_value);
res.insertBefore(res.m_head, p2-m_value);
}
Node* p = (p1 != seq1.m_head ? p1 : p2);
Node* pend = (p1 != seq1.m_head ? seq1 : seq2).m_head; for ( ; p != pend; p = p-m_next)
res.insertBefore(res.m_head, p-value);
Swap *this with res swap(res);
Old value of *this (now in res) is destroyed when function returns.
}
Assume that seq1, seq2, and the old value of *this each have about N elements. In terms of the number of ItemType objects visited during the execution of this function, what is its time
complexity? Why? Is it the same, better, or worse, than the implementation in part a?
The file sorts.cpp contains an almost complete program that creates a randomly ordered array, sorts it in a few ways, and reports on the elapsed times. Your job is to complete it and experiment with it.
You can run the program as is to get some results for the STL sort algorithm. The insertion sort result will be meaningless (and you'll get an assertion violation), because the insertion sort function right now doesn't do anything. That's one thing for you to write.
The objects in the array are not cheap to copy, which makes a sort that does a lot of moving objects around expensive. Your other task will be to create a vector of pointers to the objects, sort the pointers using the same criterion as was used to sort the objects, and then make one pass through the vector to put the objects in the proper order.
Your two tasks are thus:
Implement the insertion_sort function.
Implement the compareStudentPtr function and the code in main to create and sort the array of pointers.
The places to make modifications are indicated by TODO: comments. You should not have to make modifications anywhere else. (Our solution doesn't.)
When your program is correct, build an optimized version of it to do some timing experiments. On the
SEASnet Linux servers, build the executable and run it this way:
/usr/local/cs/bin/g32fast -o sorts sorts.cpp
./sorts
(You don't have to know this, but this command omits some of the runtime error checking compiler options that our g32 command supplies, and it adds the -O2 compiler option that causes the compiler to spend more time optimizing the machine language translation of your code so that it will run faster when you execute it.)
Under Xcode, select Product / Scheme / Edit Scheme.... In the left panel, select Run, then in the right
panel, select the Info tab. In the Build Configuration dropdown, select Release. For Visual C++, it's a little trickier.
Try the program with about 10000 items. Depending on the speed of your processor, this number may be too large or small to get meaningful timings in a reasonable amount of time. Experiment. Once you get
insertion sort working, observe the O(N2) behavior by sorting, say, 10000, 20000, and 40000 items.
To further observe the performance behavior of the STL sort algorithm, try sorting, say, 100000, 200000, and 400000 items, or even ten times as many. Since this would make the insertion sort tests take a long time, skip them by setting the TEST_INSERTION_SORT constant at the top of sorts.cpp to false.
Notice that if you run the program more than once, you may not get exactly the same timings each time. This is not because you're not getting the same sequence of random numbers each time; you are. Instead, factors like caching by the operating system are the cause.
Turn it in
By Monday, March 6, there will be a link on the class webpage that will enable you to turn in this homework.
Turn in one zip file that contains your solutions to the homework problems. The zip file must contain four files:
Sequence.h, a C++ header file with your definition and implementation of the class and function templates for problem 1. For you to not get a score of zero for this problem, this test program that we will try with your header must build and execute successfully under both g32 and either Visual C++ or clang++:
#include "Sequence.h"
#include <iostream
#include <string
#include <cassert
using namespace std;
void test()
{
Sequence<int si;
Sequence<string ss;
assert(ss.empty());
assert(ss.size() == 0);
assert(ss.insert("Hello") == 0);
assert(si.insert(10) == 0);
assert(si.erase(0));
assert(ss.remove("Goodbye") == 0);
assert(ss.find("Hello") == 0);
string s;
assert(ss.get(0, s));
assert(ss.set(0, "Hello"));
Sequence<string ss2(ss);
ss2.swap(ss);
ss2 = ss;
assert(subsequence(ss,ss2) == 0);
assert(subsequence(si,si) == -1);
interleave(ss,ss2,ss);
interleave(si,si,si);
}
int main()
{
test();
cout << "Passed all tests" << endl;
}
hw.doc, hw.docx, or hw.txt, a Word document or a text file with your solutions to problems 2, 3b, 4a, 4b, 5a, and 5b.
list.cpp, a C++ source file with the implementation of the two-parameter overload of the listAll function for problem 3a.
sorts.cpp, a C++ source file with the your solution to problem 6.
