1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Algorithms I (CS214) - Final Exam
Exam Date: Saturday 20/5/2023 Allowed Time: 2 hours
Dr. Salwa Osama
What is a hash table?
If several elements are competing for the same bucket in the hash table, what is it called?
What is the hash function used in the division method?
What can be the value of m in the division method?
Using division method, in a given hash table of size 157, the key of value 172 is placed at position
What is the table size when the value of p is 7 in multiplication method of creating hash functions?
What is the average retrieval time when k has the same slot?
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.
What is indirect addressing?
What is the search complexity in direct addressing?
What is a hash function?
Which of the following is not a technique to avoid a collision?
What is the load factor?
What is simple uniform hashing?
In simple chaining, what data structure is appropriate?
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?
Maximum number of nodes in a binary tree with height k, where root is height 0, is
Quick sort algorithm is an example of
The minimum number of edges required to create a cyclic graph of n vertices is
Which of the following is example of not in-place algorithm?
Time required to sort "n" identical items of size m and n, is
Which of the following uses memorization?
Heap is an example of
Access time of a binary search tree may go worse in terms of time complexity up to
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
From the following sorting algorithms which algorithm needs the minimum number of swaps
From the following sorting algorithms which has the lowest worst case complexity?
Match the following pairs
I.
II.
III.
IV.
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
Time complexity on merging three sorted lists of sizes m, n and p is
Which of the algorithm design approach is used by Mergesort
Which of the following shortest path algorithm cannot detect presence of negative weight cycle graph?
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?
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?
If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?
What is the special property of red-black trees and what root should always be?
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
What are the operations that could be performed in O(logn) time complexity by red-black tree?
Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?
Pseudo Code
What is the below pseudo code trying to do, where pt is a node pointer an l
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
Dijkstra’s Algorithm is used to solve
What is the time complexity of Dijkstra’s algorithm?
Dijkstra’s Algorithm cannot be applied on
How many priority queue operations are involved in Dijkstra's Algorithm?
How many times the insert and extract min operations are invoked per vertex
The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to
What is running time of Dijkstra's algorithm using Binary min- heap method?
Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?
What will be the below pseudo code trying to do, where pt is a node pointer and root pointer?
Dijkstra's Algorithm is used to solve the following problems.
What is the time complexity of Dijkstra's algorithm?
Dijkstra's Algorithm cannot be applied on
How many priority queue operations are involved in Dijkstra's Algorithm?
How many times the insert and extract min operations are invoked per vertex?
The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to
What is running time of Dijkstra's algorithm using Binary min-heap method?
If b is the source vertex, what is the minimum cost to reach vertex f?
Identify the shortest path having minimum cost to reach vertex E if A is the source vertex
Dijkstra's Algorithm is the prime example for
