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. […]
As both Dynamic Programming and Greedy Strategy are used for solving Optimization problems and influenced by optimal-sub property; it might possible that one can attempt to find Greedy solution, if in fact Dynamic Programming is the right approach or vice versa. With this background, Knapsack problem (either 0/1 or Fractional) is a classic optimization problem to investigate with. You are required to support or contradict the […]
Question No.1: (12 Marks) Mr. Rashid is a visiting Lecturer by profession and he has several teaching opportunities available for the coming session. A number of educational institutes have offered him salary per day with number of hours for which his lecturing services are required. These institutes have flexible time scheduling for lectures but have restrictions on […]
Question: 1 Analyze the following pseudo code containing nested loops by computing its worst-case running time complexity. Perform all the steps by writing out the loops as summations and then solve the summations. for i = 1 to log n { set j = 1 ; // ignore its constant time in analysis while ( j […]