Question:&nbsp;Explain Breadth First Search (BFS) algorithm with a suitable example. Answer:&nbsp;Breadth First Search (BFS) is a graph traversal algorithm used to explore nodes and edges of a graph systematically. It starts at a given source node and explores all its neighbors at the current depth before moving on to nodes at the next depth level. BFS is particularly useful for finding the shortest path in an unweighted graph and for exploring all connected components of a graph. <h2>How BFS Works:</h2><ul><li style="background-color: transparent;font-size: 18px">Initialization: Start with a queue and enqueue the starting node. Mark the starting node as visited.</li><li style="background-color: transparent">Traversal: While the queue is not empty:<ul><li style="background-color: transparent;font-size: 18px">Dequeue a node from the front of the queue.</li><li style="background-color: transparent;font-size: 18px">Process the node (e.g., print it or store it in a result list).</li><li style="background-color: transparent;font-size: 18px">Enqueue all its unvisited neighbors and mark them as visited.</li></ul></li><li style="background-color: transparent;font-size: 18px">Repeat: Continue until the queue is empty.</li></ul>BFS uses a queue data structure to ensure that nodes are processed in the order they are discovered. <h3 style="line-height: 1.2">Example:</h3>Let’s consider a graph represented as an adjacency list:<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/BFS_1743337807868.png" alt="BFS" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="BFS.png" data-file-size="11346" data-origin="," origin-size="240,178" style=""></figure></div><h3> </h3>Adjacency List:A: [B, C] B: [A, D, E] C: [A, F] D: [B] E: [B] F: [C] <h3>BFS Traversal:</h3>​Suppose we start BFS from node A. <ul><li style="background-color: transparent">Initialization:<ul><li style="background-color: transparent;font-size: 18px">Queue: [A]</li><li style="background-color: transparent;font-size: 18px">Visited: {A}</li></ul></li><li style="background-color: transparent">Step 1:<ul><li style="background-color: transparent;font-size: 18px">Dequeue <code>A</code> (process it).</li><li style="background-color: transparent;font-size: 18px">Enqueue its neighbors <code>B</code> and <code>C</code>.</li><li style="background-color: transparent;font-size: 18px">Queue: [B, C]</li><li style="background-color: transparent;font-size: 18px">Visited: {A, B, C}</li></ul></li><li style="background-color: transparent">Step 2:<ul><li style="background-color: transparent;font-size: 18px">Dequeue <code>B</code> (process it).</li><li style="background-color: transparent;font-size: 18px">Enqueue its unvisited neighbors <code>D</code> and <code>E</code>.</li><li style="background-color: transparent;font-size: 18px">Queue: [C, D, E]</li><li style="background-color: transparent;font-size: 18px">Visited: {A, B, C, D, E}</li></ul></li><li style="background-color: transparent">Step 3:<ul><li style="background-color: transparent;font-size: 18px">Dequeue <code>C</code> (process it).</li><li style="background-color: transparent;font-size: 18px">Enqueue its unvisited neighbor <code>F</code>.</li><li style="background-color: transparent;font-size: 18px">Queue: [D, E, F]</li><li style="background-color: transparent;font-size: 18px">Visited: {A, B, C, D, E, F}</li></ul></li><li style="background-color: transparent">Step 4:<ul><li style="background-color: transparent;font-size: 18px">Dequeue <code>D</code> (process it).</li><li style="background-color: transparent;font-size: 18px">No unvisited neighbors.</li><li style="background-color: transparent;font-size: 18px">Queue: [E, F]</li><li style="background-color: transparent;font-size: 18px">Visited: {A, B, C, D, E, F}</li></ul></li><li style="background-color: transparent">Step 5:<ul><li style="background-color: transparent;font-size: 18px">Dequeue <code>E</code> (process it).</li><li style="background-color: transparent;font-size: 18px">No unvisited neighbors.</li><li style="background-color: transparent;font-size: 18px">Queue: [F]</li><li style="background-color: transparent;font-size: 18px">Visited: {A, B, C, D, E, F}</li></ul></li><li style="background-color: transparent">Step 6:<ul><li style="background-color: transparent;font-size: 18px">Dequeue <code>F</code> (process it).</li><li style="background-color: transparent;font-size: 18px">No unvisited neighbors.</li><li style="background-color: transparent;font-size: 18px">Queue: []</li><li style="background-color: transparent;font-size: 18px">Visited: {A, B, C, D, E, F}</li></ul></li></ul><h4>Final BFS Traversal Order:</h4>​A -&gt; B -&gt; C -&gt; D -&gt; E -&gt; F ​<h2>Pseudo Code for BFS</h2><blockquote>​ <pre style="line-height: 1.45">​BFS(Graph, StartNode): 1. Create an empty Queue 2. Create a Set to keep track of visited nodes 3. Enqueue the StartNode into the Queue 4. Mark StartNode as visited by adding it to the Set 5. While the Queue is not empty: a. Dequeue a node (CurrentNode) from the front of the Queue b. Process the CurrentNode (e.g., print it or store it in a result list) c. For each Neighbor of the CurrentNode: &nbsp;&nbsp;&nbsp;&nbsp;i. If the Neighbor is not in the visited Set: &nbsp;&nbsp;&nbsp;&nbsp;- Enqueue the Neighbor into the Queue &nbsp;&nbsp;&nbsp;&nbsp;- Mark the Neighbor as visited by adding it to the Set 6. End</pre></blockquote> <h3>Key Points:</h3><ul><li style="background-color: transparent;font-size: 18px">BFS explores all nodes at the current depth level before moving to the next level.</li><li style="background-color: transparent;font-size: 18px">It uses a queue to keep track of nodes to be processed.</li><li style="background-color: transparent;font-size: 18px">BFS is guaranteed to find the shortest path in an unweighted graph.</li><li style="background-color: transparent;font-size: 18px">It works for both directed and undirected graphs.</li></ul>

