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 […]
Question Statement Counting money problem is an optimization problem in which the Change (coins, paper notes) is to be count out for a certain amount of money (N) in minimum possible number of coins/bills. Like 0/1 Knapsack problem in the Dynamic Programing solution for Making change, we also build a table C [k, N]. Columns […]
Question 1: (5 Marks) What are the characteristics of Random Access Machine? Briefly write down any two characteristics. Solution: Random Access Machine is a favorite model of a sequantial ‘ computer. Its main features are: 1. Computation unit with a user defined program.’ 2. Read-only inputtape and write-only output tape. 3. Unbounded number of local memory cells. […]