Some algorithmic quizzes

Many algorithmic puzzles are circulating around the net. Here i want to present some problems i came across and found interesting to solve (or not to solve).

Neither did i solve all the problems nor do i even know, if solutions exist for particular problems.

Partial shifts

Consider an array $a = a_0, a_1, \dots a_n$ . A k-shift (notation: $s_k$ ) is an operation that takes the k-th element and moves it to the first position. For example $s_3(0,1,2,3,4,5) = (3,0,1,2,4,5)$ .

The goal is to sort the array using only k-shifts. Give an polynomial-time algorithm that calculates the minimum number of shifts to sort the array, and the shifts itself.

Bonus: What is the expected number of moves?

Finding minimum / maximum

Given an array, that either consists of first ascending and then descending numbers (e.g. 0, 3, 5, 7, 9, 13, 7, 4, 2), of first descending and then ascending numbers (e.g. 10, 8, 3, 2, 5, 7, 9).

Give an efficient algorithm that computes the position of the maximum or minimum, respectively.

Finding palindromes

A palindrom is a sequence of signs that can be read from left to right and right to left without changing, that is: $p_1, p_2, \dots, p_{n-1}, p_n = p_n, p_{n-1}, \dots p_2, p_1$ .

Given an array of characters, find the longest palindromic subarray efficiently (that is: $O(n)$ ).

Stack sorting

Given a stack, sort its content using only:

recursion

a queue

Tree distances

Given a undirected, unweighted tree, give an preprocessing algorithm, so that all distances from node $u$ to node $v$ can be computed in $O(dist(u,v))$ .

This entry was posted on 11. July 2009 at 11:23 pm and is filed under Algorithms, Can you solve it?. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

phimuemue's Blog