Question 1 (d)

<h2 style="line-height: 1.2">Previous Year Question and their Answers. </h2><h3 style="line-height: 1.2">Below are the list of Question asked in December 2023. </h3>1. <a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(a)">(a).&nbsp;What is Euclid’s algorithm to find GCD of two given integers ? Write the steps involved in finding GCD of (a, b) using Euclid’s algorithm.</a> <a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(b)">(b).&nbsp;What are Big 'O' and Big 'Θ'&nbsp;notations ? Explain with the help of representative diagram.</a>​<a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(c)">(c).&nbsp;Write and explain linear search algorithm. Mention best case, worst caseand average case scenarios of linear search.</a><a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(d)">(d).&nbsp;Explain Breadth First Search (BFS) algorithm with a suitable example.</a><a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(e)">(e).&nbsp;What is Task Scheduling algorithm ? Write pseudo code for task scheduling algorithm.</a><a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(f)">(f).&nbsp;Solve the given recurrence relation using recursion tree method:</a><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mn>2</mn><mi>T</mi><mrow><mo fence="true">(</mo><mfrac><mi>n</mi><mn>2</mn></mfrac><mo fence="true">)</mo></mrow><mo>+</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">(n) = 2T\left({ \frac n 2}\right)+n</annotation></semantics></math>(n)=2T(2n​)+n<a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(g)">(g).&nbsp;What are P, NP and NP-complete problems ? Give example of each.</a><a href="https://ignoustudyadda.com/solved-paper/mcs-211-dec-2023/question-1-(h)">(h).&nbsp;What is a Minimum Cost Spanning Tree(MCST) ? Write Generic MCST algorithm.</a>

Home

