# Programming Problems 13

March 26, 2010 Leave a comment

Here is another set of problems, these are not just a piece of cake 🙂

1. [From CLRS] You are given an array of integers where different integers may have different number of digits, but the total number of digits over all the integers in the array is n. Give an algorithm to sort the array in O(n) time.

2. [From CLRS] Give an algorithm to sort n integers in the range 0 to n^2 – 1 in O(n) time.

3. Suppose we are given a collection A = {a1, a2, ….., an } of n positive integers that add upto N. Design an O(nN)-time algorithm to determine whether there is a subset B ⊂ A, such that the sum of the elements in the set B is equal to the sum of the elements in the set A-B.

4. [Code this one to trust your algorithm :)]Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, l3, ……,ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If given line contains words i through j, where i ≤ j, and we leave exactly one space between words, the number of extra space characters at the end of the line is M – j + i – Σj{k=i} lk, which must be non-negative so that words fit on a line. We wish to minimize the sum, over all lines except the last, of the numbers of extra space characters at the ends of the lines. Design an algorithm to print a paragraph of n words neatly on a printer.

5. [Nice one, do give a shot :)] Given a directed graph G, with V vertices and E edges. Each edge in E is associated with a real number ‘r’,a reliabilty factor with r between 0(exclusive) and 1(inclusive). You are also given a pair of nodes u and v. Find the most reliable path in the given graph from u to v.

Input will be the graph represented as a matrix with the following format:

* the number of vertices n. (therefore, A is an nxn matrix)

* The elements of A, row-wise: (total n*n numbers)

A(i,j) = 0 denotes that the edge (i,j) is not present

A(i,j) between 0 (exclusive) and 1 (inclusive) indicates

that the edge (i,j) is present with reliability A(i,j).

Output: Your output will be a sequence of vertices giving the path from u to v such as 1,4,3,5,8,6,7 with u=1 and v=7. The output is thus a comma separated list of vertices giving the path from u to v.

Njoi

## Recent Activity