## New Update

IGNOU BCA, MCA New, PGDCA New, M.com, PGDIBO solved assignments July-January 2023-24 & January -July 2023 now available. Note: If do not get solved assignments after payment then mail us. Thanks You...

## Saturday, 1 April 2023

IGNOU BCA fourth semester BCS-042 term-end exam notes, upcoming guess papers, questions papers, books/blocks, important questions, important notes and old/previous years papers with solutions free download. We provided bca term-end exam notes with solution for ignou student help in exam. IGNOU BCS-042 term-end exam notes, important questions, questions papers download. IGNOU BCA/MCA all semester new revised (1st semester, 2nd semester, 3rd semester, 4th semester, 5th semester and 6th semester) term-end exam notes, study materials, important questions, books/blocks, previous years paper, upcoming guess paper (June-December) free download.

IGNOU BCA BCS-042 4th semester Term-End Examination (INTRODUCTION TO ALGORITHM DESIGN) books/block,term-end exam notes, upcoming guess paper, important questions, study materials, previous year papers (June 2015 to June 2018) with solutions download.

 S No. Topic with  Solutions 1. Algorithm and Complexity 2. Introduction and Recurrence Relation 3. Analysis of Simple Algorithm 4. Greedy Technique 5. Graph 6. Divider and Conquer 7. Guess Questions Set 8. Old/Previous Years Papers with Solutions (June 2015 to June 2018)

Notes-1

1. (i) Given a list of integers (shown below),determine the number of comparisons and assignment operation used by bubble sort to sort the list. Show the process of sorting.
35 8 7 15 25 30 10 12
Perform worst case analysis.
(ii) Prove or disprove the following using the basic definition of 0 (big Oh) :
5n2 + 8n + 15 = 0(n2)
(iii) Group the following function by complexity category :

2n, n, n!,→√n, 4n + 12
(iv) Apply DFS and BFS to the complete graph on four vertices. List the vertices in the order they would be visited.

2. Write Prim's algorithm and apply to find minimum cost spanning tree for the following graph :

3. Illustrate the working of binary search tree while searching for the element 14 in the following
sorted array :
8 14 20 25 35 45 50 85 95 100
Also analyze the algorithm for best and worst cases.

4. (i) What is recurrence relation ? Write a recurrence equation for any algorithm which follows Divide and Conquer strategy and explain it.
(ii) Define the following terms :
• Backtracking
• Dynamic Programing
• Time Complexity
• Asymptotic Analysis
• Upper Bound

5. (i) Suppose you are given currency notes of all denominations, e.g. (2, 5, 10, 15, 20, 100, 500). Further it is assumed that currency notes of each denomination are available in sufficient numbers for the purpose of using the minimum number of notes. The problem is to find the minimum number of
currency notes to make the amount of 437 using the Greedy approach. Show the sequence of steps for selection and rejection of notes.
(ii) Define the following terms :
• Connected Graphs
• Path
• Cycle
• Tree

Notes-2

1. (a) Write an algorithm to compute an by left to right binary exponentiation method and illustrate through an example.
(b) Do the complexity analysis of the above algorithm.
(c) Put the following classes of algorithm in the increasing order of growth :
O(2n), O(n log2 n), O(log2 n), O(n).
(d) Using the definition of Big Oh, show that
6n2+ 20 n = O(n3).
(e) What is the difference between a graph and a tree ? Draw four spanning trees of the following graph :

2. Apply Kruskal's algorithm to find a minimum cost spanning tree of the following graph :

3. (a) Apply the Merge Sort algorithm to sort the following list :
15 5 8 7 4 20 25
(b) Describe any two methods of solving the recurrence relation.

4. Explain the following terms with examples :
(a) Complete graph
(b) Combinatorial problems
(c) Branch and bound technique
(d) Loose bound
(e) Average case

5. (a) Find the optimal solution to the knapsack instance (fractional) :
n = 5, M = 10
(P1, P2, P3, P4, P5) = (14, 24, 32, 18, 20)
(W1, W2, W3, W4, W5) = (7, 8, 4, 3, 5)
(b) What is a single source shortest path problem ? What are the proposed solutions ?

Notes-3

1. (a) Using the definition of  𝛀, show that

6n2 + 20n ≠ 𝛀(n3)
(b) Given a list of n distinct integers. Write an algorithm to determine the position of an integer in the list using a linear search and count the number of comparison operations required.
(c) By applying induction method, show that for all positive integers n

(d) Illustrate the representation of the following graph through adjacency list and adjacency matrix :

2. (a) Find the optimal solution to the knapsack (fractional) problem n = 5 and m = 10, where n is the number of objects and m is the capacity of knapsack.Profit and weight of each object are given
below :
(P1, P2, P3, P4, P5) = (10, 30, 35, 20, 40)
(W1, W2, W3, W4, W5) = (3, 5, 2, 6, 1).
(b) Write Prim's algorithm to find the minimum cost spanning tree.

3. (a) Apply QuickSort to sort the following array. Show all the steps.
15 5 10 8 7 2 20 30
(b) What are the worst case and best case in QuickSort algorithm ?

4. Define the following terms :
(a) Optimization
(b) Dynamic programming
(c) Recurrence relation
(d) Asymptotic bounds
(e) Unconnected graph

5. For the given graph, apply DFS traversal scheme and write DFS sequence. Also write the time
complexity of DFS and BFS algorithms.

IGNOU BCA BCS-042 4th semester Term-End Examination (INTRODUCTION TO ALGORITHM DESIGN) term-end notes and old paper (June 2015 to June 2018) with solutions. Download

Also available:-