Algorithms
Links: tutorialspoint, khan academy
52 flashcards · Computer Science · by lakesare
How to traverse a tree using preorder tree traversal?
Because Red has the numbers 3 and 6, it is a descendant of the 1-18 Food node. https://www.sitepoint.com/hierarchical-data-database-2
What is a tree traversal?
Process of visiting (checking and/or updating) each node in a tree.
What's a binary search?
Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than or greater than the middle element, the search continues in the lower or upper half of the array, respectively, eliminating the other half from consideration.
What's the Big O of binary search?
O(log2 n_els_in_array) How many times can we divide an array of N elements by 2 until only 1 element will be left? n_els_in_array/2/2/2/2...(n_of_steps times) = 1 n_els_in_array / 2n_of_steps = 1 n_els_in_array = 2n_of_steps n_of_steps = log2 n_els_in_array Sources: youtube video on binary search
Why is Bubble Sort called so?
Because the tallest person kind of bubbles up on every iteration.
What's a Big O of Bubble Sort?
O(n2) We have 2 nested loops. for (int lastIndex = unorderedAray.length; lastIndex != 0; lastIndex--){ for (int i = 0; i != lastIndex; i++){ unorderedArray[i] = secondNumber; unorderedArray[i+1] = firstNumber; } }
What's a linear search?
Linear search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n/2 comparisons, but the average case can be affected if the search probabilities for each…
Name 2 categories of tree traversal.
depth-first search: deepen as much as possible on each child before going to the next sibling breadth-first search: we visit every node on a level before going to a lower level
What is stable vs unstable sorting algorithm?
Stable: two records R and S have the same key, and R appears before S in the original list, then R will always appear before S in the sorted list. In the card example, cards are represented as a record (rank, suit), and the key is the rank.
What's meant by a key in sorting algorithms?
What we sort by. Here order is the key: [ { order: 3, color: 'red' }, { order: 1, color: 'blue' } ]
What's meant by in-place algorithm?
When no auxiliary data structure is used. The input is usually overwritten by the output as the algorithm executes.
How does insertion sort work?
divide an array into sorted and unsorted parts, take each element from unsorted part insert it in the proper order into the sorted part. Links: very nice video
Recursion vs looping?
By looping we can manually implement stack. Everything done with recursion can be done with looping, everything done with looping can be done with recursion.
Name 3 steps for writing a recursive function.
write if: there must be 2 cases - base and recursive. write the base case. call yourself
There are 2 types of tree traversals: breadth-first depth-first. Explain breadth-first traversal.
It starts at the tree root, and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.
There are 2 types of tree traversals: breadth-first depth-first. Name 3 subtypes of the depth-first traversal.
preorder - <root><left><right> inorder - <left><root><right> postorder - <left><right><root>
Explain depth-first tree traversal (e.g. preorder tree traversal).
In the preorder traversal we visit <root><left><right>. Search tree is deepened as much as possible on each child before going to the next sibling. Links: https://www.youtube.com/watch?v=9RHO6jU--GU
What's Monte Carlo tree search?
The focus of MCTS is on the analysis of the most promising moves, expanding the search tree based on random sampling of the search space. The application of Monte Carlo tree search in games is based on many playouts also called roll-outs. In each playout, the game is played out to the very end by selecting moves at random. The final game result of each playout is then used to weight the nodes in the game tree so that better nodes are more likely to be chosen in future playouts. Monte Carlo tree…
What's a greedy algorithm?
Algorithm that makes the locally optimal choice at each stage to find a global optimum. Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".
A particular sorting algorithm takes n2 comparisons to sort n numbers. Suppose that computing speed increases by a factor of 100. How many comparisons can the computer execute now?
In the time that it was required to take to execute the n2 comparisons, it is now possible to do 100n2 = (10n) 2 comparisons. Unfortunately, with 100 times speed-up, only 10 times as many numbers can be sorted as before.
What is the asymptotic behaviour of T(n)? Suppose that the time complexity of the algorithm is (n is the input size to the algorithm)
Asymptotic behaviour of T(n) as n approaches ∞ is n.
In general, the asymptotic behaviour of functions can be described by so-called “big-O” notations, often consisting of four members: O() Ω() Θ() o(). How is each pronounced?
O - big-oh Ω - omega Θ - theta o - small-oh
What's capital and lowercase of Omega (greek)?
Omega (capital: Ω, lowercase: ω) Omega is the 24th and last letter of the Greek alphabet.
What does 𝑓(𝑛) = O(g(n)) really mean?
f(n) ∈ O(g(n))
What's O(g(n))?
>= Set of functions where g(n) is the upper bound. O(g(n)) is a set of functions that grow at most as fast as g when n → ∞.
What's Ω(g(n))?
<= Set of functions where g(n) is the lower bound. Ω(g(n)) is a set of functions that grow at least as fast as g when n → ∞.
What's Θ(g(n))?
== Θ(g(n)) is a set of functions that have the same growth rate as gwhen n → ∞.
What's o(g(n))?
> Set of functions where g(n) is the upper bound, but not same! o(g(n)) is a set of functions that grow slower than g when n → ∞.
Why is constant c needed as a helper? (shouldn't n >= n0 be enough?)
One needs the c so that f(n) is big O of any multiple of itself. If we were to drop the requirement for the existence of c, we would have that 2n2 ≠ O(n2), for example.
Express this in notation:
In general, an algorithm may accept k different instances of size n. Let Ti(n) be the time complexity of the algorithm when given the ith instance, for 1 ≤ i ≤ k. Let pi be the probability that this instance occurs.What's time complexity of: W(n) - worst case A(n) - average case?
Name 3 sorting algorithms.
Bubble Sort Merge Sort Quick Sort
[sorting algorithms] Describe Bubble Sort algorithm.
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. After the first iteration tallest person is guaranteed to be at the end. When you reach the first sorted player, start over at the left end of the line.
[sorting algorithms] Describe Merge Sort algorithm.
Divide list into the smallest unit (1 element), Compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
[sorting algorithms] Describe Quick Sort algorithm.
We choose pivot at random, then move 'all of the smaller things' to the left, and move 'all of the bigger things' to the right. Now we choose the random pivot (to the left AND right of the previous pivot) again, and repeat the process. Full example of quicksort on a random set of numbers. The shaded element is the pivot. It is always chosen as the last element of the partition. However, always choosing the last element in the partition as the pivot in this way results in poor performance (O(n²)…
What's Fibonacci numbers?
Fibonacci numbers form a sequence, called the Fibonacci sequence, such that each number is the sum of the 2 preceding ones, starting from 0 and 1.
What's the formula for the Fibonacci number at index n?
What's dynamic programming?
Dynamic programming is when repeated computations are avoided for overlapped subproblems. The goal of Dynamic programming is to solve the overlapped parts of the subproblems once only. Instead of repeatedly solving the overlapped subproblems again and again, the Dynamic programming approach records intermediate partial results in a table. The solutions to any of the subproblems, if available, can then be retrieved directly from the table to form the solution to another bigger (sub)problem on re…
What's the difference between Divide and Conquer and Dynamic Programming approaches?
Dynamic programming is similar to Divide and Conquer since they both divide a problem into several smaller subproblems. The difference is that the dynamic programming approach computes the solutions to the subproblems in a bottom-up fashion while Divide and Conquer takes a top-down approach. If the subproblems are overlaps to each other, the bottom up approach such as dynamic programming may save time and space resources.
Degree of a tree node VS degree of a tree?
Write recursive algorithms in Java for tree traversals: preorder(treeNode T) inorder(treeNode T) postorder(treeNode T)
What's the strategy for deleting the smallest/largest element from the heap?
Place the bottommost element in roots place: (a) the smallest element ‘1’ is removed(b) The root position becomes available.(c)(d) Datum 15 is moved from the leaf to the root.(e) Datum 15 is swapped with its smaller (the right) child 5, and then (e) swapped with its smaller (the left) child 8.(f) Datum 15 is finally settled as a leaf and becomes the left child of node 8.
[Heapsort algorithm] Heaps can be used to sort arrays. Sort a list of integers A[1..8] = (10, 8, 14, 15, 12, 5, 6, 1) using a max-heap.
The list of n = 8 unsorted integers is first converted to a max-heap, i.e. a partially sorted, left complete binary tree with the largest integer at the root as in Figure 4.12. The first position A[1] is the root element. During the sorting process, the list is divided into two sections: A[1..k], the heap and A[k + 1..n], the sorted part (in shade in Figures 4.17–4.19). We shall each time remove the root element at A[1], the largest integer from the current heap and insert it to location k + 1,…
What's the strategy for inserting the element to the heap? (Add 2)
Demonstrate, step by step, how to construct a max-heap for the list of integers A[1..8] = (10, 8, 14, 15, 12, 5, 6, 1). Assume the heap is empty initially.
Describe, for graphs: breadth-first traversal depth-first traversal
Breadth-first traversal is to visit all vertices within one same radius (the same path length from the start point) before visiting all vertices within the next radius further. Depth-first traversal is to go as far as possible along a path without revisiting any node, then backtrack to the last turning point and go as far as possible down the next path, and so on, until all the nodes are visited. Depth-first search is analogous to preorder traversal of an ordered tree.
Note there may be other correct traversals and the result depends on the implementation.
What's Huffman coding?
The more frequently the symbol occurs, - the less bits should be used to represent it. Huffman coding is a frequency based variable length coding scheme. Instead of using a fixed-length coding scheme, such as ASCII code, where 8 bits are used to encode every symbol in an alphabet, the more frequently occurring symbols are encoded by shorter codewords using fewer bits than the less frequently occurring symbols. The Huffman algorithm is useful for text file compression. In English text, some char…
What's the objective of Dijkstra's algorithm?
To find the shortest path between 2 points in a weighted graph.
Huffman coding VS Hamming code VS Hamming distance? Richard Hamming (1915 - 1998) David Huffman (1925 - 1999)
Huffman coding - lossless compression algorithm, where the more frequently the symbol occurs, - the less bits should be used to represent it. Hamming code - error correcting code that lets you fix the error in one bit, and find the error in two bits. Hamming distance - number of positions at which the corresponding symbols differ.
What's loop invariant?
Logical assertion that's true before and after the loop call. Knowing loop invariant(s) is essential in understanding the effect of a loop.