Education In Pakistan

Papers, Notes, Books & Help For Students

UPDATED EDUCATIONAL NEWS INTERVIEW HELP FOR ALL JOBS ONLINE BOOKS SCHOLARSHIPS AVAILABLE INTERNSHIP JOBS

Tag: Fundamentals of Algorithms

Virtual University VU CS502- Fundamentals of Algorithms Final Term Past Solved Unsolved All Year Past Papers

Virtual University VU CS502- Fundamentals Of Algorithms Final Term Past Solved Unsolved All Year Past Papers

Click Any Link Below to View Final Term Past Papers

Virtual University VU CS502- Fundamentals Of Algorithms Final Term Past Solved Unsolved All Year Past Papers

VU CS502- Fundamentals of Algorithms FinalTerm solved unsolved past papers Fall 2008

VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers Fall 2008

FINALTERM EXAMINATION

Fall 2008

CS502- Fundamentals of Algorithms (Session – 1)

Question No: 1 ( Marks: 1 ) – Please choose one

_______________ is a graphical representation of an algorithm

  • notation
  • Flowchart
  • Asymptotic notation
  • notation

Question No: 2 ( Marks: 1 ) – Please choose one

Which of the following is calculated with bigo notation?

  • Lower bounds
  • Upper bounds
  • Both upper and lower bound
  • Medium bounds

Question No: 3 ( Marks: 1 ) – Please choose one

Merge sort makes two recursive calls. Which statement is true after these recursive calls

finish, but before the merge step?

  • The array elements form a heap
  • Elements in each half of the array are sorted amongst themselves
  • Elements in the first half of the array are less than or equal to elements in the second half of the array
  • None of the above

Question No: 4 ( Marks: 1 ) – Please choose one

Who invented Quick sort procedure?

  • Hoare
  • Sedgewick
  • Mellroy
  • Coreman

Question No: 5 ( Marks: 1 ) – Please choose one

What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1

  • O(logn)
  • O(n)
  • O(nlogn)
  • O(2n)

Question No: 6 ( Marks: 1 ) – Please choose one

Consider the following Huffman Tree

The binary code for the string TEA is

  • 10 00 010
  • 011 00 010
  • 10 00 110
  • 11 10 110

Question No: 7 ( Marks: 1 ) – Please choose one

If a graph has v vertices and e edges then to obtain a spanning tree we have to delete v edges.

  • v
  • e + 5 edges
  • v + e edges.
  • None of these

Question No: 8 ( Marks: 1 ) – Please choose one

Can an adjacency matrix for a directed graph ever not be square in shape?

  • Yes
  • No

Question No: 9 ( Marks: 1 ) – Please choose one

One of the clever aspects of heaps is that they can be stored in arrays without using any

