The first problem

Given a tree T of N nodes, where each node i has C_i coins attached with it. You have to choose a subset of nodes such that no two adjacent nodes(i.e. nodes connected directly by an edge) are chosen and sum of coins attached with nodes in chosen subset is maximum.

The second problem

Given a tree T of N nodes, calculate longest path between any two nodes

The third problem

You have a set of n integers each in the range 0 ... K. Partition these integers into two subsets such that you minimize |S1 - S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

---------------------Just think(kernels)------------------

The fourth problem

Given naturals n and k, to output the lexicographically smallest permutation(if possible) of [n] such that |i-a(i)|<=k

The fifth problem(this is hard)

Given a set S, |S|=n. Need to find the element "a" in S which occur >(n/2)

Note:- (1)Observe the strict inequality.

(2)The only operation you can do is check if 2 elements in the set S are equal, you get answer as yes or no via this operation.

(3) You can't order the set.

----------------------------Greedy--------------------------

The sixth problem

You are want to conserve money and the laptop you are using has become old. So you decide to make your own desktop and conserve money.

So what you do is get some cache(rest is done by your brother), but the cache is really small, it can store only k thing(all of equal size), you want to implement a cache algorithm but you have no idea about online algorithms. so you pray to THE ORACLE, THE ORACLE sees the future and tells what you are going to do. So you know the order of things which will be required. 

You get the items C_i 1<=i<=n.

Now how cache works is it store the things which will be required often and just stores them. 

It stores a new thing it sees; if it has empty space then just add the new thing to the cache, else deletes 1 of the k things which is already in the cache, and stores the new thing.

Now your goal is to minimize the number of times the cache is altered. 

If you did not understand that:-

Cache with capacity to store k items, 

sequence of n items is requested C_i 1<=i<=n.

Cache hit: item already in cache when requested.

Cache miss: item not already in cache when requested:must bring requested item into cache, and evict some existing item, if full

Output and eviction schedule that minimizes the number of cache misses.

------------------------Divide and Conquer---------------

The seventh problem

Given an array A of integers find the subarray with the maximum sum of elements.(don't give a DP solution, compare the complexity with DP solution).

The eighth problem

Suppose you are given k sorted lists each of n elements, you want to combine them to make a kn element array, how will you do this, think about the complexity.