Module 6 Flashcards
This type of approach deals with a group of design methods base on transformation.
Transform and Conquer
In transformation, the problem’s instance is _______.
Modified
What are the three major variations of Transform and Conquer?
(RIP)
- Representation Change
- Instance Simplification
- Problem Reduction
It is a transformation to a different representation of the same instance.
Representation Change
It is a transformation into a simpler or more convenient instance of the same problem.
Instance Simplification
It is a transformation to an instance of a different problem for which an algorithm is already available.
Problem Reduction
What is the Transform and Conquer strategy flow?
Problem Instance -> Transform Variation -> Solution
What problems involving lists are easier when the list is sorted?
(GPECS)
- Geometric Algorithms
- Presorting
- Element Uniqueness
- Computing the median (Selection Problem)
- Searching
Efficiency of algorithms with pre-sorts depends on what?
Efficiency of Sorting
These comparisons are necessary in the worst case to sort a list of size “n” by any comparison-based algorithm.
[log2 n!] = n log2 n
These comparisons are also sufficient to sort array of size “n” by Merge Sort and Quick Sort.
n log2 n
What is the efficiency of Searching with Pre-sorting?
Θ(nlog n) + O(log n) = Θ(nlog n)
What is the efficiency of Element Uniqueness with Pre-sorting?
Θ(nlog n) + O(n) = Θ(nlog n)
What is the efficiency of Computing for Mode with Pre-sorting?
Θ(nlog n) + O(n) = Θ(nlog n)
The AVL tree was named after whom?
Adelson-Velsky and Landis
Who are the two Soviet inventors that published the AVL Tree?
Georgy Adelson-Velsky and Evgenii Landis
When was the AVL Tree published?
On 1962 in a paper titled “An Algorithm for the Organization of Information”
In computer science, it is a self-balancing binary search tree.
AVL Tree
In an AVL tree, the heights of the two child subtrees of any node differ by at most how many?
The heights of the two child subtrees of any node differ by at most ONE.
In an AVL tree, if at any time the nodes differ by more than one, what is done to restore this property?
Rebalancing
Lookup, insertion, and deletion all take how much time in both average and worst cases?
O(log n)
AVL trees are similar to _____ because both support the same set of operations and take O(log n) time for the basic operations.
Red-black trees
What are the 4 types of AVL rotations?
- Left Rotation
- Right Rotation
- Left-Right Rotation
- Right-Left Rotation
An unbalanced tree has a height of at least how many?
Two
It is performed if a tree becomes unbalanced by inserting a node into the right subtree of the right subtree ( \ becomes ^ )
Left Rotation
It is performed if a tree becomes unbalanced by inserting a node into the left subtree of the left subtree ( / becomes ^ )
Right Rotation
What rotation is a combination of the left rotation followed by right rotation? ( < becomes / becomes ^ )
Left-Right Rotation
What rotation is a combination of the right rotation followed by left rotation? ( > becomes \ becomes ^ )
Right-Left Rotation
