Data Structures and Algorithm Analysis in C++, Weiss - Downloadable Solutions Manual (Revised)

CHAPTER 1


Introduction
1.1
/*
Exercise 1.1
Selection of integers with k = N/2
select1 => sorting and selecting
select2 => keeping top k
*/

#include <iostream>
#include <ctime>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;



void sort(vector<int> & vec)
{ // bubble sort ascending
bool sorted = false;
while (!sorted)
{
sorted = true;
for (auto i = 1; i < vec.size(); i++)
{
if (vec[i-1]> vec[i])
{
swap(vec[i],vec[i-1]);
sorted = false;
}
}
}
}

void sortDec(vector<int> & vec)
{ // bubble sort descending
bool sorted = false;
while (!sorted)
{
sorted = true;
for (auto i = 1; i < vec.size(); i++)
{
if (vec[i-1]< vec[i])
{
swap(vec[i],vec[i-1]);
sorted = false;
}
}
}
}

, int select1(vector<int> nums)
{
int k = (nums.size()+1)/2;
sort(nums);
return nums[k];
}


int select2(const vector<int> &nums)
{
int k = nums.size()/2;
vector<int> topK(nums.begin(), nums.begin() + k);

sortDec(topK);
for (auto i = k; i < nums.size(); i++)
{
if (nums[i] > topK[k-1])
{
for (auto j = k-2; j >=0 ; j--)
if (nums[i] < topK[j])
{topK[j+1] = nums[i]; break;}
else
topK[j+1] = topK[j];
if (topK[0] < nums[i])
topK[0] = nums[i];
}
}
return topK[k-1];
}

int main()
{
vector<int> nums;
int selected;
time_t start, end;

srand(time(NULL));
for (auto numInts = 1000; numInts<=10000; numInts+=1000)
// sizes 1,000, 2,000, 3,000, ...10,000
{
nums.resize(numInts);

start = time(NULL);
for (auto i = 0; i < 10; i++) // run 10 times
{
for (auto j = 0; j < numInts; j++)
nums[j] = rand()%(2*numInts);
selected = select1(nums); // or selected = select2(nums);
}
end = time(NULL);
cout<<numInts<<"\t"<<difftime(end,start)<<endl;
}
return 0;
}

, 180

160

140

120

100
Time of Select1
80
Time of Select2
60

40

20

0
0 5000 10000 15000


2. /*
Word Puzzle problem
from the example in figure 1.1
*/

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include "matrix.h"
#include<algorithm>

using namespace std;

const int MAXROWS = 4;
const int MAXCOLS = 4;

struct Orientation
{
Orientation() : delRow(0), delCol(0) {}
Orientation operator() (int direction)
{
switch (direction)
{
case 0 : delRow = -1; delCol = -1; break;
case 1 : delRow = -1; delCol = 0; break;
case 2 : delRow = -1; delCol = 1; break;
case 3 : delRow = 0; delCol = -1; break;
case 4 : delRow = 0; delCol = 1; break;
case 5 : delRow = 1; delCol = -1; break;
case 6 : delRow = 1; delCol = 0; break;
case 7 : delRow = 1; delCol = 1; break;
}
return *this;
}
int delRow;
int delCol;

, };

class Puzzle
{
public:
Puzzle(int numRows, int numCols )
{
matrix<char> temp(numRows,numCols);
puzzle= temp;
initPuzzle();
}
Puzzle(int numRows , int numCols , vector<string> wordList) :
dictionary(wordList)
{
matrix<char> temp(numRows,numCols);
puzzle= temp;
initPuzzle();
}
void solvePuzzle();
void findWords(int startRow, int startCol, Orientation orient);
private:
void initPuzzle();
matrix<char> puzzle;
vector<string> dictionary;
};

void Puzzle::initPuzzle()
{
puzzle[0][0] = 't';
puzzle[0][1] = 'h';
puzzle[0][2] = 'i';
puzzle[0][3] = 's';
puzzle[1][0] = 'w';
puzzle[1][1] = 'a';
puzzle[1][2] = 't';
puzzle[1][3] = 's';
puzzle[2][0] = 'o';
puzzle[2][1] = 'a';
puzzle[2][2] = 'h';
puzzle[2][3] = 'g';
puzzle[3][0] = 'f';
puzzle[3][1] = 'g';
puzzle[3][2] = 'd';
puzzle[3][3] = 't';
}

void Puzzle::solvePuzzle()
{
Orientation orient;
for ( auto startRow = 0; startRow < puzzle.numrows(); startRow++)
for ( auto startCol=0; startCol < puzzle.numcols(); startCol++)
for (auto i = 0; i < 8 ; i++)
findWords(startRow,startCol,orient(i));
}


void Puzzle::findWords(int startRow, int startCol, Orientation orient)
{