What a great idea! Make sure to switch channel with up/down buttons!

# Category Archives: nh

# Skiena’s TADM Problem 7-19

From Skiena’s Algorithm Design Manual

**Problem 7-19**

Use a random number generator (rng04) that generates numbers from {0, 1, 2, 3, 4} with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability. What are expected number of calls to rng04 per call of rng07?

**Solution**

(no guarantee that the solution is good or even correct)

The basic idea is to represent the numbers 0..7 with three bits, where each bit is set randomly. To this end the rng04() is wrapped into a method rng03(), which trims its output to 0..3. Then, rng07() uses this output to set each of the three bits and return the random number in 0..7.

The code uses rng03() from the AlgoWiki.

Here is a Python 3 solution. Please leave comments if you find a mistake or an improvement.

#!/usr/bin/env python import sys, random # used for counting method calls. taken from # http://stackoverflow.com/questions/1301735/counting-python-method-calls-within-another-method def counted(fn): def wrapper(*args, **kwargs): wrapper.called+= 1 return fn(*args, **kwargs) wrapper.called= 0 wrapper.__name__= fn.__name__ return wrapper # RNG 0..4 (given) @counted def rng04(): return random.randint(0,4) # filtered call to rng04 # return 0..3 @counted def rng03(): while True: i = rng04() if i < 4: return i # generate uniform numbers in 0..7 # use rng03 to generate representations of the 3 bits for # numbers in the range 0..7 def rng07(): b3 = rng03() % 2 b2 = rng03() % 2 b1 = rng03() % 2 n = b3*4 + b2*2 + b1 return n if __name__ == "__main__": rands = [] n = 100000 for i in range(n): rands.append(rng07()) for i in range(8): print (str(i) + "'s: " + str(rands.count(i))) print ("Called rng04() " + str(rng04.called) + " times") print ("rng04()/rng03() call ratio: " + str(rng04.called/rng03.called)) print ("rng04()/rng07() call ratio: " + str(rng04.called/n)) sys.exit()

Each call to rng07() calls rng03() to set each of the three bits, which in turn calls rng04() 5/4 times to obtain a number in 0..3. Hence, rng04() is called 5/4*3 = 3.75 times in average on each call to rng07(). The solution on the AlgoWiki requires about one call less, the solution on panictank requires more.

# Skiena’s TADM Problem 7-15

From Skiena’s Algorithm Design Manual

**Problem 7-15**

Implement an efficient algorithm for listing all k-element subsets of n items.

**Solution**

(no guarantee that the solution is good or even correct)

This solution is based on Solution 7-1

Compile with -std=c++11 and please leave comments if you find a mistake or an improvement.

#include <iostream> #include <array> #define N 5 #define K 3 // Comment 1: some function parameters are unused but kept // to provide consistency with Skiena's book // By construction it is a solution if we reach the last element bool is_a_solution ( std::array<int, K>& arr, int k, int n ) { return k == n-1; } // processing = print it void process_solution ( std::array<int, K>& arr, int k, int n ) { for ( int i = 0; i != n; ++i ) printf ("%i ", arr[i]); printf ( "\n" ); } void construct_candidates ( std::array<int, k="">& arr, int k, int n, std::array<int, n="">& cands, int& ncandidates ) { ncandidates = 0; if ( k == 0 ) { for ( int i=0; i != N; ++i ) cands[ncandidates++] = i; } else { // all numbers greater than the currently greatest are candidates for ( int i = arr[k-1]+1; i != N; ++i ) cands[ncandidates++] = i; } } void backtrack ( std::array<int, K>& arr, int k, int n ) { std::array<int, n=""> cands = {0}; int ncandidates; if ( is_a_solution ( arr, k, n )) process_solution ( arr, k, n ); else { k = k+1; construct_candidates ( arr, k, n, cands, ncandidates ); // pruning condition if ( ncandidates < K-k ) return; for (int i=0; i<ncandidates; i++) { arr[k] = cands[i]; backtrack ( arr, k, n ); } } } int main () { std::array<int, K> arr = {0}; int k = -1; backtrack ( arr, k, K ); return 0; }

# Skiena’s TADM Problem 7-1

**Problem 7-1**

A derangement is a permutation \(p\) of \(\{1,…,n\}\) such that no item is in its proper position, i.e. \(p \not= i\,\, \forall\,\, 1 \le i \le n\). Write an efficient backtracking program with pruning that constructs all the derangements of n items.

**Solution**

(no guarantee that the solution is good or even correct)

Compile with -std=c++11 and please leave comments if you find a mistake or an improvement.