<h1>Question: What is Euclid’s algorithm to find GCD oftwo given integers ? Write the steps involved in finding GCD of (a, b) using Euclid’s algorithm</h1>​ Answer: Euclid's Algorithm is an efficient method for finding the Greatest Common Divisor (GCD) of two integers. The GCD of two integers is the largest integer that divides both of them without leaving a remainder.Lets take two positive integers (12, 33) for explanation.There are 4 things that will play crucial role to get GCD for very huge numbers.<ol><li style="font-size: 18px">Integer (a) </li><li style="font-size: 18px">Integer (b)</li><li style="font-size: 18px">Quotient (q)</li><li style="font-size: 18px">Remainder (r)</li></ol>As per the given integer 12 and 33.&nbsp; Step 1:&nbsp; During execution of Euclid's algorithm bigger integer should be swap to a and lesser to b like below.a = 33b = 12Step 2: Check if b &gt; 0 then move to next step other wise the existing number in a column would be GCD of the integers.Step 3: Will get Mod of a and b and assign remainder to r and do same repetion untill b value becomes 0.<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/euclid-algo_1737707461106.png" alt="Euclid's Algorithm to get GCD" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="euclid-algo.png" data-file-size="50713" data-origin="," origin-size="341,381" style=""></figure></div><h2> </h2><h2>Steps of the Algorithm </h2><ol><li style="font-size: 18px">​If b=0, return a and exit</li><li style="font-size: 18px">else go to step 3</li><li style="font-size: 18px">&nbsp;Divide a by b and assign remainder to r</li><li style="font-size: 18px">&nbsp;Assign the value of b to a and the value of r to b and go back to step 1</li></ol><h2>Pseudo Code</h2><blockquote>​begin [start of Algorithm]{while b ≠ 0 do{r ← a mod b; a ←b;b← r;} [end of while loop]return (b)} [end of algorithm] </blockquote>

Question 1 (a)

