Analysis of Algorithm chapter 9 : Algorithm on Graph

Analysis of Algorithm chapter 9 : Algorithm on Graph

University

9 Qs

quiz-placeholder

Similar activities

ความรู้เกี่ยวกับ Dijkstra's Algorithm

ความรู้เกี่ยวกับ Dijkstra's Algorithm

University

7 Qs

Dynamic Programming_CSE

Dynamic Programming_CSE

University - Professional Development

10 Qs

Bertelsmann AI Track Quiz Initiative #1

Bertelsmann AI Track Quiz Initiative #1

University - Professional Development

10 Qs

Programming basic

Programming basic

University

10 Qs

Standard Algorithm Multiplication 2x3 Digit

Standard Algorithm Multiplication 2x3 Digit

5th Grade - University

14 Qs

Multi-Digit Multiplication Standard Algorithm

Multi-Digit Multiplication Standard Algorithm

5th Grade - University

10 Qs

Multiplication 2 Digit by 1 Digit Word Problems and Standard Algorithm

Multiplication 2 Digit by 1 Digit Word Problems and Standard Algorithm

5th Grade - University

13 Qs

Multiply With Standard Algorithm

Multiply With Standard Algorithm

5th Grade - University

14 Qs

Analysis of Algorithm chapter 9 : Algorithm on Graph

Analysis of Algorithm chapter 9 : Algorithm on Graph

Assessment

Quiz

Mathematics

University

Hard

Created by

วัชรศักดิ์ ศิริเสรีวรรณ

Used 5+ times

FREE Resource

9 questions

Show all answers

1.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

Which ones are the types of graph representation

Adjacency Matrix

Adjacency List

Edge List

Vertex List

2.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

Which statements about Graph Traversal are TRUE ?

Stack is usually applied on implementing Depth-First Search

Stack is usually applied on implementing Breadth-First Search

Priority Queue is usually applied on implementing Breadth-First Search

Kahn's Algorithm uses DFS to find the topological sorting

3.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

Media Image

Which one is not Topological sorting of this graph

D-B-A-C-E

D-A-B-C-E

A-B-C-D-E

B-C-D-A-E

4.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

Which statements about Topological sorting are true?

Kahn's algorithm starts on the node with zero in-degree

The order of removing in-degree comes from the queue

Sorting from DFS and Kahn's are usually same.

Kahn's algorithm is a Greedy algorithm

It is possible to find alternative sorting if some preferences in algorithm is changed

5.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Media Image

Based on Prim's algorithm, if the current spanning tree consists of node a and e, which edge will be added to the spanning tree next ?

ab

df

ef

af

6.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

which ones are the correct initializations of Dijkstra's algorithm if the starting node is X

D[i] = 0 for all node i except X

D[X] = 0

prev[X] = 0

visited[i] = FALSE for all node[i]

7.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

To find the shortest path start from node s on the graph with n nodes, which statement are True

There are n rounds for Dijkstra's algorithm

The maximum number of round for Bellman-Ford algorithm is n - 1

The minimum number of round for Bellman-Ford algorithm is 1

The relaxation occurs when d[i] < d[s] + w[s, i]

8.

FILL IN THE BLANK QUESTION

1 min • 1 pt

Media Image

This is a distance matrix of graph during step 4 of Floyd-Warshal algorithm. How many relaxations will there be in this step?

9.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

A* algorithm is used to find the optimal path from the starting point to the finish by calculating the function f(x) = g(x) + h(x). Which statements are True?

h(x) is defined by the distance from the point x to the finish

g(x) is defined by the cost of travelling the starting point to the point x

At each step, the points with the highest f(x) will be chosen for the next step.

If there are multiple best f(x), the one among these best f(x) with the lowest h(x) will be chosen