Test Bank for Database Concepts, 9th Edition by David M. Kroenke, Chapters 1-7

Data Structures and Algorithm Analysis in C++, 4th edition




SOLUTIONS
ST
UV

Data Structures and
IA

Algorithm Analysis in
.A

C++, 4th edition
PP
RO

Authors:
Mark A. Weiss
VE

◊ ALL CHAPTERS

◊ INSTANT PDF DOWNLOAD💯💯💯
D?

◊ ORIGINAL FROM PUBLISHER
??

MEDCONNOISSEUR

, CHAPTER 1


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

#include <iostream>
#include <ctime>
#include <cmath>
IA
#include <vector>
#include <algorithm>
using namespace std;
.A
void sort(vector<int> & vec)
{ // bubble sort ascending
bool sorted = false;
PP
while (!sorted)
{
sorted = true;
for (auto i = 1; i < vec.size(); i++)
{
RO
if (vec[i-1]> vec[i])
{
swap(vec[i],vec[i-1]);
sorted = false;
}
}
VE
}
}

void sortDec(vector<int> & vec)
{ // bubble sort descending
bool sorted = false;
D?
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];
}
ST
int select2(const vector<int> &nums)
{
int k = nums.size()/2;
UV
vector<int> topK(nums.begin(), nums.begin() + k);

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

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

srand(time(NULL));
for (auto numInts = 1000; numInts<=10000; numInts+=1000)
VE
// 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
D?
{
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
ST
100
Time of Select1
80
Time of Select2
60
UV
40

20

0
IA
0 2000 4000 6000 8000 10000 12000


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

#include<iostream>
#include<fstream>
PP
#include<string>
#include<vector>
#include "matrix.h"
#include<algorithm>
RO
using namespace std;

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

struct Orientation
VE
{
Orientation() : delRow(0), delCol(0) {}
Orientation operator() (int direction)
{
switch (direction)
{
D?
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;