Syllabuses

Let G = (V, E) be a directed graph and vertices start, goal to be in V. Assuming all edges in E are of non-negative weight, describe an efficient algorithm for finding the longest cyclic path from start to goal.

Describe an algorithm to check whether a given integer is a node of an AVL tree.

The integers 5, 26, 41, 18, 16, 4, 13 are to be stored in a closed bucket hash table of length 7. Write a suitable hash function and show where each of the integers would be stored in the table, assuming the order of insertion is from left to right.

In the previous problem, show the heap after adding the four max elements.

Add the following numbers sequentially to an initially empty heap: $12, 5, 15, 9, 22, 41, 18, 16, 4, 13$

An operation to read a time should have the time set by the time of the clock advance by one second. Give the pseudo algorithm.

Find the time efficient algorithm to describe an abstract data type specification and implementation.

Write an algorithm to check whether a given integer is stored in the table.

Describe how a new integer could be inserted into a sequence of sorted integers (so that the resulting sequence is also sorted) in each of the following cases: i. The sequence is stored in an array. ii. The sequence is stored in a linked list.

The integers 5, 26, 22, 41, 18, 16, 4, 13 are to be stored in a closed bucket hash table of length 13: i. Suggest a suitable hash function. ii. Compare the efficiency of (i) and (ii). iii. Give the time complexity of various sorting/searching algorithms as per the table given below: | Algorithm | Best case | Average case | Worst case | | :--- | :--- | :--- | :--- | | Binary search | - | - | - | | Insertion sort | - | - | - | | Linear search | - | - | - | | Bubble sort | - | - | - | | Radix sort | - | - | - | | Quick sort | - | - | - | | Heap sort | - | - | - | | Merge sort | - | - | - |