Reference no: EM131157394
Assignment:
Answer question 1, question 2, and any other 2 questions from questions 3 to 6. You must score at least 50 to pass the assignment.
1. You have learned some fundamental data structure concepts such as array, queue and priority queue, stack, list and linked list, sequence, and unordered set, and you understand the concept of interface or abstract data type that defines the set of operations supported by a data structure and the semantics, or meaning, of those operations. You can use the interface of one particular data structure to define or implement the operations of a different data structure.
a. Describe the meaning of the essential methods add(x), deleteMin(), and size() that are supported by the priority queue interface. Implement those methods using a singly-linked list.
Analyze the running time of the add(x) and deletMin() operations based on this implementation.
b. Implement the stack methods push(x) and pop() using two queues (5 marks for each method).
Analyze the running time of the push(x) and pop() operations based on this implementation.
2. Swap two adjacent elements in a list by adjusting only the links (and not the data) using
a. singly-linked list.
b. doubly-linked list.
c. skiplist.
3. Exercise 1.5. Using a USet, implement a Bag. A Bag is like a USet-it supports the add(x), remove(x), and find(x) methods-but it allows duplicate elements to be stored. The find(x) operation in a Bag returns some element (if any) that is equal to x. In addition, a Bag supports the findAll(x) operation that returns a list of all elements in the Bag that are equal to x.
4. Exercise 2.3. Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The add(x) and remove() operations in a RandomQueue should run in constant time per operation.
5. Exercise 3.12. Write a method, reverse(), that reverses the order of elements in a DLList.
6. Exercise 3.14. Design and implement a MinStack data structure that can store comparable elements and supports the stack operations push(x), pop(), and size(), as well as the min() operation, which returns the minimum value currently stored in the data structure. All operations should run in constant time.
|
Discuss the importance of integrating sales and operations
: In this lesson, we discuss the importance of integrating sales and operations. This idea of integrated management is indeed a key tenet of supply chain and operations management practices today
|
|
How did the roles of african americans change
: How did the roles of African Americans change as thousands of Black soldiers began to come back to the United States? Please keep in mind that many of these solders were returning the segregated South.
|
|
Geometric distribution applies
: Assume the geometric distribution applies. Use the given probability of success p to find the indicated probability.
|
|
Find the probability that the number who consider
: Of men consider themselves professional baseball fans. You randomly select 10 men and ask each if he considers himself a professional baseball fan. Find the probability that the number who consider themselves baseball fans is(a) exactlyfive, (b) a..
|
|
Design and implement a randomqueue
: Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue.
|
|
Benefits and disadvantages of business analytics
: Describe the benefits and disadvantages of business analytics, as well as how the organization can be proactive in addressing any disadvantages. Include at least 3 benefits and disadvantages
|
|
Audit of the financial statements of transoceanic
: For purpose s of the audit of the financial statements of Transoceanic, what procedures should the auditors employ in examining the described loans?
|
|
Financial statement disclosures
: a.) For purpose s of the audit of the financial statements of Transoceanic, what procedures should the auditors employ in examining the described loans? b.) What financial statement disclosures should the auditors expect to find with respect to th..
|
|
What is expected return for each of given investment option
: what is the expected return for each of these investment options- How can you explain to your friend why the expected returns of each investment are different?
|