Solution Manual for Data Structures And Algorithm Analysis In C++ 4th Edition / All Chapters 1 - 12 / Full Complete 2023

Data Structures And Algorithm Analysis In C++ 4th Edition Solution Manual 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; } 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; 180 160 140 120 100 80 Time of Select1 Time of Select2 60 40 20 0 0 2000 4000 6000 8000 10000 12000 }; 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) { string word ="";