Question # 1: 10 Marks Consider the following algorithm for sorting: The main idea behind this sorting algorithm is as follows: Find the smallest element in the array Exchange it with the element in the first position Find the second smallest element and exchange it with the element in the second position Continue […]
For the following code segment, provide line-by-line analysis and construct function T(n) that give the runtime of this code as a function of “n”. Also determine the big-O for this code segment. [Marks: 5+3+2] Code segment Cost i = 1 j = 1 k = 1 while (i <= n) i = i + 1 […]
Question # 1: 10Marks (5+5) In the context of Activity Selection Problem, consider the following set of activities: Activity A B C D E F G H I J K L M N O Start Time 2 4 6 1 6 3 1 8 5 6 7 4 2 5 7 Finish Time 9 5 […]
For the following code snippet, provide line-by-line analysis and construct function T(n) that give the runtime of this code snippet as a function of “n”. Also determine the big-Oh of Best-case, Worst-case and Average case for this code snippet. [Marks: 4+2+2+2] Search(A, Key) i←1 while (A[i] ≠ key) and (i ≤ length[A]) i←i+1 if ( […]
Question. 1 Consider the following Directed Acyclic Graph. (10 Marks) Run BFS on this graph by taking node ‘1’ as source node and list the vertices in order while running BFS. Note: Write a list of vertices only, no need to show the intermediate steps. Question. 2 (5 Marks) Two directed graphs are given […]
Question 1 (10) Find the running time complexity of the following piece of code and show your working step by step. yz =0; xw=0; for(i=m; i>-6; i=i-6) { xw++; } for (i=n; i>-2015;i=i-5) { yz=yz+1;} for (i=1;i<=n;i=i*5) { for (j=1;j<=5n;j*12 { for(k=n;k>-5; k=k-4) { x=x+12 } } } Print x; While(k<=z) { k=k*2 ( for(m=k; […]
Quantum Computing is the theory that can solve all NP classes’ problems in Polynomial Time.” Support or contradict the above statement. Consider all aspects and describe precisely but not more than 100 words. Solution: There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be […]
To solve Counting money problem through Dynamic Programing as well as Greedy algorithm approaches and to develop Huffman binary tree and codes from the given frequency table. Q.No.1 Let us suppose you have to give Money change for Rs.23 in Pakistani currency in minimum possible coins/currency notes. The denominations in the form of coins are 1, 2, 5 and currency notes of 10, […]
Question 1 (10) Arrange the following in the Most to least complexity. Here “n “is the input size for the some complexity function and j> k where j , k are numbers greater than 2.Every function is separated by “comma” and note that there are 20 functions to arrange. Question 2 (5+5) a) You have to build Max heap for […]
This assignment is to revise basic level concepts to make basis for advance concepts of Analysis of Algorithms. This assignment will help you to understand the concepts of Asymptotic Growth, making analysis of pseudo code, recurrence relation development, and asymptotic function understanding of resultant formulae concept of recurrences. You can write the pseudo codes form given […]