Assignments-S4‎ > ‎

### BT0080

 Bachelor of Science in Information Technology (BScIT) – Semester 4 BT0080 – Fundamentals of Algorithms – 4 Credits (Book ID: B1092) Assignment Set – 1 (60 Marks)     Answer the following:                                                                   6x10 = 60 1. Write the different characteristics of an algorithm. 2. Explain the concept of Mathematical expectation in average case analysis. 3. Write the MaxMin algorithm. 4. Prove that “ If then, Greedy knapsack algorithm generates an optimal solution to the given instance of the knapsack problem” 5. Explain the concept of travelling salesman problem. 6. What do you mean by sum of subsets problem? Explain? ============================================= Bachelor of Science in Information Technology (BScIT) – Semester 4 BT0080 – Fundamentals of Algorithms – 4 Credits (Book ID: B1092) Assignment Set – 2 (60 Marks)     Answer the following:                                                                   6x10 = 60 1. Write the steps involved in the general method for Branch and Bound? Explain? 2. Explain the NP hard and the NP complete problems? 3. Briefly explain the concept of trees? 4. Prove that “A tree with n vertices has (n – 1) edges”? 5. Prove that “A connected graph G is a Euler graph if and only if it can be decomposed into circuits” 6. Show that the Clique problem is an NP-complete problem.