#include <iostream> #include <array> #define N 10 // Comment 1: some function parameters are unused but kept // to provide consistency with Skiena's book // Comment 2: there is no pruning because the candidate lists // are constructed to contain only possible numbers // By construction it is a solution if we reach the last element bool is_a_solution ( std::array<int, N>& arr, int k, int n ) { return k == n-1; } // processing = print it void process_solution ( std::array<int, N>& arr, int k, int n ) { for ( int i = 0; i != n; ++i ) printf ("%i ", arr[i]); printf ( "\n" ); } void construct_candidates ( std::array<int, N>& arr, int k, int n, std::array<int, N>& cands, int& ncandidates ) { ncandidates = 0; // generate a full list of candidates int candlist[N]; for ( int i = 0; i != n; ++i ) candlist[i] = i; // remove those that are in the array already and the one in position k for ( int i = 0; i != k; ++i ) candlist[arr[i]] = -1; candlist[k] = -1; // the rest are candidates for ( int i = 0; i != n; ++i ) if ( candlist[i] != -1 ) cands[ncandidates++] = candlist[i]; } void backtrack ( std::array<int, N>& arr, int k, int n ) { std::array<int, N> cands = {0}; int ncandidates; if ( is_a_solution ( arr, k, n )) process_solution ( arr, k, n ); else { k = k+1; construct_candidates ( arr, k, n, cands, ncandidates ); for (int i=0; i<ncandidates; i++) { arr[k] = cands[i]; backtrack ( arr, k, n ); } } } int main () { std::array<int, N> arr = {-1}; int k = -1; backtrack ( arr, k, N ); return 0; }

# Create sorted 1D array from sorted 2D array

**Problem:**

Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?

**Solution:**

A possible solution utilizes a propagating front separating the elements that have already been sorted into the 1D array from those that are still pending. The solution is \(\mathcal{O}(N)\) in space because of the storage required for the front and \(\mathcal{O}(N^3)\) in time as the insertion of each of the \(N^2\) numbers requires a comparison of the N front values (at most).

The algorithm generalizes to sorting \(D\)-dimensional arrays, in which case the front has dimension \(D-1\).

Compile with -std=c++11 and please leave comments if you find a mistake or an improvement.

#include <iostream> #include <limits> using namespace std; // typedef double arraytype; typedef int arraytype; #define N 4 // example with a 4x4 matrix const arraytype mat[N][N] = {{1,2,4,5},{2,3,5,7},{4,6,12,13},{5,20,21,22}}; // sorted 2D array int main () { arraytype arr[N*N] = {0}; // initialize the array to zero unsigned int front[N] = {0}; // use a front that contains the first number to consider for each column, i.e., // the first number in each column that has not be sorted in the 1D array yet for ( unsigned int n = 0; n != N*N; ++n ) { // loop the 1D array arraytype m = numeric_limits<arraytype>::max(); // init smallest element found to max unsigned int f = 0; // variable for updating the front in one column for ( unsigned int col = 0; col != N; ++col ) { // walk the 2D array by columns if ( front[col] == N ) continue; // if the front hits row N in column col go to next column if ( (col > 0) && (front[col] == 0) && (front[col-1] == 0) ) break; // optimization: stop the current column iteration if the front in column col and col-1 is at row 0 (and col > 0) if ( m > mat[front[col]][col] ) { // check 2D array for value smaller than m m = mat[front[col]][col]; // update m f = col; // set f for updating front but don't update front yet because another smaller value might be found } } arr[n] = m; // set value in 1D array front[f]++; // update front } for ( auto& i : arr ) // print sorted 1D array cout << i << " "; cout << endl; return 0; }

Solutions with complexity of \(\mathcal{O}(N^2)\log(N)\) are achieved by maintaining the front values in a priority queue. This is the same as the merge step of mergesort.

Simply adding all values of the 2D array into a min heap and extracting them of the top is also \(\mathcal{O}(N^2)\log(N)\) (as \(\mathcal{O}(N^2)\log(N^2) = \mathcal{O}(N^2)2\log(N) = \mathcal{O}(N^2)\log(N)\)). Adding the values to the heap following diagonals from the largest number (bottom right) to the smallest number (top left) will reduce the bubble down time.

# Atoms For Peace – Ingenue

Who says you need to spend a lot of money for a great music video?

The opposite demonstrated to perfection by the Ingenue video of Atoms for Peace (Thom Yorke of Radiohead‘s new side project).

# Online Petition “Mehr Bahnradsport live”

Mehr Information hier.