Programming Problems 13

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.



About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: