Anna Univ question bank for IT

My exam of IT at Anna university is about to come. So I need a sample paper. So here can you provide me a sample paper of this exam?

[sumit]

I have a sample paper of Anna university as you want. So here I am providing you it.




1. Find the order of n3 +300 +500

2. Define 0 notation.

3. List the basic steps involved while solving any problem using the Divide-and-
Conquer strategy.

4. State a problem that is solved using a Greedy algorithm.

5. What are Greedy algorithms?

6. Give an application of the Longest Common Sequence problem.

7. How is the solution for 8-Queens problem represented?

8. What is meant by best-first branch-and-bound algorithm?


9. Define NP problems using language theoretic framework.


10. State a classical NPC problem.
Part B (5 X 16 = 80 marks)


11. Write the complete Merge-so rt algorithm including any algorithm it
uses and do a worst case analysis of it. Show how the algorithm works
on the list {10, 15, 25, 35, 50, 90, 40, 80}
(8+4+4)


12.
(a) Write the complete Quick-sort algorithm including any algorithm it
uses. Generate a recurrence relation for its worst case analysis.
Solve this recurrence relation and arrive at its worst-case behavior. (8+2+6)

(OR)

(b) Write the algorithm FASTEST-WAY that finds the fastest way through the
factory which has two assembly lines.
(16)

13.
(a) Write down the MATRIX-CHAIN_ORDER algorithm. Find an optimal
parenthesization of a matrix-chain product whose sequence of
dimensions is (5, 10, 3, 2, 5 ). How many scalar multiplications are
done in that case? Show the m table and s table generated.
(16)