exam Algorithm

Last updated 12 months ago

59 questions

Library

exam Algorithm

Last updated 12 months ago

59 questions

1

Algorithms I (CS214) - Final Exam
Exam Date: Saturday 20/5/2023    Allowed Time: 2 hours
Dr. Salwa Osama

What is a hash table?

A structure that maps values to keys

A structure that maps keys to values

A structure used for storage

A structure used to implement stack and queue

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

Diffusion

Replication

Collision

Duplication

What is the hash function used in the division method?

h(k) = k/m

h(k) = k mod m

h(k) = m/k

h(k) = m mod k

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

Any prime number

Any even number

2ᵖ - 1

2ᵖ

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

19

72

15

17

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

14

128

49

127

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

\Theta(n)

\Theta(n^2)

\Theta(\log n)

\text{Big-O}(n^2)

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.

True

False

What is indirect addressing?

Distinct array position for every possible key

Fewer array positions than keys

Fewer keys than array positions

Same array position for all keys

What is the search complexity in direct addressing?

O(\alpha)

O(\log n)

O(1)

O(k \log n)

What is a hash function?

A function has allocated memory to key

A function that computes the location of the key in the array

A function that creates an array

A function that computes the location of the values in the array

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

Make the hash function appear random

Use the chaining method

Use uniform hashing

Increasing hash table size

What is the load factor?

Average array size

Average key size

Average chain length

Average hash table length

What is simple uniform hashing?

Every element has equal probability of hashing into any of the slots

A weighed probabilistic method is used to hash elements into the slots

Elements have random probability of hashing into any slots

Elements are hashed based on priority

In simple chaining, what data structure is appropriate?

Singly linked list

Doubly linked list

Circular linked list

Binary trees

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?

46, 42, 34, 52, 23, 33

34, 42, 23, 52, 33, 46

46, 34, 42, 23, 52, 33

42, 46, 33, 23, 34, 52

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

2^{k+1} - 1

2^{k-1}

2^{k+1} + 1

2^{k-1}

Quick sort algorithm is an example of

Greedy approach

Improved binary search

Dynamic Programming

Divide and conquer

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

n

n-1

n+1

2n

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

Bubble Sort

Merge Sort

Insertion Sort

All of the above

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

O(m\ n)

O(m\ +\ n)

O(m\ log\ m)

O(n\ log\ m)

Which of the following uses memorization?

Greedy approach

Divide and conquer approach

Dynamic programming approach

None

Heap is an example of

complete binary tree

spanning tree

sparse tree

binary search tree

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

O(n^2)

O(n\ log\ n)

O(1)

O(n)

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

0,1010,11,110,1111

0,101,11,1001,010

0,101,0001,100,1010

100,110,001,000,010

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

Bubble Sort

Quick Sort

Merge Sort

Selection Sort

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

Bubble Sort

Quick Sort

Merge Sort

Selection Sort

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

I-P, II-M, III-N, IV-O

I-O, II-P, III-M, IV-N

I-O, II-N, III-M, IV-P

I-O, II-N, III-P, IV-M

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

x = N+1

x=N(N-1)/2

x=N(N+1)/2

x=N^2

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

\Theta(m+n+p)

\Theta(m\cdot (m,n,p))

\Theta(max(m,n,p))

(m.n.p)

Which of the algorithm design approach is used by Mergesort

Branch and bound approach

Divide and Conquer approach

Dynamic approach

Greedy approach

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

Bellman Ford Algorithm

Floyd-Warshall Algorithm

Dijkstra's Algorithm

None of the above

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?

(A,G) then (G,C) then (C,B) then (C,F) then (F,E) then (F,D)

(A,G) then (A,B) then (B,C) then (A,D) then (C,F) then (F,E)

(A,G) then (B,C) then (E,F) then (A,B) then (C,F) then (D,E)

(A,G) then (A,B) then (A,C) then (A,D) then (A,D) then (C,F)

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

(A, G) then (G, C) then (C, B) then (C, F) then (F, E) then (E, D)

(A, G) then (A, B) then (B, C) then (A, D) then (C, F) then (F, E)

(A, G) then (B, C) then (E, F) then (A, B) then (C, F) then (D, E)

(A, G) then (A, B) then (A, C) then (A, D) then (A, D) then (C, F)

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

20

40

200

400

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

A color which is either red or black and root should always be black color only

Height of the tree

Pointer to next node

A color which is either green or black

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

to get logarithm time complexity

to get linear time complexity

to get exponential time complexity

to get constant time complexity

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

insertion, deletion, finding predecessor, successor

only insertion

only finding predecessor, successor

for sorting

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

no they are not preferred

What is a hash table?

A structure that maps values to keys

A structure that maps keys to values

A structure used for storage

A structure used to implement stack and queue

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

Diffusion

Replication

Collision

Duplication

What is the hash function used in the division method?

h(k) = k/m

h(k) = k mod m

h(k) = m/k

h(k) = m mod k

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

Any prime number

Any even number

2ᵖ - 1

2ᵖ

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

19

72

15

17

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

14

128

49

127

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

\Theta(n)

\Theta(n^2)

\Theta(\log n)

\text{Big-O}(n^2)

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.

True

False

What is indirect addressing?

Distinct array position for every possible key

Fewer array positions than keys

Fewer keys than array positions

Same array position for all keys

What is the search complexity in direct addressing?

O(\alpha)

O(\log n)

O(1)

O(k \log n)

What is a hash function?

A function has allocated memory to key

A function that computes the location of the key in the array

A function that creates an array

A function that computes the location of the values in the array

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

Make the hash function appear random