Question:&nbsp;What are Big 'O' and Big 'Θ'&nbsp;notations ? Explain with the help of representative diagram.Answer:&nbsp;Big O Describes the&nbsp;Upper Bound&nbsp;of an algorithm's running time. It represents the worst-case scenario.Big O is used to represent the upper bound or a worst case of an algorithm since it bounds the growth of the running time from above for large value of input sizes. It notifies that a particular procedure willnever go beyond a specific time for every input n.notation is that it makes algorithms much easier to analyze, since we can conveniently ignore low-order terms. <h3>Expression:&nbsp;</h3>T(n) ∈ O(g(n)) if&nbsp;there&nbsp;exist&nbsp;constants&nbsp;c &gt; 0&nbsp;and&nbsp;n0&nbsp;such&nbsp;that&nbsp;T(n) ≤ c⋅g(n)&nbsp;for&nbsp;all&nbsp;n ≥ n0.<h3>Example: IfT(n)=3n2+5n+7T(n) = 3n^2 + 5n + 7&nbsp;T(n)=3n2+5n+7, then&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>T</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mi>ε</mi><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></mrow><annotation encoding="application/x-tex">T(n) \varepsilon {O(n^2)}</annotation></semantics></math>T(n)εO(n2)​</h3> <div class="se-component se-image-container __se__float-none" style="width: 100%"><figure style="width: 100%;"><img src="https://www.api.ignoustudyadda.com/upload/editor-image/big-o_1737782457013.jpg" alt="Big O Representative Digram" data-rotate="" data-proportion="true" data-size="100%," data-align="none" data-percentage="100," data-file-name="big-o.jpg" data-file-size="3157801" data-origin="," origin-size="1972,1109" style="width: 100%;"></figure></div><h2 style="line-height: 1.2">Theta Notation (Θ\ThetaΘ)​</h2>​​Describes the&nbsp;tight bound&nbsp;of an algorithm's running time. It represents both the best-case and worst-case scenarios.​In case the running time of an algorithm is&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>θ</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\theta(n)</annotation></semantics></math>θ(n), it means that once n gets large enough the running time is minimum c1.n and maximum time is c2.n, where c1 and c2 are constants.It provides both upper and lower bounds of an algorithm. The following&nbsp;figure illustrates the function f(n) = Θ(g(n).<div class="se-component se-image-container __se__float-none" style="width: 100%"><figure style="width: 100%;"><img src="https://www.api.ignoustudyadda.com/upload/editor-image/big-theta_1737783802848.jpg" alt="Thta notation Representative diagram" data-rotate="" data-proportion="true" data-size="100%," data-align="none" data-percentage="100," data-file-name="big-theta.jpg" data-file-size="5999080" data-origin="," style="width: 100%;"></figure></div>​<h3 style="line-height: 1.2">Expression:</h3>T(n) ∈ Θ(g(n)) if&nbsp;there&nbsp;exist&nbsp;constants&nbsp;c1,c2&gt;0&nbsp;and&nbsp;n0&nbsp;such&nbsp;that&nbsp;c1⋅g(n)≤T(n)≤c2⋅g(n)&nbsp;for&nbsp;all&nbsp;n≥n0.Example:<h3 style="line-height: 1.2">IfT(n)=3n2+5n+7T(n) = 3n^2 + 5n + 7T(n)=3n2+5n+7,then&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>T</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mi>ε</mi><mrow><mi>θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></mrow><annotation encoding="application/x-tex">T(n) \varepsilon {\theta(n^2)}</annotation></semantics></math>T(n)εθ(n2)</h3> ​​

Question 1 (b)

Question 1(c):&nbsp;Write and explain linear search algorithm. Mention best case, worst case&nbsp;and average case scenarios of linear Search. Answer: Linear search or sequential search is a very simple search algorithm which isused to search for a particular element in an array. Unlike binary search algorithm, in linear search algorithm, elements are not arranged in a particular order. In this type of search, an element is searched in an array sequentially one by one. If a match is found then that particular item is returned and the search process stops. Otherwise, the search continues till the end of an array.The following steps are used in the linear search algorithm: <h2>How Linear Search Works</h2><blockquote>​Linear_ Search( A[ ], X)Step 1: Initialize i to 1Step 2: if i exceeds the end of an array then print “element not found” and ExitStep 3: if A[i] = X then Print “Element X Found at index i in the array” and Exit Step 4: Increment i and go to Step 2 </blockquote><h3>Algorithm Steps</h3>Initialize: Start at the beginning of the list (index 0).Iterate through the List:<ul><li style="font-size: 16px">For each element in the list:</li><ul><li style="font-size: 16px">Compare the current element with the target value.</li><li style="font-size: 16px">If the element equals the target, return the index (or the element itself, depending on the requirements).</li></ul></ul>Termination:<ul><li style="font-size: 16px">If the target is found, the search stops.</li><li style="font-size: 16px">If the end of the list is reached without finding the target, the algorithm indicates that the target is not present (often by returning -1 or null).</li></ul><h3>Pseudocode </h3><pre>​function linearSearch(array, target): for index from 0 to length(array) - 1: if array[index] == target: return index // Target found at this index return -1 // Target not found </pre><h2> </h2><h2>Time and Space Complexity</h2><h3>​Time Complexity: </h3><table class="se-table-layout-fixed"><thead><tr><th><div>Case</div></th><th><div>Best Case&nbsp;</div></th><th><div>Worst Case</div></th><th><div>Average Case</div></th></tr></thead><tbody><tr><td><div>Item is Present</div></td><td><div>O(1)</div></td><td><div>O(n)</div></td><td><div>O(n/2) = O(n)</div></td></tr><tr><td><div>Item is not Present</div></td><td><div>O(n)</div></td><td><div>O(n)</div></td><td><div>O(n)</div></td></tr></tbody></table><h3> </h3><h3>Space Complexity: </h3>​O(1) — Only a constant amount of extra memory is needed regardless of the size of the input.​

Question 1 (c)

Question: What is Task Scheduling algorithm ? Write pseudo code for task scheduling algorithm. Answer:&nbsp;A Task Scheduling Algorithm is a technique used to determine the order in which tasks or processes are executed by a CPU or resource. The goal is to optimize resource utilization, minimize waiting time, and ensure fairness among tasks. Common scheduling algorithms include First Come First Serve (FCFS), Shortest Job Next (SJN), Round Robin (RR), and Priority Scheduling. <h2>Pseudo Code for Task Scheduling Algorithm (FCFS) </h2><pre>​TaskScheduling(Tasks): 1. Input: A list of tasks with their arrival time and execution time 2. Sort the tasks by their arrival time 3. For each task in the sorted list: &nbsp;&nbsp;&nbsp;&nbsp; a. Wait until the task's arrival time (if necessary) &nbsp;&nbsp;&nbsp;&nbsp;b. Execute the task for its execution time &nbsp;&nbsp;&nbsp;&nbsp; c. Mark the task as completed 4. End </pre> This pseudo code represents the First Come First Serve (FCFS) scheduling algorithm, where tasks are executed in the order they arrive.​

Comments

MCS 211