Reference no: EM131211971
1. Acme company buys and sells oil futures over the Internet. Its trading system receives buy orders from customers that seek to buy from the company. Each order has a bidding price. Orders may be deleted by the customer at any point in time and new orders may also come in at any time.The trading desk would like you to implement a system that keeps track of the top 100 highest buy orders at any point in time.You decide to build a data structure that has two parts: Minheap M of the top 100 orders, and a maxheap H that stores the remaining orders. The contents of the minheap are then displayed to the trading desk, whenever demanded.You are allowed heap operations: (a) min(M): returns the minimum element of a minheap M,(b) max(H): returns the maximum element of maxheap H, (c) insert(G,x): insert the element x in heap G and (d) delete(G,i): delete the ith element G[i] from heap G.Write down pseudocode for how you would update the M and H, under the following situations.Also, write down the worst-case running time in terms of the number of orders n that are currently active. You can assume for simplicity that n 100.
(A) A new order with price $B arrives. (Hint: You will first have to decide if the price is a top 100 price or not. Based on that you have to perform the appropriate heap operations).
(B) The top 100 order M[i] is withdrawn by the customer
2. An array is almost k sorted if every element is no more than k positions away from where it would be if the array were actually sorted in an ascending order.
(A) Write down pseudo code for an algorithm that sorts the original array in place in time nk log(k).Your algorithm can use a function sort(A, l, r) that sorts the subarray A[l], . . . , A[r].
(B) Suppose you are allowed extra array of size k + 1 on the side. Modify heap sort using a minheap of size k + 1, to sort the given array in time n log(k). (Hint: Take the first k + 1 elements and make a min heap. Keep extracting the minimum element from this min heap and adding anew element from the original array.).
|
Major security breach
: Research a case that has been in the news in the last few years where a major security breach occurred on a wireless network. Find a case where attackers got in via the wireless network, but then penetrated farther into the network, resulting in s..
|
|
What is the maximum size of a file
: In UNIX System V, the length of a block is 1 Kbyte, and each block can hold a total of 256 block addresses. Using the inode scheme, what is the maximum size of a file?
|
|
What is the maximum file size supported by this system
: Assuming no information other than that the file inode is already in main memory, how many disk accesses are required to access the byte in position 13,423,956?
|
|
Gives example of what characteristics fit into each category
: The Classification assignment requires you to organize a topic into categories and then provide examples of what characteristics fit into each category.
|
|
Pseudo code for an algorithm
: Write down pseudo code for an algorithm that sorts the original array in place in time nk log(k).Your algorithm can use a function sort(A, l, r) that sorts the subarray A[l], . . . , A[r].
|
|
What are some of the key characteristics of an embedded os
: What are some typical requirements or constraints on embedded systems?
|
|
Describe and define usability and usability
: Describe and define usability and usability best practices in web and mobile design. NOTE: The answer should be between 250 to 350 words and should not contain plagiarism.
|
|
Designing a dns namespace for a large enterprise
: What considerations should be made when designing a DNS namespace for a large enterprise? What are the different types of DNS zones?
|
|
What concurrency mechanisms are available in ecos
: What concurrency mechanisms are available in eCos?
|