Description
Problem 1:
Suppose you are given a set of intervals I1 = [s1, t1], . . . , In = [sn, tn], which can
possibly overlap. Your task is to select a set of points p1, . . . , pm so that each
interval intersects at least one of the points. Give an algorithm to minimize the
number of selected points m, and prove that your algorithm is optimal.
Problem 2:
Suppose you need to perform n tasks, and you can only perform one task at a
time. It takes ti time to perform the i’th task, and the task has an importance
of wi > 0. Let Ci be the completion time of the i’th task, i.e. the time when
you finish performing the task.
Find an ordering of the tasks to minimize their
weighted completion time, defined as ∑n
i=1 wiCi
. Your algorithm should work
in O(n log n) time, and you need to analyze the algorithm’s time complexity
and prove its correctness.
Problem 3:
A thief is planning to rob houses along a street. Each house has a certain
amount of money stashed, and the thief can rob any set of houses, as long as he
does not rob any adjacent houses. Determine the maximum amount of money
the thief can steal.
Problem 4:
Given three sequences L1, L2 and L, design an efficient algorithm to check if L1
and L2 can be interleaved to produce L. For example, the sequences L1 = aabb
and L2 = cba can be interleaved into sequence L = acabbab, but L1 and L2
cannot be interleaved into sequence L = aaabbbc. Analyze the time and space
complexity of your algorithm as a function of the lengths of L1 and L2.
Problem 5:
Suppose you are given a propositional logic formula containing only the terms ∧,
∨, T and F, without any parentheses. You want to find out how many different
ways there are to correctly parenthesize the formula so that the resulting formula
evaluates to true.
For example, the formula T ∨ F ∨ T ∨ F can be correctly
parenthesized in 5 ways:
(T ∨ (F ∨ (T ∨ F)))
(T ∨ ((F ∨ T) ∨ F))
((T ∨ F) ∨ (T ∨ F))
(((T ∨ F) ∨ T) ∨ F)
((T ∨ (F ∨ T)) ∨ F)
Of these, 3 evaluate to true: ((T ∨ F) ∨ (T ∨ F)), (T ∨ ((F ∨ T) ∨ F)) and
(T ∨ (F ∨ (T ∨ F))).
Give a dynamic programming algorithm to solve this problem. Describe your
algorithm, including a clear statement of your dynamic programming equation,
show that it is correct, and prove its running time.
Problem 6:
Consider a weighted directed graph G with n vertices and m edges, where
each edge (i, j) has a positive integer weight wi,j . A walk is a sequence of not
necessarily distinct vertices v1, v2, …, vk, such that any two consecutive vertices
vi
, vi+1 are connected by an edge.
The length of the walk is the sum of the
weights of the edges in the walk. Design an algorithm to find the number of
different walks from a vertex s to another vertex t which have length exactly L,
and analyze the time complexity of your algorithm.