Programming Problems 8

Reduced Edge MST
Recall that we can nd a minimum spanning tree of a graph G = (V,E) in O(m+ n log n) time, where m = |E| and n = |V|. Suppose we change the weight of a single arbitrary edge of G to obtain a new graph G’. Show that the new minimum spanning tree of G’ can be found in linear time, given a minimum spanning tree
for the old graph G. More formally, design an algorithm that implements:
NewSpanTree(G, w, e, x, T), which returns the minimum spanning tree of G upon changing the weight of edge e from w(e) to x, where T is a minimum spanning tree of G under the original edge weights w.Your algorithm for NewSpanTree should run in O(m+ n) time.

Merging Scheme
Suppose you have k arrays, A1,A2,……, Ak, where each input array Ai is a sorted array of numbers. You would like to output one sorted array of all the numbers in the input. To do this, you repeatedly take a pair of arrays and merge their elements into sorted order, writing the result of this merge to an intermediate
array. To merge a pair of sorted arrays with p and q elements into one sorted array takes p + q time.
The speci cation of which arrays to merge in this pairwise process is called a merging scheme. Your goal is to nd a scheme that merges all the input arrays into one sorted array and uses the minimum total merge time.

Design an algorithm that nds an optimal merging scheme. Your algorithm should run in O(n + k log k) time, where n is the total length of all the input arrays.

Arranging Pillars
You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

You have to paint N boards of length {B1, B2, B3… BN}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Array Clicking
You are given an array A of length N. You have to destroy it, given that you have the power to remove any continuous chunk of same numbers with 1 click. Thus the order in which you remove chunk matters. For example given {1, 2, 3, 1} normally it will take you 4 clicks to remove but if you first remove 2 making array {1, 3, 1} then 3 making it {1, 1} and then you can remove this continuous chunk of similar number in one click, thus completing the task in 3 clicks. How to find minimum number of clicks required? Another example is {1, 2, 3, 2, 1} which can be destroyed in 3 clicks


Programming Problems 7

Answering dynamic kth smallest queries
Given a set of n numbers, the kth smallest element can be found in O(n) time using the algorithm we
learned in class. Suppose we have a dynamic set S of numbers that changes over time, and we want to
be able to efficiently support the operations of
(a) inserting a new number into set S, and
(b) Finding the kth smallest element of S, for any k, at any time.
We could support both operations by representing S as an unsorted array A. Inserting a new element
would take just O(1) time. Finding the kth smallest element would take O(n) time. If there are many
kth smallest operations executed on set S, performing all of them will take a large amount of total
time. We might like to speed up the time to find the kth smallest, at a slight increase in the time
to insert an element. Design an algorithm that
(a) supports inserting an element into S in O(log n) time,
(b) supports Finding the kth smallest element of S in O(log n) time as well.

Room Scheduling
Suppose you have n classes that you want to schedule in rooms. Each class has a fixed time interval at which it is offered, and classes whose times overlap cannot be scheduled in the same room. There are enough rooms to schedule all the classes.
Design an algorithm to find an assignment of classes to rooms that minimizes the total number of rooms used, in O(n log n) time.

Minimizing average completion-time
Suppose you are given a collection of n tasks that need to be scheduled. With each task, you are given its duration. Specifically, task i takes ti units of time to execute. Suppose with each task we also have a release time ri, and that a task may not be started before its release time. Furthermore, tasks may be preempted, in that a scheduled task can be interrupted and later resumed, and this can happen repeatedly. Design an algorithm that finds a schedule that minimizes the average completion-time in this new situation.

Close Numbers
For a set S of n real numbers, a pair of elements x, y belong to S, where x < y, are said to be close if
y – x <= ( max(S) – min(S) ) / (n-1)
Suppose you are given an unsorted array A[1 : n] of distinct real numbers. Design an algorithm that fi nds a pair of close numbers in A in O(n) time.

Exploring a Binary Heap
Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Merging two search trees
You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?

In place Ordering
Suppose we are given a sequence S of n elements, each of which is colored red or blue.
Assuming S is represented as an array, give an in-place method for ordering S so that all the blue
elements are listed before all the red elements. Now extend your approach to three colors.
In-place means that only swap operations are allowed.

Programming Problems 6

Mapping a Phone Number

Map a phone number (such as 023-254435-13) into all the strings which can be potentially generated with a phone keyboard. Please remeber that 1 has no mapping, 2 can be mapped into ‘a’ or ‘b’ or ‘c’, 3 can be mapped into ‘d’, or ‘e’, or ‘f’ and so on. Note that 7 can be mapped into ‘p’, ‘q’, ‘r’, ‘s’, while 9 can be mapped into ‘w’, ‘x’, ‘y’, ‘z’.

Top Search Queries
Magy! receives a huge amount of queries everyday. They don’t want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don’t want to store all the queries.
Hint: split the stream into windows and accept some error in estimation.

First Not present
You are given a sequence of m distinct numbers extracted by a set of 1…n numbers, with m < n. Can you give an efficient algorithm for identifying a number not in the sequence.

How many loops
You are given n segments. In turn, you take each one of them and join it with one among those already selected, creating either a loop or a longer segment. How many loops there are in average, at every instant of time?

Finding elements near the median
Given an unsorted array A of n distinct numbers and an integer k where 1 <= k <= n, design an algorithm that finds the k numbers in A that are closest in value to the median of A in O(n) time.

Minimum positive-sum subarray
In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm.

Number of Inversions
Find the number of inversions in an array in O(nlogn) time.

%d bloggers like this: