Goldsmiths Exam: Algorithms

19 flashcards · Computer Science · by lakesare

  1. Define hashing.

    Hash function is a mapping of data of arbitrary size to fixed-size value. In databases For Hash indexingIn digital signatures There are several well-known hash functions used in cryptography. These include the message-digest hash functions MD2, MD4, and MD5, used for hashing digital signatures into a shorter value called a message-digest, and the Secure Hash Algorithm (SHA), a standard algorithm, that makes a larger (60-bit) message digest and is similar to MD4. A hash function that works well…

  2. Name 2 states that are needed for each cell if hash function is perfect, and 1 additional state that's needed if hash function is not perfect?

    empty, occupied A perfect hash function requires a good prior knowledge of the set of potential keys. Two states are sufficient for each cell of the hashtable, namely empty and occupied.rehashed All the rehash sequence of cells have to be flagged for the rehashed keys.

  3. Suppose the hash function is h(k) = k mod 11, and rehash function is then h(k) = (k + 1) mod 11. Describe the search for 159. h(159) = 159 mod 11 = 5

    We first find the location for 159: h(159) = 159 mod 11 = 5. Since the state is rehash, we proceed rehashing to probe location 6. In location 6, state of the cell is occupied, we know there is no further rehashing is required and the key is found in H[6]. The situation, however, requires further indication since cell H[6] is the actual key for 159, but is one of the rehash cells for 27 and 17. In this case, the state of each cell needs to be key oriented as well. That is, the state of the same…

  4. What's greedy algorithm VS exhaustive search? Give one advantage for each. (Both phrased by me)

    Exhaustive search - checks all solutions, and picks the best. Advantage: will always get you the optimal solution. Greedy search - makes the locally optimal decision at each step, trying to find the global optimum. Advantage: quick. Greedy algorithms have some advantages and disadvantages: It is quite easy to come up with a greedy algorithm (or even multiple greedy algorithms) for a problem. Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (li…

  5. Give 2 reasons why Turing machine (an abstract computational model) is used in the study of computability (instead of the real computer).

    1. Results should work for the future computers We need to be able to argue that our results on computability (tractability) apply to all types of computers, including the ones not only in the past or at present, but also in the future.2. It's a mathematical model, it's reductionist & simple. What can be done algorithmically, can be done by a Turing Machine and what can’t be done by an algorithm can’t be done by a Turing machine

  6. Undecidable problem VS intractable problem?

    undecidable - e.g. halting problem, - a problem for which it's impossible to construct an algorihm that intractable - it has a complexity worse than O(n1 or 2 or 99) Intractable:

  7. Prove that there is no algorithm that would determine whether ANY program g halts or not. Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.

    If there exists halts(g) - code of the program g can include this function halts(g), and do the opposite of it. It's a proof by contradiction, - suppose there exists a function halts(g) that always returns whether ANY program g halts. then we can create a program g that includes halts(g) in its implementation, effectively reversing it. def g(): if halts(g): loop_forever()

  8. Give the corresponding decision problem for the Travelling Salesman Problem. The Travelling Salesman Problem is a combinatorial optimisation problem. There are N cities { A, B, C, D }, and each city has to be visited ONCE ONLY before returning to the origin. The aim of the TSP is to find a cyclic path A-C-D-B-A that minimises the distance travelled.

    Corresponding decision problem asks: Is there a path with a cost LESS THAN some fixed amount k. Decision problem definition: A problem with a "yes" or "no" answer. Equivalently, a function whose range is two values, such as {0,1}. There are two versions of the Traveling Salesman Problem.The optimization version: Given a complete weighted graph G with positive integer weights find a Hamilton Cycle in G with minimum weight.The decision version: Given a complete weighted graph G with positive inte…

  9. What does it mean for the Travelling Salesman Problem to be NP-complete? The Travelling Salesman Problem is a combinatorial optimisation problem. There are N cities { A, B, C, D }, and each city has to be visited ONCE ONLY before returning to the origin.The aim of the TSP is to find a cyclic path A-C-D-B-A that minimises the distance travelled.

    It's In NP (can be verified in polynomial time) In NP-hard (every problem in NP can be transformed into NP-hard) https://stackoverflow.com/questions/49837125/confusion-about-np-hard-and-np-complete-in-traveling-salesman-problems The definition of an NP-complete problem was meant for decision problems, so it technically does not apply directly to search or optimization problems. But because the theory behind it is well defined and useful, it is handy to still apply the term NP-complete/NP-hard t…

  10. Explain which decision problems are: P NP NP-hard NP-complete

    P - can be solved in polynomial time. NP - solutions can be verified in polynomial time. NP-hard - everything in NP can be transformed into NP-hard. A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it.NP-complete - both NP and NP-hard! problems that are both NP-hard, and in NP. Proving that a problem is NP is usually trivial, but proving that a problem is NP-hard is not. Boolean satisfiability (SAT) is widely believed to be NP-hard, and thus the usu…

  11. What is a search tree? Name 2 types of search trees.

    Tree where the key for each node must be: greater than any keys in subtrees on the left, and less than any keys in subtrees on the right. binary search tree B-tree - generalization of the binary search tree, where a tree can have a variable number of subtrees at each node. ternary search tree Type of tree that can have 3 nodes: a lo kid, an equal kid, and a hi kid. Each node stores a single character and the tree itself is ordered the same way a binary search tree is, with the exception of a po…

  12. What's this type of a tree called?

    Binary search tree

  13. Visualise depth-first search:

    Just play it again.https://www.hackerearth.com/ru/practice/algorithms/graphs/depth-first-search/visualize Here is the breadth-first one: https://www.hackerearth.com/ru/practice/algorithms/graphs/breadth-first-search/visualize

  14. Draw the search tree for the travelling salesman problem.

  15. Name 3 uses of quadtrees.

    efficient collision detection in two dimensions spatial indexing in spatial databases A spatial database is a database that is optimized for storing and querying data that represents objects defined in a geometric space. image representation A tree where each internal node has exactly 4 children.

  16. Convert the pixel-grid into a quadtree.

  17. Describe the Abstract Data Type for the quadtree.

    find(x,y) returns true if a point (x,y) is found in a given object insert(x,y) add one point (x,y) in a given object delete(x,y) remove one point (x,y) from a given object

  18. What's octtree?

    Like quadtrees, but for three-dimensional space. A cube is recursively partitioned into eight octants, using three orthogonal planes.

  19. Given the quadtree below, draw the original pixel image.