5120COMP: A queue is a special kind of list, where items are inserted at one end and deleted at the other end :Algorithm Design, Assessment, LJMU, UK

• A queue is a special kind of list, where items are inserted at one end (the rear) and deleted at the other end (the front). We shall use the following operations on queues.

Enqueue(X): Inserts element X at the end of the queue.
Dequeue(): Remove the first element of the queue.

1. Explain the disadvantages of implementing the operations Enqueue and Dequeue, by NOT thinking of the array as a circle (where the first position follows the last). Illustrate your answer using diagrams. [5]
2. Explain how we can implement the operations Enqueue and Dequeue by thinking of an array as a circle. Illustrate your answer only using diagrams (you do not need to write methods for the operations). You should give the contents of the array after each operation and clearly indicate the positions of the front and rear. [10]
3. (i) Draw an undirected connected graph with five vertices and at most five edges. Label the vertices with integers, {1, 2, 3, 4, 5}. You should not use a graph from the lectures or online sources.

(ii) Give the order of the vertices of the graph in part (c) (i) visited using Breadth
First Search (BFS) starting at vertex 1. A queue can be used in BFS traversal.
You should give the elements of the queue after every step. [10]

1. Using suitable diagrams, show how a binary search tree would be built for a sequence of letters from your surname. The order of the letters in the sequence is the same order as in your surname. Assume that all the letters are uppercase letters.
2. Describe the following recursive traversals of a binary tree, and list the values stored at the nodes of the binary search tree you created in part (a)

(i) in order,
(ii) preorder, and
(iii) postorder.

Describe how to recursively traverse a binary search tree to print out the
values stored at the nodes in descending order. 

1. Using suitable diagrams, show how a heap tree would be built for a permutation of four numbers such that the value in each node is greater than or equal to the values in its children. You should not use a permutation of four numbers from the lectures or online sources. [14]
2. Operation deleteMax deletes and returns the largest element from a heap tree. Using suitable diagrams shows how this operation can be efficiently performed on the heap tree from your answer to part (a). Note that the remaining elements after the operation deleteMax should satisfy the heap-tree properties. [6]
3. Explain why implementations of the priority queue using a heap-tree (partially ordered list) are more efficient than using an ordered list

• For a given weighted undirected graph, briefly describe two greedy criteria for constructing a minimum-weight spanning tree.
•  Draw a connected weighted graph with five vertices and at least seven edges. Label the vertices. You should not use a graph from the lectures or online sources.
• Using the greedy criteria you described in (a), construct a minimum weight
  spanning tree for the graph in (b) (i). You should construct a tree for each greedy criterion. Number the tree edges in the order in which they were selected.
• Run two steps of the basic Page Rank algorithm on the following network of web pages.

Suppose there is no edge from R to S in the above network. What will be the
converging PageRank values?

• Given an array containing n entries sorted in nondecreasing order, and
  given a value x, describe the binary search method for finding the position of x in the array. [4]
• Using an example of a sorted array of eight numbers, explain how the binary search method finds the position of number 5. You should not use an example from the lectures or online sources. [6]
• Let D1 and D2 denote two decision problems. What does it mean to say that D1 is polynomially transformable to D2 (written Explain the steps for proving Hamiltonian Circuit Problem (HCP) is polynomially transformable to Travelling Salesman Problem (TSP) using an example of an instance for HCP. You should not use examples from the lectures or online sources. [5]
• Prove that, if D1 £P D2 and D2 can be solved by a polynomial-time algorithm, then D1 can be solved by a polynomial-time algorithm. [5]

Give a definition of the set of NP-complete problems.

Answer

Request Answer of this Assignment