Dynamic Programming

1. A sequence is a palindrome if it reads the same whether you read it left to right or right to left. For example A,C,G,G,G,G,C,A. Given a sequence of length n devise an algorithm to output the length of the longest palindromic subsequence. For example, the string, A,G,C,T,C,B,M,A,A,C,T,G,G,A,M has many palindromes as subsequences, for instance: A,G,T,C,M,C,T,G,A has length 9.

2. As input you are given a string of n characters. You should output yes if the string can be broken up into a sequence of valid English words. You can assume a boolean function dict which takes a string and returns true if the string were a valid word and false otherwise in O(1) time.

Give an algorithm to determine if an input string of letters can be reconstitued as a sequence of valid words.
For instance you should output yes for Igrewvechicles since you can split this into I grew vehicles but no for Igrevvehicles

3. A k-interval-sequence of positive integers 1 ≤ a₁ < b₁ a₂ < b₂ < ... a_k < b_k ≤ n. Your input is an array A of size n and k. The array can have both positive and negative entries. The cost of a k-interval-sequence is,
∑^k_i=1 (A[b_i] - A[a_i])
Desing an algorithm that takes as input the array A and k, and determines the maximum cost you can get over all k-interval-sequences.

4. Given an array A of positive integers (need not be sorted), and an integer M, determine if there are consecutive elements A_i,A_i+1,...,A_j, in the array, whose sum is M. Devise an algorithm with runtime as O(n).

5. The input for this problem is a rooted tree with positive integer weights on its vertices. Design algorithm to output a subset S of the vertex set of maximum total weight such that, if a vertex is picked then neither its children nor its grandchildren can be selected.

6. You are given a sequence of positive integers. The weight of a subsequence is the sum of the elements in the subsequence. The length of the subsequence is the number of elements in it.

Design an algorithm to output a subsequence of maximum weight such that no three consecutive elements of the sequence are chosen to be in the subsequence.
Design an algorithm to output an increasing subsequence of maximum length such that no two consecutive elements of the sequence are chosen

<< Back to Tech Archives