Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

First Semester Examination

June 2017

Data Structures and Algorithms

CITS2200

Q1.

(a) Write pseudo code for the quick different parts of your code.

(b)

sort algorithm, explaining clearly the (5)

· What is the asymptotic time complexity of the quick  sort algorithm?

· Write a recurrence relation for expressing the time complexity of the

quick  sort algorithm and give intuitive arguments for its solution.

·  Simulate the algorithm you have written in part (a) on the following

array for sorting it in ascending order.   You should choose the first element of an array as the pivot.

9,  8,  7,  6,  5,  4,  3,  2

(5)

Q2. Points on the plain are denoted by (z, y) coordinate pairs with respect to two coordinate axes, z and y.  For example, (2, 5), (2.8, 11.9) are two points on the plain.   A 2-dimensional  range  tree data structure stores  (z, y) coordinate pairs of points on the plain and has the following properties:

· Both the z and y coordinates are oating point numbers.

·  Given a set of points, the primary tree is built by first sorting the

z-coordinates and storing them in the leaves of a binary tree T in ascending order.

·  Suppose X is an internal node in the tree T.  All the y-coordinates of

the points stored in the leaves of the subtree rooted at X are stored in another binary tree rooted at the node X.

· The range tree is used for answering range  search queries.  Given a

set of points s on the plane, first a range tree T is constructed as de- scribed above.  A query range is a rectangle whose sides are parallel to the coordinate axes.  A query range is denoted by a pair of coordi- nates (z1 , y1 ) and (z2 , y2 ), which are the coordinates of the top-left and bottom-right corners of the query rectangle.

·  Given a query range g, one of the aims of a range tree is to count the

number of points in s .

(a) Write a class in Java for implementing the range tree data structure. What is the time complexity for constructing a range tree, if it stores X points? Describe an algorithm for inserting a point in the range tree (either as a Java method, or in pseudo code, or in English).   What is the time complexity of your algorithm?

(5)

(b) Describe an algorithm (either as a Java method, or in pseudocode, or in English) that takes a query g and a range tree T, and returns the count of the number of points inside g. What is the time complexity of your algorithm?

(5)

Q3.

(a)

· Prove that X log2 X is not o(X).

· Prove that X2 log X is o(X3 ).

(5)

(b) Order the following functions by growth rate (low to high).  All loga-

rithms are base 2:             

(5)

Q4.

(a) Write pseudocode or explain in your own words the in-order, pre-order and post-order traversal algorithms for trees.

(5)

(b) Show the execution of your algorithms in part  (a) on the tree given below. Show the vertices visited as a sequence of their labels at every step.

a

b

m

f                  h

 

(5)

Q5.

(a) Write pseudocode or explain in your own words the Floyd-Warshall all- pairs shortest path algorithm. Given a graph G = (v, E), what is the asymp- totic complexity of this algorithm? Explain your answer clearly.

(5)

(b) Write pseudo code or explain in your own words the Bellman-Ford single- source shortest path algorithm.   Given a graph G  =  (v, E), what is the asymptotic complexity of this algorithm? Explain your answer clearly.