Assignment 2–Implementation of Algorithms and Data Structures

Type: Individual assignment
Submission: A Word file that contains Java code listings and test cases (including input, output and your comments) for each of the questions listed below. Submit this Word file via Moodle. Email submission is not accepted. Tutors will test your Java code listings and test cases on Hacker Rank or Tutorials Point.
Total mark: 20
Proportion of unit assessment: 20%
Late submission:5% of the total mark (i.e., 1 mark) per day.
Language: Java (use Google Java Stylehttps://google.github.io/styleguide/javaguide.html)

Note: – 5 marksif Google Java Style is not used

Question 1. [4 marks]
a. [2 marks] Implement a generic Stack<T> class using an array T[] for storing elements. Your class should include a constructor method, which takes as argument the capacity of the stack, push, pop and peek methods, and asize method which returns the number of elements stored. Implement dynamic resizing for this stack.
b. [2 marks] Write a program to test your implementation of this Stack class. You also need to provide at least 4 test cases for this program to test all the methods including constructor, push, pop, peek and size, and to test dynamic resizing.

Submission: A report that shows how to implement dynamic resizing. AJava program that contains this Stack class and all test cases. Tutor will run your program on Tutorials Point web site. Your program will have no input at runtime and will output results for all test cases at the same time.
 You cannot use any existing Stack class in Java library to implement this Stack. Use an array to implement this Stack.
Hint:Think of an efficient algorithm for dynamic resizing first.

Question 2. [4 marks]
a. [2 marks] Implement a genericQueue<T> class that has enqueue, dequeue and peek methods and all of these methods must be O(1) time. This class also has a min methodwhich returns the minimum value stored in the queue, and throws an exception if the queue is empty. Assume elements are comparable. If the queue contains n elements, you can use O(n) space, in addition to what is required for the elements themselves.
b. [2 marks] Write a program to test your implementation of this Queue<T> class. You also need to provide at least 4 test cases for this program to test all the methods including enqueue, dequeue, peek and min.

Submission: A report that shows how the enqueue, dequeue and peek methods are O(1) time. AJava programthat contains the queue class and all test cases. Tutor will run your program on Tutorials Point web site. Your program will have no input at runtime and will output results for all test cases at the same time.
 You cannot use any existing queue class in Java library to implement this queue, however other data structures (ArrayList, LinkedList, Stack, etc.) are acceptable.
Hint:Compare different data structures in Java and choose an appropriate one. Check theirBig-O for time and space efficiency.

Question 3. [4 marks]
a. [2 marks] Implement a generic queueclass namedInefficientQueue<T> in terms of twointernal stacks. The methods required in this class are enqueue, dequeue, andpeek. The goal of this problem is to get you to use the stack abstraction while implementing aqueue abstraction. This method for implementing a queue is quite inefficient (thus the name of the class). Why is this so?
b. [2 marks] Write a program to test your implementation of this queue class. You also need to provide at least 4 test cases for this program to test all the methods including enqueue, dequeue and peek.

Submission: A report that explain why this queue is inefficient. A Java programthat contains the InefficientQueue class and all test cases. Tutor will run your program on Tutorials Point web site. Your program will have no input at runtime and will output results for all test cases at the same time.

Question 4. [4 marks]
Implement theRemoveBefore(intnodeValue)[1 mark] and RemoveAfter(intnodeValue)[1 mark] methods for aLinkedListclass.

The RemoveBefore (RemoveAfter) method removes the node before (after) the node having the given node value. The internal class Node[1 mark] to build the LinkedList class has only an integer value, nodeValue, and a single link, next, that links to the node just behind the given node.You also need to implement the Add(intnodeValue) method [1 mark] for the LinkedList class using the internal Node class.

Submission: a Java programthat contains the Node and LinkedListclasses, your method implementation, and all test cases. Tutor will run your program on Tutorials Point web site. Your program will have no input at runtime and will output results for all test cases at the same time.
Hint:You cannot use any existing LinkedList and Node classes in Java library

Question 5. [4 marks]
a. [2 marks] Write a method that takes a sorted integer array A and a key k and returns the index of the first occurrence of k in A. Return -1 if k does not appear in A. For example, when applied to the array in Figure 12.1 below, your algorithm should return 3 if k = 108; if k = 285, your algorithm should return 6.
b. [2 marks] Write a Java program to test this method and provide at least 4 test cases for this program.

Submission: The Java method and programand all test cases. Tutor will run your program on Tutorials Point web site. Your program will have no input at runtime and will output results for all test cases at the same time.

 

References:
[1] Gayle Laakmann. Cracking the Coding Interview.
[2] Adnan Aziz, Tsung-Hsien Lee and AmitPrakash. Elements of Program Interviews.