Assignment 2 – Implementation of Algorithms and Data Structures

Software Technology 2 (7170)

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.

Note– 5 marks if Google Java Style is not used

• [4 marks]
1.  [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 a size method which returns the number of elements stored. Implement dynamic resizing for this stack.
2. [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. A Java 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.

• [4 marks]
1.  [2 marks] Implement a generic Queue<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 method which 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.
2. [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. A Java program that 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 their Big-O for time and space efficiency.

• [4 marks]
1. [2 marks] Implement a generic queue class named InefficientQueue<T> in terms of two internal stacks.  The methods required in this class are enqueue, dequeue, and peek.  The goal of this problem is to get you to use the stack abstraction while implementing a queue abstraction. This method for implementing a queue is quite inefficient (thus the name of the class).  Why is this so?
2. [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 program that 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.

• [4 marks]

Implement the RemoveBefore(int nodeValue) [1 mark] and RemoveAfter(int nodeValue) [1 mark] methods for a LinkedList class.

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(int nodeValue) method [1 mark] for the LinkedList class using the internal Node class.

Submission: a Java program that contains the Node and LinkedList classes, 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

• [4 marks]
1. [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.
2. [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 program 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.

References:

[1] Gayle Laakmann. Cracking the Coding Interview.

[2] Adnan Aziz, Tsung-Hsien Lee and Amit Prakash. Elements of Program Interviews.

— END —