Assignment - Implementation of Algorithms and Data Structures

Question 1.

a. Implement a generic Stack 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. 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.

Question 2.

a. Implement a genericQueue 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. 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, peek and min.

Question 3.

a. Implement a generic queueclass namedInefficientQueue 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. 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.

Question 4.

Implement theRemoveBefore(int nodeValue) and RemoveAfter(int nodeValue) methods for aLinkedListclass.

The RemoveBefore (RemoveAfter) method removes the node before (after) the node having the given node value. The internal class Node 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 for the LinkedList class using the internal Node class.

Question 5.

a. 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. Write a Java program to test this method and provide at least 4 test cases for this program.

References:

[1] Gayle Laakmann. Cracking the Coding Interview.

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