M180: Data Structure and Algorithms in Java

Question 1: (6 marks)
Suppose that we have a node p as follows:
Write the necessary statements that do the following: a) Insert a node q of data = 4 after p. b) Exchange the data in p and q c) Insert a node r of data= 5 between p and q.

Question 2: (12 marks)
Use a stack to write a method reverseString that takes a string as an argument, then it should return a string, which is the reverse of the input string.

Question 3:(12 marks) Write the Java code of the method difference2D that takes two 2-dimentional array (matrix) A and B and returns one 2-dimentional array C that contains the difference between the two matrices. For example, if A and B are as follows:



A B C

Question 4: (10 marks)
For each of the following expressions, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation. Expression Dominant term O(..) 2n(300+0.5n3 ) 2n5+ nlogn5 100n/(2n+1) 100 log( logn) + 5logn 900n4 +2n4 logn2