Algorithms: Abstract Data Types

33 flashcards · Computer Science · by lakesare

1. What's Abstract Data Type (ADT)?

   Definition of the data type that only mentions what operations can be performed, but NOT how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view.

2. What's matrix?

   Array of arrays Matrices are two dimensional arrays and have following characteristics: a collection of data of the same type arranged in a two dimensional table consisting of rows and columns the rows and columns themselves are each indexed by a separate contiguous range of some ordinal data type, e.g. integers.

3. What's a linked list?

   In a linked list structure, each datum consists of at least two fields: data and next, where data is of a simple data type and the next is an address or index pointing to the datum after the the current one. The relationship among data is one-after-another. In a linked list, a datum can only be accessed by following the link from its precessor. It would naturally take longer to reach the last element in a long list than the one in front

4. What's array?

   Array is a powerful data structure with a constant access time. The structure can be used to mimic a real linear memory storage because the data items in an array are placed one after another and each item is associated with an index (called an address). Arrays are often described as static data structures if the number of data items has to be specified at the beginning. The maximum number of the index remains the same no matter what operations are performed on the data. The size of the array c…

5. Why is array slow for insertion?

   Values are stored in contiguous locations, and in order to insert a datum at some place in an array of integers, all the data from that location on have to be moved one cell towards the end to generate a cell for the new datum. Arrays are powerful for storing data but they are after all a data holder. Data is stored in contiguous locations and the size of the array has to be fixed before any usage of the array.This makes some updating operations such as insertion or deletion or updating extreme…

6. What's the difference between inserting an element in the array (a) VS in the list (c)?

   For each datum, the field next points to the following datum, where the sign “/” represents the end of the linked set (i.e. the special value null in Java). For example, the next object after {12,2} should be {10,3}. Figure 2.2 (d) shows that the physical location of each datum does not really matter as long as the data link gives the correct order. Figure 2.2 (c) and (d) both have the same logical link (i.e. data order) as 2.2 (e). Now it is an easy matter to insert an element before 10. We co…

7. What two fields would a linked list Node implementation have in Java?

   A linked list (or list) is an abstract data structure consisting of a collection of data objects in which each item contains not only a data field but also at least one link field to point to the following object.

8. List of lists: ((((A, B), C, D), E, F, G), (H, I, J), ((K, L, M), N)) Draw the tree this list of lists represents!

9. How can the arithmetic expression be represented as a list?

10. How many existing nodes need to be affected to insert a node in the linked list?

    To insert the node before p: node before p self To insert the node before head p of the list: self :-)

11. Two nodes are special in such a linked list: first node (head), last node

    The first node of a linked list is called the head of the list, which cannot be accessed following the link of any list nodes. The head of a list has to be initialised. The last node of a linked list points to nobody and has a null value for its nextNode field.

12. What fields would the LinkedList class have?

13. Name 2 sides of a queue.

    front rear

14. In a queue, what do enqueue and dequeue functions do?

    enqueue(x) add an element x at the rear end of the queue. dequeue() remove an element x from the front end of the queue.

15. What's dequeue (not function, but a data structure)?

    A deque is a double-ended queue in which objects can be added or removed at either end of the queue. Note the difference between the term dequeue and deque: Dequeue is an operation on a queue, and deque is a special queue that allows the addition or deletion of an element from both ends.

16. What's hash table / hash map?

    A hash table is a { key: value, ... } data structure, where index of where value is stored is determined by the key itself. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

17. What are the hash code and a hash function?

    hash_function(value) - hash_code A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

18. [hash tables] What is a collision?

    A collision happens when a datum is attempted to be stored in an already occupied cell. Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are always accommodated in some way. The idea of hashing is to distribute the entries (key/value pairs) across an array of buckets. Given a key, the algorithm…

19. Name 2 uses of hash tables.

    Associative arrays - hash tables are commonly used to implement many types of in-memory tables. They are used to implement associative arrays (arrays whose indices are arbitrary strings or other complicated objects), especially in interpreted programming languages like Ruby, Python, and PHP. Database indexing - hash tables may also be used as disk-based data structures and database indices (such as in dbm) although B-trees are more popular in these applications. In multi-node database systems,…

