Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E4-2'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-2

Question

For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, S = 8, 19 − 3 maximizes the difference, while 8 − 6 minimizes the difference.
(a) Let S be an unsorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that maximizes |x−y|. Your algorithm must run in O(n) worst-case time.
(b) Let S be a sorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(1) worst-case time.
(c) Let S be an unsorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that minimizes |x − y|, for x ≠ y. Your algorithm must run in O(n log n) worst-case time.
(d) Let S be a sorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that minimizes |x − y|, for x ≠ y. Your algorithm must run in O(n) worst-case time.

Solution

Outline

(a) Go through whole array and trace the maximum and minimum value Finally calc the maximum of difference using traced two values

(b) (Ascendingly) sorted array has maximum value in its tail and minimum value in its head So we simply pick the values and calc the diff That can be applied for descendingly sorted array

(c) Normally sort the array using heapsort But at the same time trace the minimum difference every time examine_min_diff (equivalent to textbook's extract-min) routine is called, and update it if neccessary. Finally when sort is completed, all differences is checked and we simply return it.

(d) For already sorted array, we need no mutation and examine a diff between each adjacent pair, and return the smallest.

Code

(a)

// Go through whole array and trace the maximum and minimum value
// Finally calc the maximum of difference using traced two values

#include <algorithm>
#include <cassert>
#include <vector>
int find_max_diff(const std::vector<int>& v) {
    int max{v[0]}, min{v[0]};
    for (auto&& e : v) {
        max = std::max(max, e);
        min = std::min(min, e);
    }
    return max - min;
}

int main(int argc, char const* argv[]) {
    assert(find_max_diff({1, 3, -1, 5, 0, 9}) == 10);  // test
    return 0;
}

(b)

// (Ascendingly) sorted array has maximum value in its tail and minimum value in
//  its head
// So we simply pick the values and calc the diff
// That can be applied for descendingly sorted array

#include <algorithm>
#include <cassert>
#include <vector>

int find_max_diff(const std::vector<int>& sorted_v) {
    return std::abs(sorted_v.back() - sorted_v.front());
}

int main(int argc, char const* argv[]) {
    assert(find_max_diff({-4, -1, 1, 4, 7}) == 11);
    assert(find_max_diff({6, 3, 2, 1}) == 5);
    return 0;
}

(c)

// Normally sort the array using heapsort
// But at the same time trace the minimum difference every time examine_min_diff
//  (equivalent to textbook's extract-min) routine is called, and update it if
//  neccessary.
// Finally when sort is completed, all differences is checked and
//  we simply return it.

#include <algorithm>
#include <cassert>
#include <limits>
#include <stdexcept>
#include <vector>
size_t pq_parent(size_t i) { return i / 2; }
size_t pq_young_child(size_t i) { return i * 2; }
size_t pq_top() { return 1; }
size_t pq_len(size_t x) { return x - 1; }
void pq_swap(std::vector<int>& q, size_t i1, size_t i2) {
    auto t{q[i1]};
    q[i1] = q[i2];
    q[i2] = t;
}
void bubble_down(std::vector<int>& q, size_t p) {
    auto c{pq_young_child(p)};
    auto min_idx{p};
    for (size_t i = 0; i < 2; i++) {
        if (c + i <= pq_len(q.size()) && q[c + i] < q[min_idx]) min_idx = c + i;
    }
    if (min_idx == p) return;
    // swap
    pq_swap(q, p, min_idx);
    // recurse
    bubble_down(q, min_idx);
}
std::vector<int> make_heap(const std::vector<int>& v) {
    std::vector<int> q(v.size() + 1);
    std::copy(v.cbegin(), v.cend(), q.begin() + 1);

    for (size_t i = pq_len(q.size()) / 2; i >= 1; i--) {
        bubble_down(q, i);
    }
    return q;
}
int examine_min_diff(std::vector<int>& q) {
    if (pq_len(q.size()) <= 0) throw std::invalid_argument{"Empty queue"};
    if (pq_young_child(pq_top()) <= pq_len(q.size())) {
        auto dm{std::min(q[pq_young_child(pq_top())] - q[pq_top()],
                         q[pq_young_child(pq_top()) + 1] - q[pq_top()])};
        q[pq_top()] = q[pq_len(q.size())];
        q.resize(q.size() - 1);
        bubble_down(q, pq_top());
        return dm;
    } else {
        return std::numeric_limits<int>::max();
    }
}
int find_min_diff(const std::vector<int>& v) {
    std::vector<int> q{make_heap(v)};
    auto min_diff{std::numeric_limits<int>::max()};
    for (size_t i = 0; i < v.size() - 1; i++) {
        min_diff = std::min(min_diff, examine_min_diff(q));
    }
    return min_diff;
}
int main(int argc, char const* argv[]) {
    assert(find_min_diff({-4, -1, 1, 4, 7}) == 2);
    assert(find_min_diff({6, 3, 2, 1}) == 1);
    assert(find_min_diff({124, 63, 23, 78, 11, 52}) == 11);
    return 0;
}

(d)

// For already sorted array, we need no mutation and examine a diff between each
// adjacent pair, and return the smallest.

#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
int find_min_diff(const std::vector<int>& sorted_v) {
    auto min_diff{std::numeric_limits<int>::max()};
    for (size_t i = 0; i < sorted_v.size() - 1; i++) {
        min_diff = std::min(min_diff, sorted_v[i + 1] - sorted_v[i]);
    }
    return min_diff;
}
std::vector<int> sorted_array(const std::vector<int>& v) {
    std::vector<int> v2(v.cbegin(), v.cend());
    std::sort(v2.begin(), v2.end());
    return v2;
}
int main(int argc, char const* argv[]) {
    assert(find_min_diff(sorted_array({-4, -1, 1, 4, 7})) == 2);
    assert(find_min_diff(sorted_array({6, 3, 2, 1})) == 1);
    assert(find_min_diff(sorted_array({124, 63, 23, 78, 11, 52})) == 11);
    return 0;
}