1
Q
Name three desirable properties of a good algorithm.
A
Algorithm should be:
- Correct
- Efficient
- Easy to implement
These goals might not be and often are not simultanously achievable.
2
Q
How is mergesort algorithm implemented?
A
- Based on divide-and-conquer approach.
- Breaks array into two halves and sorts both halves
- Once subproblem is 2 element array it starts merging back arrays so that they are sorted during merge. After bubbling up the recursion array is sorted.
- Needs an additional temporary array for merging.
3
Q
How is quicksort algorithm implemented?
A
- Divide and conquer approach through partitioning.
- Taking an element and partitioning the array to “lower than” and “greater than”.
- Recursively repeating partitioning on subarrays
- When subarrays have 1 element, sorting is done.
4
Q
On which algorithm is shell sort based?
A
- It is based on insertion sort algorithm.
5
Q
How is shell sort algorithm implemented?
A
- It uses so cold h-sort approach to introduce partial order in the array.
- Value h is first calculated “while (h < N/3) h = 3*h + 1”
- In every loop value h = h/3 - at the end we have h = 1 and that is regular insertion on partially sorted array.
- For wrongly set h can be slow
6
Q
Running time properties of mergesort algorithm?
A
- Mergesort is optimal compare-based sorting algorithm.
- Average, worst and best case run in O(NlogN) complexity
- Needs auxilliary array. Additional space O(N)
- For already sorted is O(N) if there is a check for if array is already sorted.
7
Q
Running time properties of quicksort algorithm?
A
- Average O(NlogN)
- Worst O(N2) when array is already sorted. Randomization before sorting is done to prevent.
- Can be improved by cutoff to insertion sort for smaller arrays
- For arrays with lot of duplicates can be significantly improved by partitioning to “smaller than”, “equal”, “larger than”.
8
Q
Ways to improve default quicksort approach?
A
- Cutoff to insertion sort for 15 element subarrays
- Picking the partition element. Median of three.
- Partitioning to “lower than”, “equal”, “greather than” for arrays with repeateable keys.
9
Q
What are optimizations for the mergesort algorithm?
A
- Cutoff to insertion sort
- Check for already sorted arrays.
10
Q
What are run-time properties of selection sort algorithm?
A
- Average, best, worst time: O(N2)
- Approx N2/2 compares and N swaps
- Doesn’t need additional memory
- Running time is not sensitive to input
11
Q
What are running time properties of insertion sort algorithm?
A
- Average case is O(N2) with N2 swaps for unsorted array
- Worst case is O(N2) with N2 swaps for random array
- Best case is O(N) with 1 swap for already ordered array.
- It doesn’t need additional memory
- Dependent on properties of input
12
Q
What are running time properties of shell sort algorithm?
A
- It is in practice O(N4/3), O(N5/4) … but no proof is given
- In practice used due to its simplicity and acceptable speed for moderately large arrays.
13
Q
Define:
heuristic
A
Heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. In a way, it can be considered a shortcut.
In general, every type of problem will have its own set of heuritics.
14
Q
Give one example of heuristics?
A
An example of heuristics is using Manhattan distance heuristic function in the problem of finding the shortest path in order to decide on the next step among the list of options.
15
Q
What is the difference between the algorithmic problem and an instance of an algorithmic problem.
A
Algorithmic problem is specified by describing the complete set of instances it must work for and produce valid solution to all of them.
Sorting is an algorithmic problem. Sorting of an array of integers is an instance of sorting problem.
This is important since recognizing the general problem in an instance is the first step to solving it.
16
Q
Fundamental difference between algorithm and heuristic?
A
There is a fundamental difference between algorithms, which always produce correct result, and heuristics, which may usually do a good job but without providing any guarantee.
17
Q
Give one example where
heuristic yields very unoptimal solution.
A
If points we are trying connect are lying on a flat line and we start in the middle then it will, instead of goinglinearly, it will jump towards the outside which is very unoptima.
In general, if distances between nearest neighbours become bigger and bigger towards the end of execution, it is most probably unoptimal
18
Q
Which are three forms of algorithmic notation?
A
Three forms of algorithmic notation (going from informal to formal):
- English
- Pseudo code
- Implementation in a particular programming language.
Common mistake is to use more formal structure to express not so formal level of communication. E.g. english explanation presented through pseudo code structure.
19
Q
Which are two parts of algorithmic problem specification?
A
Two parts of algorithmic problem specification are:
- Set of allowed input instances.
- Required properties of the algorithm output.
20
Q
What can be done with set of allowable instances in the specification of an algorithmic problem in order to make it easier to find a correct solution?
A
Narrowing down problems to a more simple allowable instances is a standard way to simplify reasoning about algorithms.
Example would be reasoning about a tree structure instead of full graph or single dimensional problem instead of 2-dimensional one.
21
Q
What is the best way to prove one algorithm incorrectness?
A
The best way to prove incorrectness of an algorithm is by finding a counter-example for which algorithm is not correct.
Counter example is the case of input sequence for which correct solution exists but algorithm doesn’t find it.
22
Q
Which are two important properties of counter-examples?
A
Two properties of a good counter-example are:
- Verifiability
- Simplicity
23
Q
Which are good approaches in finding counter-examples?
A
- Think small.
- Think exhaustively
- Hunt for the weakness
- Go for a tie - when algorithm has to decide on two options.
- Seek extremes
24
Q
Inductive proof steps are?
A
- Prove the idea for the basic case n = 1, n = 2
- Assume the idea is valid until the “n - 1” case
- Prove that it is still valid for the “n” case.
25
Inductive reasoning is important in algorithmic theory because ...
Inductive reasoning comes natural with the recursive nature of lot of algorithmic problems.
26
Two major classes of summations are?
Two major classes of summation formulas are:
* Arithmetic progression
* Geometric progression
27
Explain:
Arithmetic progression
Arithmetic progression of summation is the case where difference between consecutive terms is constant.
In general for thr p-th degree summation it yields (p+1)-th degree sum.
S(n,p) = SUMi -> n(ip) = Theta(np+1)
Concrete
SUMi -> n(i) = n(n+1)/2 ~ Theta(n2)
28
Explain:
Geometric progression
Geometric sequence of numbers if such a sequence where every next term is found by multiplying the previous one by a fixed non-zero multiplier called *common ratio*.
An example:
G(n, a) = SUMi = 0 -> n(ai) = a(an+1 - 1) / (a - 1)
In general
G(n, a) ~ Theta(an+1), a \> 1
29
Explain:
Modeling of an (algorithmic) solution.
Modeling is the process of formulating the solution of a problem in terms of precisely described well-understood and already resolved problems and solutions.
## Footnote
Proper modeling can hugely reduce the need for finding complex solutions by reusing existing solutions.
It is important to understand that modeling often has to happen on the abstract level of discussion about general structures and solutions which are not bound to any domain.
30
Modeling with *permutations*.
Permutations - arrangements or ordering of items.
For example: {1,2,3,4} and {2,3,1,4} are two permutations of the same set.
Usually, problem modeled by permutations is seeking for **ordering**, **sequence**, **tour**, **arrangement**
31
Modeling with *subsets*.
Subset - represent selection from a set of items.
For example: {1,2,4} and {3} are two distinc subsets of {1,2,3,4}
Usually, subsets are modeling the problem which seeks for **cluster**, **collection**, **group**, **packaging**, **committee**
32
Modeling with *trees*.
Trees represent hierarchical relations between items.
For example tree would be used to model family tree.
Problems with solutions modeled as trees usually are seeking for **hierarchy**, **dominance relationship**, **taxonomy**, **ancestor/descendant relationship**
33
Modeling with *graphs*.
Graphs are representing arbitrary relationship between pairs of items.
For example: road network in a city is modeled by graphs.
Usually, graphs are model of a solution when we seek for **network**, **circuit**, **web**, **relationship**
34
Modeling with *points*.
Points are representing location in some geometric space.
For example: list of monuments you want to visit in a city.
Usually they appear in the solution whenever we seek for instance **sites**, **locations**, **positions**
35
Modeling with *polygons*.
Polygons are representing some physical areas.
For example: finding neighbouring city borders.
They appear usually when we seek for **shapes**, **regions**, **configurations**, **boundaries.**
36
Modeling with *strings*.
Strings represent sequence of characters or patterns.
For example: Finding all names that start with "Iv"
Usually they appear when we are expected to find **text**, **characters**, **patters**, **labels.**
37
Explain recursive nature of standard model objects.
In general, removing an element from the set of elements of the model will produce a smaller object which will represent a smaller problem than the original full one.
38
Explain:
Knapsack problem
Imagine a tief with a knapsack breaks into a store. How would tief pick the items from the store to fill the knapsack so that it is full. Every item has size and the knapsack has a total capacity.
Given the set of numbers, find the subset that adds up to a certain target.
For example: items are of sizes S= {1, 2, 5, 9, 10} and the knapsack is of target capacity T=22.
39
Two most important tools for analysis of algorithm efficiency without actually implementing them are?
* RAM model of computation.
* Asymptotic analysis of worst-time complexity.
It is important to understand that target of these models is to analyze algorithm in a machine independent way. They are both approximations of the real machine but excellent for understanding overall properties of algorithms.
40
Which are properties of RAM (Random Access Machine) model of computation?
* Every simple operation (+, -, \*, =, /, if, call) takes one step.
* Loops and subroutines are not simple operations.
* Reading and writing of memory takes one step.
41
# Define:
Worst-case complexity.
The *worst-case complexity* of an algorithm is a function defined by the maximum number of steps algorithm takes for any input instance of size n.
For example: Sorting of an input array may be very different for different input instance.
42
Why is worst-case complexity useful metric in algorithm analysis?
* useful as pessimistic view
* easy to obtain in analysis and math of it is usually straightforward.
43
# Define:
Best-case complexity
*Best-case complexity* of an algorithm is a function defined by the **minimum number of steps** algorithm takes for input instances of any size n.
44
# Define:
Average-case compexity
*Average-case complexity* of an algorithm is a function defined by the average number of steps algorithm takes for input instances of any size n.
45
Explain the need for asymptotic notation of the algorithm run-time complexity.
Thinking in terms of exact behavior of an algorithm for any input instance is messy and doesn't expose really the overall behavior and tendency of the algorithm in a clean way.
Because of this we introduce approaximations that express the *upper* and *lower* bounds of run-time complexities which give enough information and hide the messy details.
46
Which are and what is the meaning of asymptotic bounding functions?
* g(n) = **O**(f(n)) - means that C\*f(n) is an **upper bound** on g(n)
* g(n) = **Ω**(f(n)) - means that C\*f(n) is a **lower bound** on g(n)
* g(n) = **Θ**(f(n)) - means that f(n) is a **tight bound** on g(n)
* C1\*f(n) is an upper bound
* C2\*f(n) is a lower bound
All of these relationships should hold after some input size threshold n0.
47
Standard classes of asymptotic bounds of algorithms?
Small amount of classes fit for most of practical algorithms:
* constant - f(n) = 1
* logarithmic - f(n) = log(n)
* linear - f(n) - n
* linearithmic - f(n) = n\*log(n)
* quadratic - f(n) = n2
* cubic - f(n) - n3
* exponential - f(n) = cn
* factorial - f(n) = n!
n! \>\> cn \>\> n3 \>\> n2 \>\> n\*log(n) \>\> n \>\> log(n) \>\> 1
48
Constant time complexity
f(n) = 1
Constant upper bound means that number of operations algorithm takes for any input n constant number of steps.
Examples:
* access n-th element of array by index.
49
Logarithmic time complexity
f(n) = log(n)
Logarithmic time complexity appears in algorithms where in every next step the size of the problem is halved or doubled.
Examples:
* binary search of an ordered array.
* finding an element in a fairly balanced binary search tree.
* fast exponentiation by an = (an/2)2 means we need O(log(n)) multiplications.
50
Linear time complexity
f(n) = n
Running time of such an algorithm is linearly proportional to the number of elements which means that algorithm has to go one or more times over all elements of the array.
Examples:
* checking if array is sorted.
* identify biggest item
* calculate average of the values in an array.
51
Linearithmic time complexity
f(n) = n\*log(n)
This one grows a bit faster than linear since number of times all items are visited depends on the size of thea array and it is log(n) growth.
Examples:
* divide-and-conquer sorting like quicksort and mergesort
52
Quadratic time complexity
f(n) = n2
Quadratic time complexity is property of algorithms that need to go over all or almost all elements of input for every element of the input.
For two inputs n and m it would be n\*m
Examples:
* selection sort algorithm
* insertion sort algorithm
* string pattern matching O(n\*m)
53
Cubic time complexity
f(n) = n3
Cubic time complexity is property of algorithms which enumerate over all triples of an n-element input instance.
Examples:
* matrix multiplication
54
Exponential time complexity
f(n) = cn, c \> 1
Exponential complexity is property of algorithms that enumerate of all subsets of certain set, in case of 2n.
Examples:
* generate all subsets of a set.
55
Factorial time complexity
f(n) = n!
Factorial time complexity is property of algorithms that have to enumerate all permutations of a set of n items.
Examples:
* all permutations of a set in a brute force approach.
56
Why are back of the envelope estimations important?
In relation to algorithm execution time.
Because thinking about algorithms is often about estimating how long would it take to execute certain algorithm with the growth of the size of the problem, usually in a complex setup.
In practice, for a fairly **big amount of elements** to be processed, turns out that **linear** or **nearly linear like O(n\*log n)** is the only satisfying complexity.
57
Abstract data type
vs.
Data structures
In a vague way.
* Abstract data type* is a data type which is defined only by the publicly exposed interface and the mathematical model of effects on its internal state which changes as a consequence of the use of the external interface.
* Concrete data structures* are the underlying data structures which are used to implement the public interface of an abstract data type. They are replaceable and replacement should not affect the correctness of implementation.
58
Regarding the memory organization of data structures, we can divide them into ... ?
* Contiguously-allocated structures
* memory is allocated in single slabs
* examples are **arrays**, **matrices**, **heaps** and **hash tables**
* Linked data structures.
* memory is allocated in scattered chunks and connected through pointers
* examples are **lists**, **trees**, **graph adjacency lists**.
59
Define *array* as a data structure.
Array is the fundamental continuously-allocated data structure. It is a structure of predefined number of fixed size data elements.
Because of the fixed size of the elements of an array it is possible to always calculate the position and directly access any element of it.
60
Good sides of arrays are?
* Constant-time access to a given index due to its structure.
* Space efficiency since they contain only data and not meta information unlike pointer based data structures.
* Memory locality which is helpful for good low level caching use.
61
Downsides of array data structure are?
* Limited and predefined capacity (solvable by dynamic allocation approach)
62
Arrays with dynamic allocation.
Problem of fixed size of the array can be fixed by doubling the array when capacity is not sufficient and halving when oversized. When doubling the size we have to copy the content of the old array into the new one.
Indeed, half of the elements are being copied once, quarter two times and so. At the end amount of work in managing of the size of array is *O(n).*
M = Σ(i\*n/2i)i = 1 -> log(n) = n\*Σ(i\*/2i)i = 1 -> lg(n) \<= 2n
63
Pointer data type is?
Pointer data type is type of the values which represent memory addresses. It is used to store and move around references to data instead copies of data itself.
64
Advantages of linked data structures?
* No need for dynamic size management, overflow can not happen unless we are out of memory.
* Insertions and deletions are simple, not as in continguous data structures.
* With large records, moving pointers to data is easier and more efficient than moving data itself.
65
Disadvantages of the linked data structures?
* Take additional memory to store pointers.
* Do not allow for efficient random access to elements.
* Worse memory locality and lower level cache benefits.
66
Explain single-linked list data structure.
* standard operations on a list (add, remove, find)
* structure of a list and implementation
* graphical, boxed, notation
* different variants (doubly-linked i.e.)
67
What are sentinel values?
Sentinel values are values used in implementation of algorithms for several reasons.
* Increasing speed of operations
* Reducing algorithm complexity and simplifying implementation
* Arguably increasing data structure robustness (not convinced?)
Examples: In binary tree it can be used to avoid expensive comparisons with NULL. In arrays it can be used to prevent constatnt checking for the end of array.
68
Containers
vs.
Dictionaries?
* Containers* are abstract data types which are collections of objects and rules about their access order.
* Example: stacks, queues
* Dictionaries* are abstract data types which are collections of objects which are accessed by the key which was used while storing them. Known as well as associative maps, symbol tables.
* Example: hash map, binary search tree
69
# Define:
Stack data type.
Stack is a container and an abstract data type which is defined by the:
* ***push*** and ***pop*** abstract operations on the state of the stack
* push(x, s) - put x on stack s
* pop(s) - get an element from the stack s
* **LIFO** order in which elements are returned after they are put on the stack.
LIFO - Last In First Out
70
Which are some of the situations where LIFO order of access of the stored data is natural or generally useful?
* generally useful when we don't care about the order like for batch jobs.
* generally applicable to the process of reversing order.
* naturally found in algorithms that use recursion
* recursion is kind of putting function arguments on a stack.
* people getting in and out of elevator
* bullets in the stack of a gun.
71
Stack implementation, linked-lists vs arrays?
Stack can be implemented both based on linked-lists and arrays in a very simple way.
All the pluses and minuses to both of the underlying representations apply.
In the case of arrays it is important to ask if how will size behave over the time of execution.
72
# Define:
Queue data type.
A queue is a container and abstract data type defined by the:
* **enqueue** and **dequeue** abstract operations.
* enqueue(x, q) - add element at the end
* dequeue(q) - remove element from the top
* **FIFO** order of retrieval of enqueued elements.
FIFO - First In First Out
73
Which are some situations where FIFO order of access of the stored elements is natural or generally useful?
* natural for the list of arrived messages to read
* natural for the people on the shop counter.
* everywhere where order of processing is important.
74
Queue implementation, linked-lists vs arrays?
With linked-lists we need to store the pointer to the tail. As well we need doubly linked list to move towards the head. Due to this it takes more space for maintaining the structure.
With arrays it is generally question if we can go with statically allocated array or we will lose performance on copying due to dynamic allocation.
75
# Define:
Dictionary data type.
Dictionary is an abstract data type which is used to efficiently insert, locate and delete elements based on one or more keys.
* **insert**, **find** and **delete, max**, **min**, **successor**, **predecessor** are basic abstract operations
They are as well called symbol tables.
They belong to the most fundamental data structures.
76
Common questions for choosing the right implementation of the dictionary.
* How many items will you have in your data structure?
* are you going to run out of memory?
* Do you know relative frequencies of insert, find and delete operations and which are their asymptotic behaviours?
* focus on one of them can vastly simplify the implementation and improve performance.
* Is access pattern for keys uniform and random?
* Is it critical that every operation is fast or that amortized performance is best possible?
77
Common underlying data structures which implement dictionaries are ...?
* unsorted list or array
* sorted list or array
* hash table
* binary search tree
* B-trees
* skip lists
78
Dictionary implementation with sorted and unsorted arrays?
* Asymptotic analysis of basic operations.
* Unsorted
* insert and delete are constant O(1)
* searching and traversing is O(n)
* Sorted
* insert and delete are linear O(n)
* searching is fast O(log n) based on binary search
* traversing is O(1) since we always know the next one.
79
Dictionary implementation with linked lists?
Single-linked, doubly-linked.
Like with sorted and unsorted arrays modification and searching are orthogonal.
Linked lists have option to optimize access a bit by being single or doubly linked.
No possibility for binary search.
80
# Define:
Binary Search Tree
Binary Search Tree (BST) is a linked data structure which allows **flexible updates** and **fast search** in the same time.
BST is structured so that we can access the median element of the structure over and below the current element. This way we do **binary search in a linked data structure**.
BST can be (1) **empty** (2) having a **root with two subtrees** to which root element is pointing.
Given root x, all nodes in the **left subtree are lower than x** and all nodes in the **right subtree are bigger than x**.
81
Overall Binary Search Tree implementation?
Overall, as defined, BST has
* a node which contains
* data
* link to the left subtree whose keys are smaller
* link to the right subtree whose keys are bigger.
* eventually pointer to parent.
82
BST implementation recursion vs iterative
Recursive implementation is easer to mathematically reason and simpler in implementation.
Iterative is a bit more performant.
83
BST implementation of insert()
* searching within the tree for a position to attach the new node.
* new one always goes to the bottom of the tree with complexity **O(h)** - **h** is the **height of the tree**.
* far left or far right are always an option for smallest and biggest entries.
* if ordered set is inserted then we will end up with a tall skinny tree which will actually be a list with **O(n)** complexities.
* we need to randomize the set before inserts or use some balanced tree form.
84
BST implementation of find()
* O(h) complexity of finding a node within the tree.
* Needs comparison in every node through which it passes.
85
BST implementation of remove()
* A bit trickier operation because we have to rewrite part of the tree. There are 3 cases.
1. Delete node without children - just remove it
2. Delete node with one child - just move child to the parent of a parent
3. Delete node with two subtrees
1. Find the minimum of the right tree and set it as replacement
2. Remove the minimum node from the right subtree
3. Set the right node of replacement as right node of deleted (without removed minimum)
4. Set the left node of replacement as the left node of deleted.
86
BST implementation of min/max
* Navigate to the far left/right of the tree and return the found one.
87
BST implementation of successor/predecessor.
* Navigate to the element whose succ/pred we search for
* if not found return null / better to check before diving into recursion.
* if found and has right/left tree take the min/max of the respective trees.
* if found and has no right/left tree
* return nil from the bottom
* on the way up replace the return value with the first one which is bigger/smaller
88
Sorting by the use of BST
Inserting elements in the BST which is by nature able to easy provide retrieval of elements in a sorted order is one way to sort elements.
1. Traverse the tree in-order
2. Start from a minimum and take successors
3. Start from a minimum and delete next minimum from the tree.
89
# Define:
Priority queue data structure.
*Priority queue* is a **container** data structure which provides means to work with in-order processing of data but with **more flexibility than traditional sorting methods**.
It is **much more cost-effective** to insert element into a priority queue **than to resort** the data every time new element is inserted.
* insert
* find minimum/maximum
* delete minimum/maximum
90
Basic questions to ask related to priority queues.
* Is size of the queue predefined or variable
* What are other operations needed.
* Is it needed to change the priority of the elements in the queue?
* in this case you need to take element from the queue based on their key and reinsert again.
91
Compare:
Basic implementations of priority queues based on
* an unordered array or list
* an ordered array or list
* a balanced binary search tree
Slight optimization in all the cases can be done by keeping track of the minimum/maximum element to retrieve it fast.
Evaluating three basic operations:
* **insert**: UA - O(1), OA - O(n), BST - O(log n)
* **find-minimum**: UA - O(1), OA - O(1), BST - O(1)
* **delete-minimum**: UA - O(n), OA - O(1), BST - O(log n)
92
Explain:
Standard implementations of priority queues?
* sorted array or list
* balanced binary search tree
* binary heaps
* bounded hight prioirity queues
* Fibonacci and pairing heaps
93
# Define:
heap data structure.
Heap is a tree-based data structure which satisfies the heap property. Such trees are called **heap-labeled trees** and satisfy property that parent-child relations are defined consistently through the tree. If parent is always bigger than all its childrer we get the maximum element on top of the tree, otherwise the minimum one. Thus the names *max-heap* and *min-heap*.
* Heap is usualy implemented as array.
* Heaps are usualy used to implement prioirity queues.
94
Explain:
Usages of the heap data structure.
* **Heapsort**: One of the best sorting methods being *in-place and with no quadratic worst-case scenarios*.
* **Selection algorithms**: A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap.
* **Graph algorithms**: By using heaps as *internal traversal data structures*, run time will be reduced by polynomial order. Examples of such problems are Prim's *minimal-spanning-tree* algorithmand *Dijkstra's shortest-path* algorithm.
* **Priority Queue**: Having heap being structured according to value of the priority of elements allow to pick minimal or maximal element very efficiently.
95
Explain:
Representing heaps in arrays.
* root on position 1
* without compressions
* children of root on positions 2 and 3
* in general, children of the i-th node are on 2i and 2i + 1 positions.
* needs 2n elements array
* with compression (element goes on the first free position)
* n elements
* n-th element has children on 2\*n and 2\*n + 1
96
Explain:
Tree representation in array vs linked representation.
* linked structures are more flexible for inserts and deletes.
* array representation is very inflexible when trees need to be restructured since that means moving a lot of elements and finding new places for them.
* arrays are more optimal memory-wise since for an int we don't need to drag two more pointers.
97
Explain:
Construction of the heap (array based implementation) and its operations.
* put inserted element on the first free place in array (starting from index 1 for root)
* if there are children, bubble down the element by swapping it with its left child as long as child is smaller/bigger than it
* this is a **O(log n)** operation.
* finding minimum/maximum is easy since it is always at index 1 for a non-empty heap
* removing min/max
* take element at index 1
* replace the taken one with the last of array
* bubble down the element until its place.
98
Analyse:
Asymptotic properties of heaps.
* inserting - O(log n)
* finding min/max - O(1)
* removing min/max - O(log n)
* construction O(n\*log n)
Because of these properties, it is used in heapsort approach as a way to sort an array in an optimal worst-case complexity and inplace.
* heapify on an array.
99
Explain:
Bounded height priority queue.
(for limited number of priorities)
Bounded priority queue is a data structure used when there is a limited number of priorities to be managed.
It consistes of an array of queues, one for each priority and a pointer to the current minimum priority.
* **Inserting,** and element with priority K, inserts element in the K-th queue and updates the value of the top
* **Removal**, we just remove from the queue of that prioirty and update top pointer to the next minimal.
100
Key concept hashing is?
Key concept of hashing is that a more comlex object or **content gets hashed to an integer** which then represents it.
Big object gets represented by smaller representation which can be **manipulated in constant time in algorithms**.
Hashing is done by a so called **hashing function**.
101
Usages of hashing concepts?
* implementation of dictionary data structures based on hashing.
* caching based on the content.
* finding duplicate records
* finding similar substrings (Rabin-Karp algorithm)
* Geo hashing.
102
Explain:
Properties of hashing functions.
* **Determinism** - same content has to produce same hash value
* **Defined range** - to which output range the input range is mapped.
* **Uniformity** - hash function should map input range uniformly to the output range. Important in relation with the size of the data structure.
* **Data normalization** - is the input range normalized before hashed so that "Ivan Jovanovic" and "ivan jovanovic" produce the same hash.
103
Hashing functions for strings.
Given the size of the alphabet A, for any string we can create a hash function producing the integer in number system with the base of A where base factors are multiplied by the values of the characters at the appropriate positions.
H(S) = Σi=0->|S|-1(A|S|-(i+1))\*char(Si)
104
Explain:
Collision of hash values in the hashing process.
Since hashing functions do not have an indefinite output range (having the range of 0-97 for example) it is expected that different content values get mapped to the same hashing values.
In such case, when hash values are to be stored somewhere we say that we have a collision. The collisions have to be resolved in some way or the data related to the first hash value would be overwritten by the second one.
105
Explain:
Dictionary implementation based on the hash tables.
There are two implementations of the dictionary based on hashing and they are differentiated on the approach they take regarding collision resolution.
* **separate chaining** - uses lists of values to hold all the collided values
* **linear probing** - uses extended array to make space and group collited values in an array section.
106
Dictionary implementation based on the hash table with separate chaining collision resolution strategy.
* Array of N buckets is created to hold N hashes.
* N is selected to be a prime number so that hash values are evenly distributed accross them.
* Every bucket references a list of values which get extended every time ne element for that hash value is provided.
* When collision occurs, element is added to the list of values of that bucker.
* When the element is to be retrieved, the list has to be traversed.
107
Explain:
Problems with the separate chaining in hash table implementation.
If our hashing function doesn't have good properties and have some input examples, or a bigger series of them, for which it produces all the same hash value, this can lead to the situation that some lists of the table get so long that it ends up having O(N) worst case complexity.
These are some standard attacks on the hash table implementations.
108
Hash table data structure asymptotic analysis.
For a hash table where length of the list is N/M for number of elements N and size of the table M
* **insert** - expected constant, worst-case O(1)
* **find** - expected O(N/M), worst-case **O(N)**
* **delete** - expected constant, worst-case O(1)
* **succ**, **pred**, **min**, **max** are all O(N+M) since we have to traverse the whole structure visiting M buckets and N elements in them in total.
109
Explain:
usage of hashing in Rabin-Karp substring search algorithm.
Due to the properties of hashing functions for strings, Rabin-Karp algorithm uses them to efficiently find the substrings in a string in O(n+m) asymprotic complexity.
* First time the m-length string hash is computed.
* Since hash is an integer in A-based number system, we can always drop a digit and compute a new one based on the next char.
* This way we do not recompute whole comparison every time but just once.
