CS402 - Algorithmen & Datenstrukturen - QUIZ

CS402 · Algorithmen & Datenstrukturen

ETH Zurich

Practice 10 questions on CS402 - Algorithmen & Datenstrukturen at ETH Zurich. Free AI-generated quiz on uNotes — track your score, retake anytime.

Questions

1True or False: The topological ordering of a directed acyclic graph (DAG) is always unique.

2How many swaps are performed by Bubble Sort to sort the sequence [6, 5, 4, 1, 2, 3]?

3In a connected undirected graph, if an edge e is part of a cycle, can it be a cut edge?

4What is the time complexity to compute the degree of a vertex v from an adjacency matrix representation of a graph with n vertices?

5Given an even number n and the sequence [2, 1, 4, 3, ..., n, n-1], how many swaps does Insertion Sort perform to sort it?

6Using the provided Master Theorem, what is the tight asymptotic complexity of a recurrence T(n) = 2T(n/2) + n^0.5?

7True or False: If every vertex of an undirected graph G has even degree, then G has an Eulerian walk.

8Is a topological ordering required as a prerequisite for running Dijkstra's algorithm on a directed graph?

9In a Max-Heap structure, at which level (relative to the root at level 0) will you always find the second largest element?

10What is the running time of the dynamic programming algorithm used to partition an array of size n (summing to A) into three equal subsets?