Computer Science Topics Covered in the Content

Graph and Graph Algorithms

1.Context: Graph and Graph Algorithms

a.For the following graph draw the adjacency list and adjacency matrix.

b.i)Using Dijkstra’s shortest path algorithm determine the shortest path to all other nodes in the following graph, starting from node A. Show all the steps with the values of distance and predecessor for each node.

ii)Mention one problem with Dijkstra’s shortest path algorithm.

iii)How can this problem be solved?

c.i.What is a minimum spanning tree (MST) of a graph? 

ii.Using prims algorithm find the MST for the following graph rooted at node 0. Show all the steps.

2.Greedy Algorithm and Dynamic Programming

a.i)State the fractional knapsack problem. 

ii)Write an algorithm to solve the problem using a greedy approach.

b.i)What is memoization?

ii)Write a bottom up algorithm to calculate the nth Fibonacci number using dynamic programming.

iii)In class we discussed about an algorithm to find the longest common substring between two strings using dynamic programming. Using the algorithm complete the following table for the strings “LCLC” and “CLCL”.

3.Convex Hull and Linked List:

a.i) What is a convex hull for a N points in a 2-dimensional spaces? 

ii) Given two lines with a common end point (i.e. AB and AC) in a 2-dimensional space, how can we determine the orientation (Clock wise, counter clock-wise, co-linearity) of the uncommon end-points (i.e. B and C) with respect to each other? Assume the co-ordinates for A, B, C is (x1,y1), (x2,y2), and (x3,y3).

b.For a single ended linked list, describe (do not write any code) the required steps to insert a new node: 

i.At the beginning of the list

ii.At a particular position in the list

iii.At the end of the list

4. Context: Dictionary ADT and hashing 

a.i) What is pre-hashing? 

ii) What is the advantage of using a hash value of the key to find the index for value in the hash table over directly using the key as an index?

iii) When do we have a collision in a hash table?

iv) What is the basic difference between open addressing and closed addressing collision resolution policies?

b.Say, we have the following keys to be stored in a dictionary.

keys = {2,3,9,6,11,13,7,12}

The hash table for contains 10 slots, and the index to the hash table is given by the following hash function 

H(k) = ((pre-hash(k) mod m), where m is the size of the hash table Pre-hash(k) = 2*k + 3

For resolving collision, we are using closed addressing with quadratic probing. Fill the following table and hash table with correct key values.

5. Context: Algorithm Analysis:

a. Define the asymptotic upper bound (Big O), Asymptotic Tight Bound (Big ?) of a function f(n).

6. Context: Heaps and Sorting

a.Construct a max heap from the following array. Draw the heap (tree), before and after each iteration of the build-max-heap algorithm. Circle the node on which you are currently calling max-heapify on and subtree.

A = [15,17,20,1,7,9,45,3,9,5,11]

b.Show the contents of the array after all the required number of passes for sorting the following array using radix sort

A = [0109,  0221, 1723, 0034, 0324, 1211, 0659, 1222]