Algorithms and Complexity

Algorithms and Complexity Assignment

Question 1 (10 mark) Important features of Object-Oriented programming are encapsulation, abstraction,

inheritance and polymorphism. Describe an example where you have seen abstraction used in a program.

Provide details.

Question 2 (10 mark) Given an n-element sequence S, you have an algorithm B that chooses (the next integer

greater than nlogn) [nlogn]elements at random and executes an O(n3)-time calculating for each. What is the

worst-case running time of B?

Question 3 (10 mark) A program to generate all the permutations of a set is run on a computer that writes

the output to a file at a rate of 1300 permutations per second. How long will it take the computer to generate

all the permutations of a set with 7 (distinct) elements?

Question 4 (10 mark) Write in pseudo code a recursive algorithm for finding the maximum element in a

sequence, R, of p3 elements. What is your running time and space usage?

Question 5 (10 mark) Memoization and Dynamic programming are both methods used in recursive

algorithms for what purpose? Explain how this is achieved.

Question 6 (10 mark) def Arithmetic (n)

for i in range (1 ,n ):

for j in range ( i ,( i +5)/3): a=nˆ i − 2. j

return a

What is the big O complexity of Arithmetic? Show working.

In question 6, in changing the assignments, i sometimes has the function iterate over a range where the parameters of the range may not be integers. If you have that error, replace range ( x, y) with range (x, floor(y)) where floor(y) is the integer n st. y-1<n<y

Question 7 (10 mark) What are the two manipulation functions required for a Queue ADT based on a Linked

List. Give the pseudo code to implement these on the base structure.

Question 8 (30 marks) .

1) Write a definition for a general Graph and write in words Euler’s generalise theorem on the

complete traversal of a graph, which is called an Eulerian cycle. If you remove the condition of the

start and end point being the same, you have an Eulerian path

2) Draw a graph with 5 vertices that has: an Euler cycle; an Euler path but not an Euler cycle; neither

of these.

3) Write in pseudo code an algorithm to traverse a graph and verify if the graph has an Eulerian cycle or path. First consider how you will represent the edges and vertices in your code and show this. Note: The Euler's theorem referred to in question 8 is the theorem relating to the Konigsberg bridge, and it is a generalised theorem on the complete traversal of a graph can be achieved if the number of edges on a vertex is always even then I asked for three types of graphs, where each graph has one of the properties given, you cannot do all in one.