Log inSign up for FREE
Library

exam Algorithm

Last updated 7 months ago
59 questions
Algorithms I (CS214) - Final Exam
Exam Date: Saturday 20/5/2023    Allowed Time: 2 hours
Dr. Salwa Osama

1

What is a hash table?

1

If several elements are competing for the same bucket in the hash table, what is it called?

1

What is the hash function used in the division method?

1

What can be the value of m in the division method?

1

Using division method, in a given hash table of size 157, the key of value 172 is placed at position

1

What is the table size when the value of p is 7 in multiplication method of creating hash functions?

1

What is the average retrieval time when k has the same slot?

1

Collisions can be reduced by choosing a hash function randomly in a way that is independent of the keys that are actually to be stored.

1

What is indirect addressing?

1

What is the search complexity in direct addressing?

1

What is a hash function?

1

Which of the following is not a technique to avoid a collision?

1

What is the load factor?

1

What is simple uniform hashing?

1

In simple chaining, what data structure is appropriate?

1

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
0:
1: 42
2:
3:
4: 23
5: 52
6:
7: 33
8: 34
9:
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

1

Maximum number of nodes in a binary tree with height k, where root is height 0, is

1

Quick sort algorithm is an example of

1

The minimum number of edges required to create a cyclic graph of n vertices is

1

Which of the following is example of not in-place algorithm?

1

Time required to sort "n" identical items of size m and n, is

1

Which of the following uses memorization?

1

Heap is an example of

1

Access time of a binary search tree may go worse in terms of time complexity up to

1

What will be the Huffman code for the letters a,b,c,d,e? If the probability are ½,1/4, 1/8,1/16,1/32

1

From the following sorting algorithms which algorithm needs the minimum number of swaps

1

From the following sorting algorithms which has the lowest worst case complexity?

1

Match the following pairs
  • I. O(\log\ n)     (M) Heap sort
  • II. O(n)     (N) DFS
  • III. n\log(n)     (O) Binary search
  • IV. O(n^2)     (P) Selecting kth smallest elements

1

What shall be value of x in the following pseudocode? x = 0; For (t = t; t <= N; t++) For p = l; p <= t; p++) x = x+1; EndFor EndFor

1

Time complexity on merging three sorted lists of sizes m, n and p is

1

Which of the algorithm design approach is used by Mergesort

1

Which of the following shortest path algorithm cannot detect presence of negative weight cycle graph?

1

For the figure below, starting at vertex A, which is a correct order for Prim's minimum spanning tree algorithm to add edges to the minimum spanning tree?

1

Graph Algorithms Questions


For the figure below, which is a correct order for Kruskal's minimum spanning tree algorithm to add edges to the minimum spanning tree? ∑ ∧ | B

1

If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?

1

What is the special property of red-black trees and what root should always be?

1

Why do we impose restrictions like . root property is black . every leaf is black . children of red node are black . all leaves have same black

1

What are the operations that could be performed in O(logn) time complexity by red-black tree?

1

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

1

Pseudo Code
What is the below pseudo code trying to do, where pt is a node pointer an l root pointer?
redblack(Node root, Node pt) : if (root == NULL) return pt if (pt.data < root.data) { root.left = redblack(root.left, pt); root.left.parent = root; } else if (pt.data > root.data) { root.right = redblack(root.right, pt); root.right.parent = root; } return root

1

Dijkstra’s Algorithm is used to solve problems.

1

What is the time complexity of Dijkstra’s algorithm?

1

Dijkstra’s Algorithm cannot be applied on

1

How many priority queue operations are involved in Dijkstra's Algorithm?

1

How many times the insert and extract min operations are invoked per vertex

1

The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to

1

What is running time of Dijkstra's algorithm using Binary min- heap method?

1

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

1

What will be the below pseudo code trying to do, where pt is a node pointer and root pointer?
redblack(Node root, Node pt) { if (root == NULL) return pt; if (pt.data < root.data) { root.left = redblack(root.left, pt); root.left.parent = root; } else if (pt.data > root.data) { root.right = redblack(root.right, pt); root.right.parent = root; } return root;
}

1

Dijkstra's Algorithm is used to solve the following problems.

1

What is the time complexity of Dijkstra's algorithm?

1

Dijkstra's Algorithm cannot be applied on

1

How many priority queue operations are involved in Dijkstra's Algorithm?

1

How many times the insert and extract min operations are invoked per vertex?

1

The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to

1

What is running time of Dijkstra's algorithm using Binary min-heap method?

1

If b is the source vertex, what is the minimum cost to reach vertex f?

1

Identify the shortest path having minimum cost to reach vertex E if A is the source vertex

1

Dijkstra's Algorithm is the prime example for