Design & Analysis of Algorithms Week 6,7 & 8 (finals)

What is transform-and-conquer

A group of techniques based on the idea of transformation to a problem that is easier to solve

What is the two-stage procedure for transform-and-conquer

Transformation: problem’s instance modified to be more amenable to solution

Conquering: problem solved

What are the three varieties of transformation

instance simplification: transforming an instance of a problem to an instance of the same problem with a special property that makes it easier to solve (presorting, gaussian elimination, rotation in AVL trees)

Representation change: implies changing one representation of a problem’s instance to another representation of the same instance (like a different data structure)

Problem reduction: calls for transforming given problem to another problem that can be solved by a known algorithm (reducing LCM to GCD, transforming max to mini, etc.)

What is presorting

instance-simplification technique where you sort the list first before processing it. (used in many geometric algorithms (close pr))

How to search with presorting

sort the array with an efficient sorting algorithm and then it scans it once to check for adjacent pairs. then apply binary search (n log n)

brute-force alternative just compares all the pairs of elements and is quadratic

What is gaussian elimination

instance-simplification technique that transforms a system of n linear equations in n unknowns into an upper-triangular coefficient matrix, then solves it using back substitution (start with last equation and move up) (cubic)

what is heap

a complete binary tree with keys (one per node) with full levels (last level not always) that satisfy the parental dominance requirement.

(all the keys are greater than or equal than to its children.)

what is heapsort

a theoretically important sorting algorithm based on arranging elements of an array in a heap and then successively removing the largest element from a remaining heap

what are the two approaches to heapsorting

1. Top-down: elements added or swapped DOWN the tree from the root towards the leaves (left to right)

2. bottom-up: searches for the correct element UP from the bottom leaves before swapping (right to left)

What is heapify

core algorithmic process of converting an unordered binary tree (array) into a valid heap data structure

What is an AVL tree

binary search trees that are always balanced to the extent possible for a binary tree. where the balance factor is at 1 (-1 for empty tree)

the balance is maintained by transformations of four types (R,L,LR,RL) called rotations.

what is an balanced search tree

attractiveness of binary search tree marred by the bad (linear) worst-case efficiency

what are the ideas necessary to keeping a tree balanced

1. restructuring it to maintain balance after an unbalancing insertion

2. allowing more than one key per node (2-3 trees)

what is space and time trade-off algorithms

algorithm design where trading space for time is more prevalent then the other way around. this is a well-known problem for both theoreticians and practitioners of computing

what are the two varieties of space time trade off algorithms

Input enhance: preprocesses input to store info to be used later in solving the problem (counting sorts and string searching algorithms)

pre-structuring/restructuring: uses extra space and preprocesses the input to facilitate a faster and more flexible access to the data (hashing, indexing)

what is string searching algorithms

computer tools designed to locate small strings (pattern) in a large body of text, if mismatch occurs realigns pattern one position to the right (x = m & n)

what are the three types of string searching algorithms

Knuth-Morris-Pratt (KMP): preprocesses pattern left to right to get useful info for later searching

Boyer-Moore: preprocesses pattern right to left and store info into two tables

Horspool: simplifies the Boyer-Moore algorithm by just using one table

what are the two tables in Boyer-Moore’s algorithm called

bad-symbol table: indicates how much to shift based on text causing a mismatch

good-suffix table: indicates how much to shift based on matched part of the pattern

what are the four shift cases in Horspool’s algorithm

1. if letter does not occur in pattern, shift by whole length

2. if letter does not occur in pattern but not its last character, align rightmost occurrence of the letter with the text’s letters

3. if letter is the pattern’s last one with no other characters among the first m-1, shift by whole length

4. if letter is the last character and other letter’s appear among the first m-1 align the rightmost of those with the text’s c

what is hashing

a very efficient method for implementing a dictionary and mapping keys into a 1D table(find, insert, delete)

what are the two types of hashing

Open hashing: each cell is a header of linked list of all keys hashed to it (separate chaining: keys are stored in linked lists OUTSIDE the hash table.

Closed hashing: one key per cell, in case of collision, finds another cell by linear probing or double hashing. (separate chaining: keys are stored inside hash table without linked list)

what is linear probing and double hashing for closed hashing

linear probing: use next free bucket

double hashing: use second hash function to complete increment

what is distribution counting

a special method for sorting lists of elements from a small set of possible values

what is the B-tree

a balanced search tree that generalizes the idea of the 2-3 tree by allowing multiple keys at the same node (pointer for every node)

what is the B+- tree

principal application of the B-tree that is used to keep index-like information about data stored on a disk (pointer for leaf nodes only)

what is the structural properties of the b-tree

1. root is either a leaf or has between 2 and m children.

2. every node except the root and the leaves has between the ceiling of m/2 and m children

3. tree is perfectly balanced with all its leaves at the same level.

how do you search a b-tree

start at the root and follow a chain of pointers down to the leaf with the search key, then search among that leaf’s keys because all keys are sorted in order of parental nodes and leaves, binary search can be used when there are enough keys.