Chapter 1: Introduction

Exercise 1.1

Suppose you have a group of n numbers and would like to determine the
_k_th largest.
Write a program to solve the selection problem. Let k = n/2.

Algorithm-1

//Exercise 1.1 :
//Write a program to solve the selection problem. Let k = n/2. 
//Draw a table showing the running time of your program for various values of n.
#include<iostream>
#include<ctime>
#include<fstream>
#include<random>
using namespace std;
int arr[100010];
void BubleSort(int arr[], int length)
{
    for (int i = length - 1; i != 0; --i) {       //sort in decreasing order
        for (int j = 0; j != i; ++j) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main()
{
    ifstream in("test.txt");
    ofstream out("test.txt");
    uniform_int_distribution<unsigned> u(0, 200000);
    default_random_engine e;
    for (size_t i = 0; i < 100000; ++i) {
        out << u(e) << " ";          //write random unsigned integer into the file
    }
    int N, num;
    cin >> N;      //determine the number of elements to test
    int k = N / 2;
    clock_t t;      //timing
    t = clock();
    for (int i = 0; i != N; ++i) {
        in >> num;              //read random unsigned interger from the file
        arr[i] = num;
    }
    BubleSort(arr, N);
    cout << arr[k - 1] << endl;
    t = clock() - t;
    cout << "It took " << static_cast<float>(t) / CLOCKS_PER_SEC << " seconds" << endl;    //output the running time 
    return 0;
}

Algorithm-2

//Exercise 1.1 :
//Write a program to solve the selection problem. Let k = n/2. 
//Draw a table showing the running time of your program for various values of n.
#include<iostream>
#include<ctime>
#include<fstream>
#include<random>
using namespace std;
int arr[100010];
void BubleSort(int arr[], int length)
{
    for (int i = length - 1; i != 0; --i) {       //sort in decreasing order
        for (int j = 0; j != i; ++j) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main()
{
    ifstream in("test.txt");
    ofstream out("test.txt");
    uniform_int_distribution<unsigned> u(0, 200000);
    default_random_engine e;
    for (size_t i = 0; i < 100000; ++i) {
        out << u(e) << " ";               //write random unsigned integer into the file
    } 
    int N, num; 
    cin >> N;         //determine the number of elements to test
    int k = N / 2; 
    clock_t t;      //timing
    t = clock(); 
    for (int i = 0; i != k; ++i) {
        in >> num;
        arr[i] = num;
    }
    BubleSort(arr, k);
    int temp = k;
    while (temp--) {
        in >> num;
        if (num <= arr[k - 1])    continue;
        else {
            for (int i = k - 2; i >= 0; --i) {
                if (arr[i] >= num) {
                    for(int j = k - 1;j != i + 1;--j) {
                        arr[j] = arr[j - 1];
                    }
                    arr[i + 1] = num;
                    break;
                }
            }
        }
    }
    cout << arr[k - 1] << endl;
    t = clock() - t;
    cout << "It took " << static_cast<float>(t) / CLOCKS_PER_SEC << " seconds" << endl;    //output the running time 
    return 0;
}

Exercise 1.2

Algorithm

//Exercise 1.2 :
//Write a program to solve the word puzzle problem.
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int change_x[8] = { 1,1,0,-1,-1,-1,0,1 };      //change x,y location
int change_y[8] = { 0,1,1,1,0,-1,-1,-1 };
vector<vector<char>> list;  //letter list
vector<string> dict;    //dictionary
int main()
{
    int dict_n, table_n;
    string word;
    char letter;
    cin >> dict_n;   //input the number of words in dictionary
    while (dict_n--) {
        cin >> word;
        dict.push_back(word);
    }
    cin >> table_n;    //input the dimension of letter list
    list.resize(table_n);     
    for (int i = 0; i != table_n; ++i) {
        for (int j = 0; j != table_n; ++j) {
            cin >> letter;
            list[i].push_back(letter);
        }
    }
    for (int i = 0; i != table_n; ++i) {  //traverse the letter list
        for (int j = 0; j != table_n; ++j) {
            for (int k = 0; k != 8; ++k) {  //traverse the change_x/change_y array
                string s;
                int x = i;
                int y = j;
                for (int l = 0; l != table_n; ++l) {   //deep search until out of range->break 
                    s += list[x][y];
                    x += change_x[k];
                    y += change_y[k];
                    if (find(dict.cbegin(), dict.cend(), s) != dict.cend())  
                        cout << s << endl;
                    if (x < 0 || x >= table_n || y < 0 || y >= table_n)    break;  
                }
            }
        }
    }
    return 0;
}