Module 6

Question 1

This type of approach deals with a group of design methods base on transformation.

Answer 1

Transform and Conquer

Question 2

In transformation, the problem’s instance is _______.

Answer 2

Modified

Question 3

What are the three major variations of Transform and Conquer?

Answer 3

(RIP)
- Representation Change
- Instance Simplification
- Problem Reduction

Question 4

It is a transformation to a different representation of the same instance.

Answer 4

Representation Change

Question 5

It is a transformation into a simpler or more convenient instance of the same problem.

Answer 5

Instance Simplification

Question 6

It is a transformation to an instance of a different problem for which an algorithm is already available.

Answer 6

Problem Reduction

Question 7

What is the Transform and Conquer strategy flow?

Answer 7

Problem Instance -> Transform Variation -> Solution

Question 8

What problems involving lists are easier when the list is sorted?

Answer 8

(GPECS)
- Geometric Algorithms
- Presorting
- Element Uniqueness
- Computing the median (Selection Problem)
- Searching

Question 9

Efficiency of algorithms with pre-sorts depends on what?

Answer 9

Efficiency of Sorting

Question 10

These comparisons are necessary in the worst case to sort a list of size “n” by any comparison-based algorithm.

Answer 10

[log2 n!] = n log2 n

Question 11

These comparisons are also sufficient to sort array of size “n” by Merge Sort and Quick Sort.

Answer 11

n log2 n

Question 12

What is the efficiency of Searching with Pre-sorting?

Answer 12

Θ(nlog n) + O(log n) = Θ(nlog n)

Question 13

What is the efficiency of Element Uniqueness with Pre-sorting?

Answer 13

Θ(nlog n) + O(n) = Θ(nlog n)

Question 14

What is the efficiency of Computing for Mode with Pre-sorting?

Answer 14

Θ(nlog n) + O(n) = Θ(nlog n)

Question 15

The AVL tree was named after whom?

Answer 15

Adelson-Velsky and Landis

Question 16

Who are the two Soviet inventors that published the AVL Tree?

Answer 16

Georgy Adelson-Velsky and Evgenii Landis

Question 17

When was the AVL Tree published?

Answer 17

On 1962 in a paper titled “An Algorithm for the Organization of Information”

Question 18

In computer science, it is a self-balancing binary search tree.

Answer 18

AVL Tree

Question 19

In an AVL tree, the heights of the two child subtrees of any node differ by at most how many?

Answer 19

The heights of the two child subtrees of any node differ by at most ONE.

Question 20

In an AVL tree, if at any time the nodes differ by more than one, what is done to restore this property?

Answer 20

Rebalancing

Question 21

Lookup, insertion, and deletion all take how much time in both average and worst cases?

Answer 21

O(log n)

Question 22

AVL trees are similar to _____ because both support the same set of operations and take O(log n) time for the basic operations.

Answer 22

Red-black trees

Question 23

What are the 4 types of AVL rotations?

Answer 23

• Left Rotation
• Right Rotation
• Left-Right Rotation
• Right-Left Rotation

Question 24

An unbalanced tree has a height of at least how many?

Answer 24

Two

Question 25

It is performed if a tree becomes unbalanced by inserting a node into the right subtree of the right subtree ( \ becomes ^ )

Answer 25

Left Rotation

Question 26

It is performed if a tree becomes unbalanced by inserting a node into the left subtree of the left subtree ( / becomes ^ )

Answer 26

Right Rotation

Question 27

What rotation is a combination of the left rotation followed by right rotation? ( < becomes / becomes ^ )

Answer 27

Left-Right Rotation

Question 28

What rotation is a combination of the right rotation followed by left rotation? ( > becomes \ becomes ^ )

Answer 28

Right-Left Rotation