Algorithm Design
Question Define computer algorithm. What are the characteristics of an algorithm that must be met?
NU Year 2012
Question With example define computational procedure. How can you analyze and test an algorithm?
NU Year 2012
Question How program performance can be evaluated? Explain with example.
NU Year 2012
Question Let two matrix A and B; where A be an M*P and B be a P*N matrix. Write an algorithm formatrix multiplication. Find out its time complexity.
NU Year 2012
Question What is growth function? With example, briefly explain each type of it.
NU Year 2012
Question Depict the general philosophy of D and C method. Write down the control abstraction of D and C.
NU Year 2012
Question Show that the following recurrence relation has the growth function of O(n log)
NU Year 2012
Question Write the recursive and iterative process of binary search algorithm.
NU Year 2012
Question Consider the following adjacency matrix. Construct a shortest path using all-pair shortest path algorithm:
NU Year 2012
Question What is binary search tree? Mention the properties of binary search tree.
NU Year 2012
Question What is Hamilton cycle? Give one example. Let G= (V, E) is an undirected graph with four vertices. Draw the state space tree for coloring all the four nodes using only tree colors.
NU Year 2012
Question Show that first 10 steps of 15 puzzle problem using DFS where the problem state is given below: 1 2 3 4 5 6 8 9 10 7 11 13 14 15 12
NU Year 2012
Question What is Knapsack problem? Consider a Knapsack problem to find out the optimal solution where
NU Year 2012 2009
Question What is dynamic programming? Write the general procedure of dynamic programming.
NU Year 2012
Question Consider the following multistage graph. Using backward reasoning find the shortest path from S to T.
NU Year 2012
Question Discuss the complexity analysis of the following algorithm: a. Merge sort. b. Selection sort. c. Binary search.
NU Year 2012
Question What is state-space tree? What is the manner in which the state-space tree for a back-tracking algorithm in constructed?
NU Year 2012
Question What is n-queen problem? Draw the solution for the 4-queens problem?
NU Year 2012
Question What is an optimal solution and feasible solution? In which situations a search path can be terminated in a branch and bound algorithm?
NU Year 2012
Question What is the travelling salesman problem? Consider the following directed graph for travelling salesman problem. You are asked to find the minimum cost tour using dynamic algorithm approach:
NU Year 2012
Question Define implicit and explicit constraint with example.
NU Year 2012
Question Define the following terms: a. Tree edge. b. Back edge. c. Cross edge.
NU Year 2012
Question Explain the subset sum problem and discuss the possible solutions strategies using backtracking.
NU Year 2012
Question Briefly explain the BFS algorithm with example.
NU Year 2012
Question What are the criteria’s an algorithm must satisfy? Describe them.
NU Year 2012
Question What is pseudocode? Write ten convention of pseudocode.
NU Year 2011
Question Explain time complexity of an algorithm.
NU Year 2011
Question Define ‘Big oh’, ‘Big theta’ and ‘Big omega’.
NU Year 2011
Question What are the general plans for divide-and-conquer algorithms?
NU Year 2011
Question Write the algorithms for finding the maximum and minimum and explain it.
NU Year 2011
Question What are the difference between quicksort and mergesort? Mention the algorithm used to partition an array for quicksort.
NU Year 2011
Question What is the improvement that can be applied to sequential search if the list is sorted?
NU Year 2011
Question What is the Greedy Choice Property? What are the steps required to develop a Greedy algorithm?
NU Year 2011
Question Explain multistage graph corresponding to backward approach with a suitable example.
NU Year 2011
Question Describe the steps to find out all pair’s shortest path.
NU Year 2011
Question What do you mean by optimal binary search tree? Give an example to demonstrate two possible binary search trees.
NU Year 2011
Question Write down pseudocode for breadth first search.
NU Year 2011
Question Draw depth first search (DFS) spanning tree and Breadth first search (BFS) spanning tree.
NU Year 2011
Question What is reachability problem?
NU Year 2011
Question Prove that if G is a connected undirected graph with n vertices and n-1 edges, then G is a tree.
NU Year 2011
Question What do you mean by backtracking? What are the factors that influence the efficiency of the backtracking algorithm?
NU Year 2011
Question What is state-space tree? What is the manner in which the state-space tree for a backtracking algorithm is constructed?
NU Year 2011
Question What is n-queens problem? Explain the solution for the 8-queen problem?
NU Year 2011
Question What is the use of Dijkstra’s algorithm? Write the dijkstra’s algorithm for single sources shortest path problem.
NU Year 2011
Question What is an algorithm? Write down the characteristics of an algorithm.
NU Year 2011 2008
Question What do you mean by complexity of an Algorithm? Find the average case complexity of quicksort algorithm.
NU Year 2011
Question What is randomized algorithm? Write down the advantage and disadvantages of randomized algorithm.
NU Year 2011
Question Compare the performance between recursive and iterative MAX-MIN algorithm
NU Year 2010
Question Write the control abstraction for divide and conquer.
NU Year 2010
Question Which application are not suitable for Quick sort and why?
NU Year 2010 2014
Question Write short note on 15 puzzle problem.
NU Year 2010
Question Differentiate backtracking and Bunch and Bound.
NU Year 2010
Question Write the similarity among LC search of BFS and DFS.
NU Year 2010
Question Show at least two solutions for 8 queen problem.
NU Year 2010
Question Explain implicit explicit constraints with example.
NU Year 2010
Question What do you mean by dynamic programming? What is the difference between optimal solution and feasible solution?
NU Year 2010
Question With suitable example briefly explain the Depth first search algorithm.
NU Year 2010
Question What are the steps required to solve a Greedy problem?
NU Year 2010
Question Why asymtotic notation is used?
NU Year 2010
Question Write an algorithm for n-queen problem.
NU Year 2010
Question What is graph coloring and why it is used?
Question Describe sum of subset problem.
NU Year 2010
Question List the important properties of Greedy method. What are different types of problems can be solved using Greedy method?
NU Year 2010
Question What is an algorithm? What are the criteria an algorithm must satisfy?
NU Year 2009
Question What do you mean by algorithm validation? Explain how to validate an algorithm.
NU Year 2009
Question What are the ways to describe an algorithm? Write down the pseudocode structures for looping and conditional statements.
NU Year 2009
Question Explain time space complexity of an algorithm.
NU Year 2009
Question What is big ‘O’ and omega notation? Explain the growth rate of n log n, n^2 and 2^n functions with n.
NU Year 2009
Question Write an algorithm to create an n*n magic square for the case in which n is odd. What is the value of its time complexity?
Question Write recursive function to add n numbers of an array with count statements. Write the recurrence relation for the value of count and solve it.
NU Year 2009
Question What is divide and conquer method?
NU Year 2009
Question Write down an algorithm for binary search.
Question Simulate the steps that the binary search algorithm goes through for 14 entries: (2009) -15, -6, 0, 7, 9, 23, 50, 81, 99, 113, 230, 231, 142, 151.
NU Year 2009
Question Explain Hoare’s method of partitioning with suitable example.
NU Year 2009
Question What is the time complexity of this algorithm?
NU Year 2009
Question Briefly describe about multistage graph.
NU Year 2009
Question What is all-pair shortest path problem?
NU Year 2009
Question Write an algorithm to determine the all-pair shortest paths.
NU Year 2009
Question What is optimal binary search tree?
NU Year 2009
Question Write down BFS algorithm.
NU Year 2009
Question Write down recursive backtracking algorithm for sum of subsets problem.
NU Year 2009
Question Why do we need to analyze algorithms?
NU Year 2008
Question What do you mean by time complexity? Calculate the time complexity of the following algorithm:
NU Year 2008
Question What do you mean by performance measurement?
NU Year 2008
Question Show that the average case complexity of quick sort technique is O (n log n).
NU Year 2008
Question Write down the control abstractions for the divide-and-conquer strategy.
NU Year 2008
Question Write down the algorithm for finding the minimum and maximum number from a number list using divide and conquer method.
NU Year 2008
Question Define the spanning tree. Describe Prim’s algorithm that finding minimum cost spanning tree with suitable example.
NU Year 2008
Question Write down the difference between Greedy method and Dynamic programming.
NU Year 2008
Question Differentiate between optimal solution and feasible solution.
NU Year 2008
Question Write down the algorithm for greedy strategies for the Knapsack problem.
NU Year 2008
Question What are the difference between breadth search and bin search?
NU Year 2008
Question Write down the advantages and disadvantages of BFS and DFS traversal algorithm.
NU Year 2008
Question Discuss the optimal binary search trees problems.
NU Year 2008
Question Define binary tree and skewed binary tree with an example.
NU Year 2008
Question Discuss the different traversal techniques of binary tree.
NU Year 2008
Question Prove that, BFS (Breadth First Search) visits all vertices reachable from V.
NU Year 2008
Question Write down the principal of optimality.
NU Year 2008
Question Differentiate backtracking and branch-bound method.
NU Year 2008
Question Discuss the 8’queen’s problem.
NU Year 2008
Question Write down the algorithm for all pair shortest path.
NU Year 2008