| Problem 1 | Problem 5 |
| Problem 2 | Problem 6 |
| Problem 3 | Problem 7 |
| Problem 4 |
void removeOdd(list<int>& li)
{
list<int>::iterator p = li.begin();
while (p != li.end())
{
if (*p % 2 != 0)
p = li.erase(p);
else
p++;
}
}
void removeOdd(vector<int>& v)
{
vector<int>::iterator p = v.begin();
while (p != v.end())
{
if (*p % 2 != 0)
p = v.erase(p);
else
p++;
}
}
void removeBad(list<Movie*>& li)
{
list<Movie*>::iterator p = li.begin();
while (p != li.end())
{
if ((*p)->rating() < 50)
{
delete *p; // *p is a Movie*; delete the Movie that *p points to
p = li.erase(p);
}
else
p++;
}
}
void removeBad(vector<Movie*>& v)
{
vector<Movie*>::iterator p = v.begin();
while (p != v.end())
{
if ((*p)->rating() < 50)
{
delete *p; // *p is a Movie*; delete the Movie that *p points to
p = v.erase(p);
}
else
p++;
}
}
// Map.h
#ifndef MAP_INCLUDED
#define MAP_INCLUDED
template<typename KeyType, typename ValueType>
class Map
{
public:
Map(); // Create an empty map (i.e., one whose size() is 0).
bool empty() const; // Return true if the map is empty, otherwise false.
int size() const; // Return the number of key/value pairs in the map.
bool insert(const KeyType& key, const ValueType& value);
// If key is not equal to any key currently in the map and if the
// key/value pair can be added to the map, then do so and return true.
// Otherwise, make no change to the map and return false (indicating
// that either the key is already in the map, or the map has a fixed
// capacity and is full).
bool update(const KeyType& key, const ValueType& value);
// If key is equal to a key currently in the map, then make that key no
// longer map to the value that it currently maps to, but instead map to
// the value of the second parameter; in this case, return true.
// Otherwise, make no change to the map and return false.
bool insertOrUpdate(const KeyType& key, const ValueType& value);
// If key is equal to a key currently in the map, then make that key no
// longer map to the value that it currently maps to, but instead map to
// the value of the second parameter; in this case, return true.
// If key is not equal to any key that is currently in the map, and if the
// key/value pair can be added to the map, then do so and return true.
// Otherwise, make no change to the map and return false (indicating
// that the key is not already in the map and the map has a fixed
// capacity and is full).
bool erase(const KeyType& key);
// If key is equal to a key currently in the map, remove the key/value
// pair with that key from the map and return true. Otherwise, make
// no change to the map and return false.
bool contains(const KeyType& key) const;
// Return true if key is equal to a key currently in the map, otherwise
// false.
bool get(const KeyType& key, ValueType& value) const;
// If key is equal to a key currently in the map, set value to the
// value in the map that the key maps to, and return true. Otherwise,
// make no change to the value parameter of this function and return
// false.
bool get(int i, KeyType& key, ValueType& value) const;
// If 0 <= i < size(), copy into the key and value parameters the
// key and value of the key/value pair in the map whose key is strictly
// greater than exactly i keys in the map and return true. Otherwise,
// leave the key and value parameters unchanged and return false.
void swap(Map<KeyType, ValueType>& other);
// Exchange the contents of this map with the other one.
// Housekeeping functions
~Map();
Map(const Map<KeyType, ValueType>& other);
Map<KeyType, ValueType>& operator=(const Map<KeyType, ValueType>& rhs);
private:
// Representation:
// a circular doubly-linked list with a dummy node.
// m_head points to the dummy node.
// m_head->m_prev->m_next == m_head and m_head->m_next->m_prev == m_head
// m_size == 0 iff m_head->m_next == m_head->m_prev == m_head
// If m_size > 0
// m_head->next points to the node at position 0.
// m_head->prev points to the node at position m_size-1.
// Nodes are in strictly ascending order of keys.
struct Node
{
KeyType m_key;
ValueType m_value;
Node* m_next;
Node* m_prev;
};
Node* m_head;
int m_size;
Node* findFirstAtLeast(const KeyType& key) const;
// Return a pointer to the node in the list whose key is the least one
// that is >= key, or m_head if there is no such pair.
bool doInsertOrUpdate(const KeyType& key, const ValueType& value,
bool mayInsert, bool mayUpdate);
// If the key is not present in the map and if mayInsert is true, insert
// the pair if there is room. If the key is present and mayUpdate is
// true, update the pair with the given key.
};
// Declarations of non-member functions
template<typename KeyType, typename ValueType>
bool merge(const Map<KeyType, ValueType>& m1, const Map<KeyType, ValueType>& m2, Map<KeyType, ValueType>& result);
// If a key/value pair occurs in m1 or m2 or both, then it will occur in
// result upon return from this function. Return true unless m1 and m2
// have a pair with the same key but different values; neither such pair
// will occur in result upon return.
template<typename KeyType, typename ValueType>
void reassign(const Map<KeyType, ValueType>& m, Map<KeyType, ValueType>& result);
// Upon return, result contains for each pair p in m, a pair with p's
// key and the value from a different pair in m.
// Inline implementations
template<typename KeyType, typename ValueType>
inline
int Map<KeyType, ValueType>::size() const
{
return m_size;
}
template<typename KeyType, typename ValueType>
inline
bool Map<KeyType, ValueType>::empty() const
{
return size() == 0;
}
template<typename KeyType, typename ValueType>
inline
bool Map<KeyType, ValueType>::contains(const KeyType& key) const
{
Node* p = findFirstAtLeast(key);
return p != m_head && p->m_key == key;
}
template<typename KeyType, typename ValueType>
inline
bool Map<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value)
{
return doInsertOrUpdate(key, value, true /* insert */, false /* no update */);
}
template<typename KeyType, typename ValueType>
inline
bool Map<KeyType, ValueType>::update(const KeyType& key, const ValueType& value)
{
return doInsertOrUpdate(key, value, false /* no insert */, true /* update */);
}
template<typename KeyType, typename ValueType>
inline
bool Map<KeyType, ValueType>::insertOrUpdate(const KeyType& key, const ValueType& value)
{
return doInsertOrUpdate(key, value, true /* insert */, true /* update */);
}
// Non-inline implementations
template<typename KeyType, typename ValueType>
Map<KeyType, ValueType>::Map()
: m_size(0)
{
// create dummy node
m_head = new Node;
m_head->m_next = m_head;
m_head->m_prev = m_head;
}
template<typename KeyType, typename ValueType>
Map<KeyType, ValueType>::~Map()
{
// Delete the m_size non-dummy nodes plus the dummy node
for (Node* p = m_head->m_prev ; m_size >= 0; m_size--)
{
Node* toBeDeleted = p;
p = p->m_prev;
delete toBeDeleted;
}
}
template<typename KeyType, typename ValueType>
Map<KeyType, ValueType>::Map(const Map<KeyType, ValueType>& other)
: m_size(other.m_size)
{
// Create dummy node; don't initialize its pointers
m_head = new Node;
// Initialize prev to last node created
Node* prev = m_head;
// Copy each non-dummy node from the other list; each iteration will set
// the m_next of the previous node copied
for (Node* p = other.m_head->m_next ; p != other.m_head; p = p->m_next)
{
// Create a copy of the node p points to
Node* pnew = new Node;
pnew->m_key = p->m_key;
pnew->m_value = p->m_value;
// Connect the new node to the previous one
pnew->m_prev = prev;
prev->m_next = pnew;
// Reset prev to last node created
prev = pnew;
}
// Connect last node created to m_head
m_head->m_prev = prev;
prev->m_next = m_head;
}
template<typename KeyType, typename ValueType>
Map<KeyType, ValueType>& Map<KeyType, ValueType>::operator=(const Map<KeyType, ValueType>& rhs)
{
if (this != &rhs)
{
Map<KeyType, ValueType> temp(rhs);
swap(temp);
}
return *this;
}
template<typename KeyType, typename ValueType>
bool Map<KeyType, ValueType>::erase(const KeyType& key)
{
Node* p = findFirstAtLeast(key);
if (p == m_head || p->m_key != key) // not found
return false;
// unlink the node from the list and destroy it
p->m_prev->m_next = p->m_next;
p->m_next->m_prev = p->m_prev;
delete p;
m_size--;
return true;
}
template<typename KeyType, typename ValueType>
bool Map<KeyType, ValueType>::get(const KeyType& key, ValueType& value) const
{
Node* p = findFirstAtLeast(key);
if (p == m_head || p->m_key != key) // not found
return false;
value = p->m_value;
return true;
}
template<typename KeyType, typename ValueType>
bool Map<KeyType, ValueType>::get(int i, KeyType& key, ValueType& value) const
{
if (i < 0 || i >= m_size)
return false;
// If i is closer to the head of the list, go forward to reach that
// position; otherwise, start from tail and go backward.
Node* p;
if (i < m_size / 2) // closer to head
{
p = m_head->m_next;
for (int k = 0; k != i; k++)
p = p->m_next;
}
else // closer to tail
{
p = m_head->m_prev;
for (int k = m_size-1; k != i; k--)
p = p->m_prev;
}
key = p->m_key;
value = p->m_value;
return true;
}
template<typename KeyType, typename ValueType>
void Map<KeyType, ValueType>::swap(Map<KeyType, ValueType>& other)
{
// swap head pointers
Node* tempHead = m_head;
m_head = other.m_head;
other.m_head = tempHead;
// swap sizes
int t = m_size;
m_size = other.m_size;
other.m_size = t;
}
template<typename KeyType, typename ValueType>
typename Map<KeyType, ValueType>::Node* Map<KeyType, ValueType>::findFirstAtLeast(const KeyType& key) const
{
// Do a linear search through the list
Node* p;
for (p = m_head->m_next; p != m_head && p->m_key < key; p = p->m_next)
;
return p;
}
template<typename KeyType, typename ValueType>
bool Map<KeyType, ValueType>::doInsertOrUpdate(const KeyType& key, const ValueType& value,
bool mayInsert, bool mayUpdate)
{
Node* p = findFirstAtLeast(key);
if (p != m_head && p->m_key == key) // found
{
if (mayUpdate)
p->m_value = value;
return mayUpdate;
}
if (!mayInsert) // not found, and not allowed to insert
return false;
// Create a new node
Node* newp = new Node;
newp->m_key = key;
newp->m_value = value;
// Insert new node before p, which points to the node with the
// least key > newp's key
// Connect it to p's predecessor
newp->m_prev = p->m_prev;
newp->m_prev->m_next = newp;
// Connect it to p
newp->m_next = p;
p->m_prev = newp;
m_size++;
return true;
}
template<typename KeyType, typename ValueType>
bool merge(const Map<KeyType, ValueType>& m1, const Map<KeyType, ValueType>& m2, Map<KeyType, ValueType>& result)
{
// For better performance, the bigger map should be the basis for
// the result, and we should iterate over the elements of the
// smaller one, adjusting the result as required.
const Map<KeyType, ValueType>* bigger;
const Map<KeyType, ValueType>* smaller;
if (m1.size() >= m2.size())
{
bigger = &m1;
smaller = &m2;
}
else
{
bigger = &m2;
smaller = &m1;
}
// Guard against the case that result is an alias for m1 or m2
// (i.e., that result is a reference to the same map that m1 or m2
// refers to) by building the answer in a local variable res. When
// done, swap res with result; the old value of result (now in res) will
// be destroyed when res is destroyed.
bool status = true;
Map<KeyType, ValueType> res(*bigger); // res starts as a copy of the bigger map
for (int n = 0; n < smaller->size(); n++) // for each pair in smaller
{
KeyType k;
ValueType vsmall;
smaller->get(n, k, vsmall);
ValueType vbig;
if (!res.get(k, vbig)) // key in smaller doesn't appear in bigger
res.insert(k, vsmall); // so add it to res
else if (vbig != vsmall) // same key, different value
{ // so pair shouldn't be in res
res.erase(k);
status = false;
}
}
result.swap(res);
return status;
}
template<typename KeyType, typename ValueType>
void reassign(const Map<KeyType, ValueType>& m, Map<KeyType, ValueType>& result)
{
// Guard against the case that result is an alias for m (i.e., that
// result is a reference to the same map that m refers to) by building
// the answer in a local variable res. When done, swap res with result;
// the old value of result (now in res) will be destroyed when res is
// destroyed.
Map<KeyType, ValueType> res;
if (!m.empty())
{
KeyType prevKey;
ValueType value0;
// Get pair 0, which must succeed since m is not empty
m.get(0, prevKey, value0);
// For each pair i after pair 0, insert into res a pair with
// pair i-1's key and pair i's value. (This loop executes 0 times
// if m has only one pair.)
for (int i = 1; i < m.size(); i++)
{
KeyType k;
ValueType v;
m.get(i, k, v);
res.insert(prevKey, v);
prevKey = k;
}
// Insert a final pair with last pair's key and pair 0's value.
res.insert(prevKey, value0);
}
result.swap(res);
}
#endif // MAP_INCLUDED
You could alternatively have implemented the member functions inside the class declaration:
template<typename KeyType, typename ValueType>
class Map
{
...
int size() const
{
return m_size;
}
...
};
Since for this problem you were already starting with a lot of code written with the implementations outside the class declaration, it was less work to leave their implementations outside.
The instantiation of Map<Coord, int>::insert calls the
instantiation of Map<Coord, int>::doInsertOrUpdate, which calls
the instantiation of Map<Coord, int>::findFirstAtLeast, which
contains the expression p->m_key < key, where both operands are
Coord. Also Map<Coord, int>::doInsertOrUpdate
contains the expression p->m_key == key, where both operands are
Coord. We never defined operator< or
operator== for Coord operands (nor should we for
operator<, since coordinates don't have a natural ordering).
void listAll(const Domain* d, string path)
{
if (d->subdomains().empty())
{
cout << path << endl;
return;
}
if (path != "")
path = '.' + path;
for (size_t k = 0; k < d->subdomains().size(); k++)
listAll(d->subdomains()[k], d->subdomains()[k]->label() + path);
}
Other ways to write the for loop are
for (vector<Domain*>::const_iterator p = d->subdomains().begin();
p != d->subdomains().end(); p++)
listAll(*p, (*p)->label() + path);
or (in C++11 or later)
for (Domain* subdomain : d->subdomains()) // or for (auto subdomain : d->subdomains())
listAll(subdomain, subdomain->label() + path);
Without any static or global variables or any additional containers, there would be no way to keep track of the path from the root to each node of the tree.
Consider the code in the k loop:
for (int k = 0; k < N; k++)
{
if (k == i || k == j)
continue;
if (hasContacted[i][k] && hasContacted[k][j])
numIntermediaries[i][j]++;
}
This involves one initialization (int k = 0), which we can ignore, since it's dominated by the N repetitions of everything else. The most work that each of the N iterations of the loop might do is a comparison (k < N), an increment (k++), two equality tests (k == i and k == j), an or test (||), an and test (&&) an increment (++), and 3 double subscriptings. These basic operations are each constant time, so the number of operations performed during one execution of the innermost loop body is bounded by some constant m.
For the rest of this analysis, we won't be so meticulous: we'll drop low order terms where it won't affect the result.
That innermost loop body obviously accounts for most of the operations of the whole algorithm, since it's executed the most and the rest of the algorithm has only basic operations. In all, that body accounts for sum(i from 0 to N-1) of sum(j from 0 to N-1) of sum(k from 0 to N-1) of m operations.
sum(i from 0 to N-1) of {sum(j from 0 to N-1) of [sum(k from 0 to N-1) of m]} ~
m * sum(i from 0 to N-1) of {sum(j from 0 to N-1) of [sum(k from 0 to N-1) of 1]} ~
m * sum(i from 0 to N-1) of {sum(j from 0 to N-1) of N} ~
m * sum(i from 0 to N-1) of N*N ~
m * N*N*N = O(N3)
Again, the innermost statement accounts for the most operations performed, and it accounts for sum(i from 0 to N-1) of sum(j from 0 to i-1) of sum(k from 0 to N-1) of m operations. We'll retain the constant of proportionality just to get a feel for how much faster this can be. (We assume m is about the same as Part a.)
sum(i from 0 to N-1) of {sum(j from 0 to i-1) of [sum(k from 0 to N-1) of m]} ~
m * sum(i from 0 to N-1) of {sum(j from 0 to i-1) of [sum(k from 0 to N-1) of 1]} ~
m * sum(i from 0 to N-1) of {sum(j from 0 to i-1) of N} ~
m * sum(i from 0 to N-1) of i*N} ~
m * N * sum(i from 0 to N-1) of i} ~
m * N * ((N-1) * N / 2)
Since ((N-1) * N / 2) ~ N*N/2, the full sum is about (m/2) * N*N*N = O(N3). For large N, this algorithm is about twice as fast as the one in Part a, but it's still order N3; doubling the size of a problem increases the running time about eightfold.
First, notice that our implementation of the three-argument form of
get takes a length of time proportional to the distance
between the desired position and the nearest end of the list.
For position k in a list of size N, this is min(k, N-k).
Also, insert calls doInsertOrUpdate, which calls
findFirstAtLeast, which can visit up to N nodes.
The size function is constant time, as is the final swap.
Now let's examine the loop.
The statements in the loop are executed N times. Each time, the call to
get function visits min(k,N-k) nodes (which is bounded by N),
and the insert visits up to N nodes. Thus, each loop
iteration visit up to 2N nodes, which is O(N). Since the loop visits O(N)
nodes on each of the N iterations, the loop overall visits
O(N2) nodes. This dominates the O(N) and O(1) parts of the
function, so the overall time complexity is O(N2).
reassign is O(N).
Changes to the program as given are bold.
…
inline
bool compareStudentPtr(const Student* lhs, const Student* rhs)
{
return compareStudent(*lhs, *rhs);
}
…
void insertion_sort(vector<Student>& s, bool comp(const Student&, const Student&))
{
for (size_t k = 1; k < s.size(); k++)
{
Student currentStudent(s[k]);
size_t m = k;
for ( ; m > 0 && comp(currentStudent, s[m-1]); m--)
s[m] = s[m-1];
s[m] = currentStudent;
}
}
…
// Create an auxiliary copy of students, to faciliate the later reordering.
vector<Student> auxStudents(students.begin(), students.end());
// Create a vector of Student pointers, and set each pointer
// to point to the corresponding Student in auxStudents.
vector<Student*> studentPtrs;
for (size_t k = 0; k < auxStudents.size(); k++)
studentPtrs.push_back(&auxStudents[k]);
// Sort the vector of pointers using the STL sort algorithm
// with the comp parameter as the ordering relationship.
sort(studentPtrs.begin(), studentPtrs.end(), comp);
// Using the now-sorted vector of pointers, replace each Student
// in students with the Students from auxStudents in the correct order.
for (size_t k = 0; k < studentPtrs.size(); k++)
students[k] = *studentPtrs[k];
// auxStudents will be destroyed upon return from the function
…