| Index TRAKLA2 Research TRAKLA2 Support |
a) Binary search and interpolation search are efficient search algorithms, when the data structure used is an ordered array. What downsides this kind of dictionaries have?
a) For each different type of tree traversal, describe an application which requires such method.
b) Which tree traversal is required in order to print a book's table of contents correctly?
Let N be the number of elements to be sorted. Are the following statements true or false?
a) Quicksort always makes theta(N) recursive calls, where N is the number of elements to be sorted.
b) In the worst case Quicksort is a O(n^2) algorithm.
c) Quicksort requires O(log N) additional space.
d) Quicksort is not a stable sorting algorithm.
Let N be the number of elements to be sorted. Are the following statements true or false?
a) Radix exchange sort always makes theta(N) recursive calls, where N is the number of elements to be sorted.
b) In the worst case radix exchange sort is a O(n^2) algorithm.
c) Radix exchange sort requires O(log N) additional space.
d) Radix exchange sort is not a stable sorting algorithm.
Let N be the number of elements in the binary heap. Are the following statements true or false?
a) Heap insertion takes O(log N) time.
b) Deleting an element from a heap takes O(N) time.
c) Deleting the smallest element element from a heap takes O(log N) time.
Let N be the number of elements in the binary heap. Are the following statements true or false?
a) N elements can be added to heap in O(N log N) time.
b) The buildheap algorithm takes O(N) time.
a) Consider a binary tree of height h. What is the minimum number of elements the tree can hold? What about the maximum number of elements?
b) If a binary tree has N elements, what is the minimum height of the tree? What about the maximum height?
c) What is the worst case time complexity of the search operation in a binary search tree? What about the best case?
How many different input sequences exist that degenerate a binary search tree into a list?
Let N be the number of elements in a binary search tree. Are the following statements true or false?
a) In the worst case deleting an element from a binary search tree takes time which is linear to the number of elements in the tree.
b) In binary search trees the search, insert and delete operations run in O(N) time.
a) Are DST and RST binary search trees?
b) Are DST and RST binary trees?
c*) Consider how you could improve DST and RST (time complexity, memory usage, string key support, duplicate handling, etc.)
Are the following statements true or false?
a) After each insertion to an AVL tree we mustdo O(1) rotations.
b) Three pointers are modified in a single rotation.
c) A double rotation can be performed by doing two simple rotations.
d) Both single and double rotations take O(1) time.
e) Insertion to an AVL-tree takes O(log N) time.
f*) What is the maximum height for an AVL-tree with N elements?
a) Show that each red node in a red-black tree has either 0 or 2 child nodes.
b) Let p1 and p2 be two paths from root to a leaf node in a red-black tree. Let |p| be the length of a path. Show that ||p1| - |p2|| ? |p1|.
c*) Can every AVL-tree be colored into a red-black tree?
Give an input sequence for the hash function given in the exercise that shows undesirable behavior (ie. clustering).
Quadratic probing: When the hash table becomes too full, the performance of quadratic probing crashes. Therefore extra space is required for the data structure to behave efficiently. Is O(log N) extra space enough?
How could you improve the performance of search trees by combining a search tree and a hash table?
Describe how to implement the BFS algorithm using Java. Which Java libraries could you use in the implementation of the auxiliary data structures? What classes would you use in your implementation? What methods are required in the different classes?
In a spreadsheet program you sometimes need to evaluate the values of several cells in order to evaluate the value of a certain cell. How could you use DFS algorithm to find the correct order of cell evaluation?
Describe how to implement Prim's algorithm using Java. Which Java libraries could you use in the implementation of the auxiliary data structures? What classes would you use in your implementation? What methods are required in the different classes?
a) What constraints are required for the Dijkstra's algorithm to work correctly? (Hint: explore how the algorithm works when there are negative weight edges in the graph)
b) Analyze the algorithm given in the exercise description. What is it's running time? How much additional space is required? Use the big Oh notation.