Reference no: EM131050455
Assignment - Implementation of Algorithms and Data Structures
Question 1.
a. 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. 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<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. 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.
Question 3.
a. 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. 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.
![1666_Figure.png](https://secure.expertsmind.com/CMSImages/1666_Figure.png)
References:
[1] Gayle Laakmann. Cracking the Coding Interview.
[2] Adnan Aziz, Tsung-Hsien Lee and Amit Prakash. Elements of Program Interviews.
Pension plan is obligated to make disbursements
: A pension plan is obligated to make disbursements of $1 million, $2 million, and $1 million at the end of each of the next three years, respectively. The annual interest rate is 10%. If the plan wants to fully fund and immunize its position, how much..
|
Sketch net present value profile for each of these projects
: Consider the following projects, X and Y where the firm can only choose one. Projects X costs $600 and has cash flows of $400 in each of the next 2 years. Project Y also costs $600, and generates cash flows of $500 and $275 for the next 2 years, resp..
|
Find the even and odd parts of the following functions
: Show that any function can be written as the sum of an odd function plus an even function. List as many even and odd functions as you can.
|
Valid restriction in a cooperative interest
: Which of the following is not a valid restriction in a cooperative interest? Which of the following is not a remedy available to homeowners' associations for violations of CCRs and rules?
|
Write a method that takes a sorted integer array 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
|
Bonds make semiannual payments-current bond price
: Sqeekers Co. issued 12-year bonds a year ago at a coupon rate of 7.8 percent. The bonds make semiannual payments and have a par value of $1,000. If the YTM on these bonds is 6.1 percent, what is the current bond price? (Do not round intermediate calc..
|
What theory of insider trading applies to each person
: What crimes, if any, have been committed? What theory of insider trading applies to each person? What viable defenses, if any, may be raised?
|
A response paper on bruised hibiscus
: Please write a response paper on Bruised Hibiscus. Your paper can focus on the concept of honor killings, the affect of early childhood trauma on adult relationships, the affects of white supremacy on those who benefit from it as well as those wh..
|
Do sales practices constitute fraud under mail fraud statute
: Do these sales practices constitute fraud under the mail fraud statute? How, if at all, do the misrepresentations differ from those in Hawkey? Are intent to deceive and intent to defraud necessarily the same thing? Explain thoroughly.
|