1 M180: Data Structure and Algorithms in Java Tutor-Marked Assignment (Spring 2015/2016) Cut-Off Date: April 30th, 2016 Total Marks: 40 Contents Warnings and Declaration………………………………………………………………………………..1 Question 1……………..……………………….………………………………………………………….2

1
M180: Data Structure and Algorithms in Java
Tutor-Marked Assignment (Spring 2015/2016)
Cut-Off Date: April 30th, 2016
Total Marks: 40
Contents
Warnings and Declaration………………………………………………………………………………..1
Question 1……………..……………………….………………………………………………………….2
Question 2 ………………..…………………………………………………………………………….….2
Question 3 ………….………..………………………………………………………………………….….3
Question 4 ………….…………..……………………………………………………………………….….3
Question 5………….…………..……………………………………………………………………….….4
Question 6………….…………..……………………………………………………………………….….4
Plagiarism Warning:
As per AOU rules and regulations, all students are required to submit their own TMA work and avoid plagiarism. The AOU has implemented sophisticated techniques for plagiarism detection. You must provide all references in case you use and quote another person's work in your TMA. You will be penalized for any act of plagiarism as per the AOU's rules and regulations.
Declaration of No Plagiarism by Student (to be signed and submitted by student with TMA work):
I hereby declare that this submitted TMA work is a result of my own efforts and I have not plagiarized any other person's work. I have provided all references of information that I have used and quoted in my TMA work.
Name of Student:………………………………..
Signature:…………………………………………...
Date:……………………………………………………
Arab Open University
2
Question 1:(6 marks)
Given a Node p in a doubly linked list of nodes L, as shown in the figure below.
Draw what will happen in the list L after each set of statements (one drawing for each part), knowing that the parts are related.
a) DoublyListNode q=new DoublyListNode (3,null,null);
q.prev=p.prev;
q.next=p;
b) p.prev.next=q;
p.prev =q;
c) p=p.next.next;
p.prev=q.next;
q.next.next=p;
d) q.prev.prev=p;
q.prev.prev.next=q.prev;
Question 2: (8 marks)
Write a java method rotate that takes a two-dimensional array a and returns a two-dimensional array b made by rotating a by 90° counterclockwise.
For example, if a holds
1 2 3 4 5 6
b = rotate(a) will hold
3 6 2 5 1 4
3
Question 3:(6 marks)
For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation.
Consider that we always have n>m.
Expression
Dominant term(s)
O(…)
5+ 0.01n3 + 25m3
500n +100n1.5 + 50nlogn
0.3n+ 5n1.5 +2.5n1.75
n2logn +n(log2m)2
mlog3n +nlog2n
50n+53m + 0.01n2
Question 4: (6 marks)
Given the following Java code:
public static void printIt(Queue myQueue)
{ int t;
if(myQueue.isEmpty())
System.out.println("Done");
else{
t= myQueue.dequeue();
System.out.print(t+"-");
printIt(myQueue);
}
}
public static void main(String[] arg) {
Queue myQueue=new Queue();
for (int i=0; i<5; i++){
myQueue.enqueue(i*3);
}
printIt(myQueue);
}
a- What will be the output of the above code?
b- Assume that the data structure used above is changed, replacing the queue with stack, what will be the expected output? Why? Discuss.
4
Question 5:(7 marks)
Suppose that a linked list is formed from objects that belong to the class
class ListNode {
int item; // An item in the list.
ListNode next; // Pointer to next item in the list.
}
Write a recursive method, recursiveListSum, that will find the sum of all the items in a linked list. The method should have a parameter of type ListNode and should return a value of type int.
Question 6: (7 marks)
Write a method convertToBin (using Stack) that takes a positive number n as an argument , and prints the binary representation of the number n.
End of Assessment