Use the chaining method

Use uniform hashing

Increasing hash table size

What is the load factor?

Average array size

Average key size

Average chain length

Average hash table length

What is simple uniform hashing?

Every element has equal probability of hashing into any of the slots

A weighed probabilistic method is used to hash elements into the slots

Elements have random probability of hashing into any slots

Elements are hashed based on priority

In simple chaining, what data structure is appropriate?

Singly linked list

Doubly linked list

Circular linked list

Binary trees

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.

42


23
52

33
34

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

46, 42, 34, 52, 23, 33

34, 42, 23, 52, 33, 46

46, 34, 42, 23, 52, 33

42, 46, 33, 23, 34, 52

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

2^{k+1} - 1

2^{k-1}

2^{k+1} + 1

2^{k-1}

Quick sort algorithm is an example of

Greedy approach

Improved binary search

Dynamic Programming

Divide and conquer

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

n

n-1

n+1

2n

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

Bubble Sort

Merge Sort

Insertion Sort

All of the above

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

O(m\ n)

O(m\ +\ n)

O(m\ log\ m)

O(n\ log\ m)

Which of the following uses memorization?

Greedy approach

Divide and conquer approach

Dynamic programming approach

None

Heap is an example of

complete binary tree

spanning tree

sparse tree

binary search tree

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

O(n^2)

O(n\ log\ n)

O(1)

O(n)

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

0,1010,11,110,1111

0,101,11,1001,010

0,101,0001,100,1010

100,110,001,000,010

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

Bubble Sort

Quick Sort

Merge Sort

Selection Sort

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

Bubble Sort

Quick Sort

Merge Sort

Selection Sort

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

I-P, II-M, III-N, IV-O

I-O, II-P, III-M, IV-N

I-O, II-N, III-M, IV-P

I-O, II-N, III-P, IV-M

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

x = N+1

x=N(N-1)/2

x=N(N+1)/2

x=N^2

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

\Theta(m+n+p)

\Theta(m\cdot (m,n,p))

\Theta(max(m,n,p))

(m.n.p)

Which of the algorithm design approach is used by Mergesort

Branch and bound approach

Divide and Conquer approach

Dynamic approach

Greedy approach

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

Bellman Ford Algorithm

Floyd-Warshall Algorithm

Dijkstra's Algorithm

None of the above

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?

(A,G) then (G,C) then (C,B) then (C,F) then (F,E) then (F,D)

(A,G) then (A,B) then (B,C) then (A,D) then (C,F) then (F,E)

(A,G) then (B,C) then (E,F) then (A,B) then (C,F) then (D,E)

(A,G) then (A,B) then (A,C) then (A,D) then (A,D) then (C,F)

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

(A, G) then (G, C) then (C, B) then (C, F) then (F, E) then (E, D)

(A, G) then (A, B) then (B, C) then (A, D) then (C, F) then (F, E)

(A, G) then (B, C) then (E, F) then (A, B) then (C, F) then (D, E)

(A, G) then (A, B) then (A, C) then (A, D) then (A, D) then (C, F)

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

20

40

200

400

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

A color which is either red or black and root should always be black color only

Height of the tree

Pointer to next node

A color which is either green or black

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

to get logarithm time complexity

to get linear time complexity

to get exponential time complexity

to get constant time complexity

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

insertion, deletion, finding predecessor, successor

only insertion

only finding predecessor, successor

for sorting

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

no they are not preferred

because of resizing issues of hash table and better ordering in redblack trees

because they can be implemented using trees

because they are unamced

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

insert a new node

delete a node

search a node

count the number of nodes

Dijkstra’s Algorithm is used to solve problems.

All pair shortest path

Single source shortest path

Network flow

Sorting

What is the time complexity of Dijkstra’s algorithm?

O(N)

O(N^3)

O(N^2)

O(logN)

Dijkstra’s Algorithm cannot be applied on

Directed and weighted graphs

Graphs having negative weight function

Unweighted graphs

Undirected and unweighted graphs

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

1

2

3

4

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

1

2

3

0

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

Total number of vertices

Total number of edges

Number of vertices - 1

Number of edges - 1

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

O(V)

O(VlogV)

O(E)

O(ElogV)

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

they are not preferred

because of resizing issues of hash table and better ordering in redblack trees

because they can be implemented using trees

because they are balanced

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;
}

insert a new node

delete a node

search a node

count the number of nodes

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

All pair shortest path

Single source shortest path

Network flow

Sorting

What is the time complexity of Dijkstra's algorithm?

O(N)

O(N^3)

O(N^2)

O(logN)

Dijkstra's Algorithm cannot be applied on

Directed and weighted graphs

Graphs having negative weight function

Unweighted graphs

Undirected and unweighted graphs

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

1

3

2

4

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

1

2

3

0

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

Total number of vertices

Total number of edges

Number of vertices - 1

Number of edges - 1

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

O(V)

O(VlogV)

O(E)

O(ElogV)

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

8

9

4

6

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

a-b-e

a-c-e

a-c-d-e

a-c-d-b-e

Dijkstra's Algorithm is the prime example for

Greedy algorithm

Branch and bound

Back tracking

Dynamic programming

exam Algorithm

exam Algorithm

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?

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 pairsI. O(\log\ n) (M) Heap sortII. O(n) (N) DFSIII. n\log(n) (O) Binary searchIV. O(n^2) (P) Selecting kth smallest elements

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 QuestionsFor the figure below, which is a correct order for Kruskal's minimum spanning tree algorithm to add edges to the minimum spanning tree? ∑ ∧ | B

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?

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

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