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>
void sort(vector<int> & vec)
{ // bubble sort ascending
bool sorted = false;
while (!sorted)
{
void sortDec(vector<int> & vec)
int select1(vector<int> nums)
{
}
}
return topK[k-1];
}
int main()
{
vector<int> nums;
int selected;
time_t start, end;
2. /*
Word Puzzle problem
from the example in figure 1.1
*/
#include<iostream>
using namespace std;
const int MAXROWS = 4;
const int MAXCOLS = 4;
{
Orientation() : delRow(0), delCol(0) {}
Orientation operator() (int direction)
{
switch (direction)
{
case 0 : delRow = -1; delCol = -1; break;
140
160
180
};
class Puzzle
{
public:
Puzzle(int numRows, int numCols )
{
matrix<char> temp(numRows,numCols);
puzzle= temp;
initPuzzle();
void Puzzle::initPuzzle()
{
puzzle[0][0] = ‘t’;
puzzle[0][1] = ‘h’;
puzzle[0][2] = ‘i’;
puzzle[0][3] = ‘s’;
void Puzzle::solvePuzzle()
{
Orientation orient;
void Puzzle::findWords(int startRow, int startCol, Orientation orient)
int row = startRow;
int col = startCol;
do
{
word = word + puzzle[row][col];
if (find(dictionary.begin(), dictionary.end(), word) != dictionary.end())
}
int main()
{
string diction[] = {“this”, “two”, “fat”, “fats”, “at”, “wad”, “ad”, “hat”, “that”,
“his”,“is”,“it”,“ah”} ;
}
1.3
void printDouble(double x)
{
if (x < 0)
{
cout<<“-“;
x = –x;
}
int intPart = floor(x);
}
}
1.4
The general way to do this is to write a procedure with heading
void processFile( String fileName );
which opens fileName, does whatever processing is needed, and then closes it. If a line of the form
is detected, then the call
processFile( SomeFile );
1.5
int ones( int n )
{
1.6
void permute(const string & str, int low, int high)
{
char letter;
1.7 (a) The proof is by induction. The theorem is clearly true for 0 < X 1, since it is true for X = 1, and for X
< 1, log X is negative. It is also easy to see that the theorem holds for 1 < X 2, since it is true for X = 2,
(b)
Subtracting the first equation from the second gives
(d) Let SN =
4
0
.
N
i
i
i
=
Follow the same method as in parts (a) – (c) to obtain a formula for SN in terms of SN–1,
1.11 (a) Proof is by induction. The statement is clearly true for N = 1 and N = 2. Assume true for N = 1, 2, … ,
(b) As in the text, the proof is by induction. Observe that
+ 1 =
2. This implies that
–1 +
–2 = 1. For N =
1 and N = 2, the statement is true. Assume the claim is true for N = 1, 2, … , k.
(b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise,
13 3 3
11
( 1)
NN
ii
i N i
+
==
= + +

1.15
class EmployeeLastNameCompare
{
public:
1.16
matrix() : array(10)