20. [hash tables] Assume that a hash function h(k) = k mod 11 is used and the hash table is empty initially. Show the content of the hash table after inserting the data (7, 31, 159, 189, 23, 6).

    Once we have the hashtable built up, searching for a datum is straightforward. Given a key k, all it is required is to compare the k to Hashtable[h(k)]. Suppose that we search for key k = 23.We check the location and find h(23) = 23 mod 11 = 1, and compare the key k and the Hashtable[1].Since k = Hashtable[1] = 23, we know that 23 is in the hashtable and can return its location 1.

21. [hash tables] Name 2 ways to resolve a collision.

    closed address hashing - does not consume any extra addresses of the hashtable open address hashing - number of addresses of the hashtable may be increased (linear probing, double hashing).

22. [hash tables: resolving collisions] What's closed address hashing?

    Closed address hashing is one easy solution for collision. The method chains the collided data together, using an array of linked lists. The size of the hash table remains the same during closed address hashing.

23. [hash tables: resolving collisions] Name 2 methods of open address hashing.

    linear probing double hashing

24. [hash tables: resolving collisions: open address hashing] What's linear probing method of resolving collisions? Suppose the hash function is h(k) = k mod 11, and the rehash function is then h(k) = (k + 1) mod 11. The hash table is empty initially. Show the content of the hash table after inserting the data (29, 93, 31, 159, 51, 189, 27, 23, 17, 9).

    Linear probing simply allocates the collided datum to the next available location. For example, if the first hash location h1 is occupied, then h1 + 1 is offered if it is empty, otherwise, the next location h1 + 2 is offered, and so on.

25. [hash tables: resolving collisions: open address hashing] What's double hashing method of resolving collisions?

    Double hashing repeatedly steps forward an interval set by a SECOND hash function until the desired value is located, an empty location is reached, or the entire table has been searched. As we can see, the double hashing is more efficient than linear probing in this example. After one rehashing, only 9 is still collided with 31. This means that one probe is not sufficient using the double hashing. In this case, we need to take another approach to resolve the collision for 9. For example, we can…

26. [hash tables] What's perfect hash function?

    A hash function that produces a hashtable without any collision is called a perfect hash function. A perfect hash function requires a good prior knowledge of the set of potential keys.

27. [hash table] What's 3 states are needed for each datum in the hash table?

    empty occupied rehashed Two states are sufficient for each cell of the hashtable, namely empty and occupied. Most hash functions are imperfect unfortunately so rehashing are required, as we see in the previous sections. When a hashtable is searched, the third state is needed for each cell in order to indicate that the data have been rehashed. Let the third state be rehash. All the rehash sequence of cells have to be flagged for the rehashed keys.

28. What fields would a TreeNode implementation have in Java?

    TreeNode allows us to construct the entire tree! We need to define three fields, namely left, da, right, where left and right are the links to the left child and right child respectively, and da is the data field.

29. What is the infix and postfix forms of the expression (a + b) * c?

    infix form: (a + b) * c postfix form: a b + c * The postfix form of an arithmetic expression a + b is ab+, and the postfix form of (a + b) ∗ c is ab + c∗.The normal form of an arithmetic expression such as a + b and (a + b) ∗ c is called the infix form.Brackets are not needed in the postfix or prefix form and therefore are economical for computer storage.

30. Write (a + b) ∗ c ∗ (d + e) in the postfix form.

    ab + c ∗ de + ∗

31. Here is an expression in postfix form: a b + c d e + * * Construct an expression tree using stack data structure.

    The evaluation of the tree takes place by reading the postfix expression one symbol at a time. If the symbol is an operand, a one-node tree is created and its pointer is pushed onto a stack. If the symbol is an operator, the pointers to two trees T1 and T2 are popped from the stack and a new tree whose root is the operator and whose left and right children point to T2 and T1 respectively is formed. A pointer to this new tree is then pushed to the Stack.

32. Store a binary tree in an array.

    The advantage of the array implementation is that each node can be accessed in O(1) time. In addition, the parent or each child of a node can be accessed in O(1) time. For example, node A[i]’s parent is: A[i div 2], its left child is A[2i] and the right child is A[2i + 1].

33. Name 2 types of binary heaps.

    max-heap - any parent node is BIGGER than its children min-heap - any parent node is SMALLER than its children