_______________.

  • Pointers (p #40)
  • constants
  • variables
  • functions

Question No: 10 ( Marks: 1 ) – Please choose one

Merge sort requires extra array storage,

  • True   p #54)
  • False

Mergesort is a stable algorithm but not an in-place algorithm. It requires extra array storage.

 

Question No: 11 ( Marks: 1 ) – Please choose one

Non-optimal or greedy algorithm for money change takes____________

  • O(k)   (p#99)
  • O(kN)
  • O(2k)
  • O(N)

Question No: 12 ( Marks: 1 ) – Please choose one

The Huffman codes provide a method of encoding data inefficiently when coded using

ASCII standard.

  • True
  • Falase   (p# 99

The Huffman codes provide a method of encoding data efficiently.

Question No: 13 ( Marks: 1 ) – Please choose one

Using ASCII standard the string abacdaacac will be encoded with __________ bits.

  • 80 (p# 99
  • 160
  • 320
  • 100

Consider the string “ abacdaacac”. if the string is coded with ASCII codes, the message length would be10 × 8 = 80 bits.

Question No: 14 ( Marks: 1 ) – Please choose one

Using ASCII standard the string abacdaacac will be encoded with 160 bits.

  • True
  • False   (p# 99)

Question No: 15 ( Marks: 1 ) – Please choose one

Using ASCII standard the string abacdaacac will be encoded with 320 bits.

  • True
  • False   (p# 99)

Question No: 16 ( Marks: 1 ) – Please choose one

Using ASCII standard the string abacdaacac will be encoded with 100 bits.

  • True
  • False   (p# 99)

Question No: 17 ( Marks: 1 ) – Please choose one

Using ASCII standard the string abacdaacac will be encoded with 32 bytes

  • True
  • False   (p# 99)

Question No: 18 ( Marks: 1 ) – Please choose one

The greedy part of the Huffman encoding algorithm is to first find two nodes with

smallest frequency.

  • True   (p# 100)
  • False

Question No: 19 ( Marks: 1 ) – Please choose one

The greedy part of the Huffman encoding algorithm is to first find two nodes with

character frequency

  • True

False   (p# 100)

Question No: 20 ( Marks: 1 ) – Please choose one

Huffman algorithm uses a greedy approach to generate an antefix code T that minimizes

the expected length B (T) of the encoded string.

  • True   (p# 102)
  • False

Question No: 21 ( Marks: 1 ) – Please choose one

Depth first search is shortest path algorithm that works on un-weighted graphs.

  • True

False   (p# 153)

The breadth-first-search algorithm we discussed earlier is a shortest-path algorithm that works on un-weighted graphs

Question No: 22 ( Marks: 1 ) – Please choose one

Dijkestra s single source shortest path algorithm works if all edges weights are nonnegative and there are no negative cost cycles.

  • True   (p# 159)
  • False

Question No: 23 ( Marks: 1 ) – Please choose one

Dijkestra s single source shortest path algorithm works if all edges weights are negative

and there are no negative cost cycles.

  • True   (p# 159)
  • False

Question No: 24 ( Marks: 1 ) – Please choose one

Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of the

algorithm is in the clever recursive formulation of the shortest path problem.

  • True   (p# 162)
  • Flase

Question No: 25 ( Marks: 1 ) – Please choose one

Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid recursive

evaluation by generating a table for

  • k
  • ij d
  • True
  • Flase

the case with DP algorithms, we will avoid recursive evaluation by generating a table for d(k)ij

 

 

Question No: 26 ( Marks: 1 ) – Please choose one

The term coloring came form the original application which was in map drawing.

  • True   (p# 173)
  • False

Question No: 27 ( Marks: 1 ) – Please choose one

In the clique cover problem, for two vertices to be in the same group, they must be_______________each other.

  • Apart from
  • Far from
  • Near to
  • Adjacent to ( P# 176)

Question No: 28 ( Marks: 1 ) – Please choose one

In the clique cover problem, for two vertices to be in the same group, they must be apart

from each other.

  • True
  • False    ( P# 176)

Question No: 29 ( Marks: 1 ) – Please choose one

The difference between Prims algorithm and Dijkstra s algorithm is that Dijkstra s

algorithm uses a different key.

  • True     ( P # 156) not sure
  • False

Question No: 30 ( Marks: 1 ) – Please choose one

The difference between Prim s algorithm and Dijkstra s algorithm is that Dijkstra s

algorithm uses a same key.

  • True
  • False    ( P # 156) not sure

 

Question No: 31 ( Marks: 1 )

Do you think greedy algorithm gives an optimal solution to the activity scheduling

problem?

Question No: 32 ( Marks: 1 )

Define Forward edge

Question No: 33 ( Marks: 2 )

Is there any relationship between number of back edges and number of cycles in DFS?

Question No: 34 ( Marks: 2 )

What is the common problem in communications networks and circuit designing?

Question No: 35 ( Marks: 3 )

Let the adjacency list representation of an undirected graph is given below.

Explain what general property of the list indicates that the graph has an isolated

vertex.

Question No: 36 ( Marks: 3 )

Describe Minimum Spanning Trees Problem with examples.

Question No: 37 ( Marks: 3 )

Explain the following two basic cases according to Floyd-Warshall Algorithm,

1. Don t go through vertex k at all.

2. Do go through vertex k.

Question No: 38 ( Marks: 5 )

Show the result of time stamped DFS algorithm on the following graph. Take node E as a

starting node.

Question No: 39 ( Marks: 5 )

Why we need reduction?

Question No: 40 ( Marks: 10 )

Run DFS sweep and topological sort on the directed graph defined by the following

adjacency matrix.

Question No: 41 ( Marks: 10 )

Consider the digraph on eight nodes, labeled 1 through 8, with eleven directed edges

1 2, 1 4, 2 4, 3 2, 4 5, 5 3 ,5 6, 7 8, 7 1, 2 7,8 7

List the strongly connected components of this digraph.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers Fall 2008

VU CS502- Fundamentals of Algorithms FinalTerm solved unsolved past papers Spring 2010

VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers Spring 2010

FINALTERM  EXAMINATION

Spring 2010

CS502- Fundamentals of Algorithms (Session – 4)

Solved by eagle _ eye

Time: 90 min

Marks: 58

Question No: 1    ( Marks: 1 )    – Please choose one

 An optimization problem is one in which you want to find,

► Not a solution

► An algorithm

► Good solution

       ► The best solution

Question No: 2    ( Marks: 1 )    – Please choose one

 Although it requires more complicated data structures, Prim’s algorithm for a minimum spanning tree is better than Kruskal’s when the graph has a large number of vertices.

       ► True

► False

Question No: 3    ( Marks: 1 )    – Please choose one

 If a problem is in NP, it must also be in P.

       ► True

► False

► unknown

Question No: 4    ( Marks: 1 )    – Please choose one

 What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

► Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)

       ► Lists require less space than matrices and they are faster to find the weight of an edge (v1,v2)

► Lists require more space than matrices and they take longer to find the weight of an edge (v1,v2)

► Lists require more space than matrices but are faster to find the weight of an edge (v1,v2)

Question No: 5    ( Marks: 1 )    – Please choose one

 If a graph has v vertices and e edges then to obtain a spanning tree we have to delete

► v edges.

► v – e + 5 edges

►  v + e edges.

       ► None of these

Question No: 6    ( Marks: 1 )    – Please choose one

 Maximum number of vertices in a Directed Graph may be |V2|

       ► True

► False

Question No: 7    ( Marks: 1 )    – Please choose one

 The Huffman algorithm finds a (n) _____________ solution.

       ► Optimal

► Non-optimal

► Exponential

► Polynomial

Question No: 8    ( Marks: 1 )    – Please choose one

 The Huffman algorithm finds an exponential solution

► True

       ► False

Question No: 9    ( Marks: 1 )    – Please choose one

 The Huffman algorithm finds a polynomial solution

► True

       ► False

Question No: 10    ( Marks: 1 )    – Please choose one

 The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.

► True

       ► False

   

Question No: 11    ( Marks: 1 )    – Please choose one

 The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.

► True

       ► False

Question No: 12    ( Marks: 1 )    – Please choose one

 Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.

► True

       ► False

Question No: 13    ( Marks: 1 )    – Please choose one

 Shortest path problems can be solved efficiently by modeling the road map as a graph.

       ► True

► False

Question No: 14    ( Marks: 1 )    – Please choose one

 Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.

► True

       ► False

   

Question No: 15    ( Marks: 1 )    – Please choose one

 Bellman-Ford allows negative weights edges and negative cost cycles.

► True

       ► False

Question No: 16    ( Marks: 1 )    – Please choose one

 The term “coloring” came form the original application which was in architectural design.

       ► True

► False

Question No: 17    ( Marks: 1 )    – Please choose one

 In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.

       ► True

► False

Question No: 18    ( Marks: 1 )    – Please choose one

 Dijkstra’s algorithm is operates by maintaining a subset of vertices

       ► True

► False

Question No: 19    ( Marks: 1 )    – Please choose one

 The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.

       ► True

► False

Question No: 20    ( Marks: 1 )    – Please choose one

 Consider the following adjacency list:

 

Which of the following graph(s) describe(s) the above adjacency list?

       ► 

 

 

 

 

 

Question No: 21    ( Marks: 1 )    – Please choose one

 We do sorting to,

► keep elements in random positions

► keep the algorithm run in linear order

► keep the algorithm run in (log n) order

       ► keep elements in increasing or decreasing order

Question No: 22    ( Marks: 1 )    – Please choose one

 After partitioning array in Quick sort, pivot is placed in a position such that

       ► Values smaller than pivot are on left and larger than pivot are on right

► Values larger than pivot are on left and smaller than pivot are on right

       ► Pivot is the first element of array

► Pivot is the last element of array

Question No: 23    ( Marks: 1 )    – Please choose one

 Merge sort is stable sort, but not an in-place algorithm

       ► True  (p#54)

► False

Question No: 24    ( Marks: 1 )    – Please choose one

 In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.

► Delete

       ► copy (p#57)

► Mark

► arrange

Question No: 25    ( Marks: 1 )    – Please choose one

 Dynamic programming algorithms need to store the results of intermediate sub-problems.

       ► True   p#75)

 

► False

Question No: 26    ( Marks: 1 )    – Please choose one

 A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute.

       ► O (q) (p= 84)

► O (1)

► O (n2)

► O (n3)

Question No: 27    ( Marks: 2 )

 Give a detailed example for 2-d maxima problem.

 

Question No: 28    ( Marks: 2 )

 Differentiate between back edge and forward edge.

 

Question No: 29    ( Marks: 2 )

 How the generic greedy algorithm operates in minimum spanning tree?

 

 

Question No: 30    ( Marks: 2 )

 What are two cases for computing  assuming we already have the previous matrix  using Floyed-Warshall algorithm?

 

 

 

 

Question No: 31    ( Marks: 3 )

 Describe Minimum Spanning Trees Problem with examples.

 

 

 

Question No: 32    ( Marks: 3 )

 What is decision problem, also explain with example?

 

 

 

Question No: 33    ( Marks: 3 )

 Prove that the generic TRAVERSE (S) marks every vertex in any connected graph exactly once and the set of edges (v, parent (v)) with parent (v) ¹F form a spanning tree of the graph.

 

 

Question No: 34    ( Marks: 5 )

 Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence?

 

 

 

 

 

Question No: 35    ( Marks: 5 )

 Prove the following lemma,

Lemma: Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) ∈ E. If this edge is a tree, forward or cross edge, then f[u] > f[v]. If this edge is a back edge, then f[u] ≤ f[v]

 

 

 

 

 

 

 

Question No: 36    ( Marks: 5 )

 What is the cost of the following graph?

VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers Spring 2010

Education In Pakistan © 2016