Given two polygons P and Q, with n_P and n_Q extreme points.

Assume P and Q are both given with their list of extreme points in, e.g., the CW order, starting with an arbitrary extreme point.

What is the best complexity of their intersection check, i.e., checking whether they intersect or not.

What is the most expensive phase in Graham's Scan in terms of the runtime?

What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap.

The total time required for this is: 

What is the time complexity of Build Heap operation? 

We work with dynamic tables and we use the following common heuristic:

Let  

NUM_i  = number of items stored after the ith operation

Which potential function (function phi) do you define:

Consider the following program

For i from 1 to n

                 Makeset(i)

For i from 1 to n-1

                 Union(i, i+1)

Assume that the disjoint sets data is implemented as disjoint trees with union by rank heuristic

What is the number of trees in the forest and the maximum height of a tree after executing this code?

In BFS, how many times a node is visited in a directed graph?

Consider the following graph.

The following sequences of depth first search are proposed:

A. abfchg

B. abghbc

C. abcghf

D. abfhgc 

Which of the following is correct?

The off-line minimum problem asks us to maintain a dynamic set T of elements from the domain {1; 2; ... ; n} under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in {1; 2; ... ; n} is inserted exactly once. We wish to determine which key is returned by each EXTRACTMIN call. Specifically, we wish to fill in an array extracted[1..m], where for i = 1; 2; ... ; m; extracted[i] is the key returned by the ith EXTRACT-MIN call. The problem is ”off-line” in the sense that we are allowed to process the entire sequence S before determining any of the returned keys a. In the following instance of the off-line minimum problem, each INSERT is represented by a number and each EXTRACT-MIN is represented by the letter E:

3, E, 7, 1, 4, E, E, 5, 2, 8, E, 6, E, 9, E, 15.

Fill in the correct values in the extracted array with the following format: 1, 2, 3, ... (no punctuation at the end)