Reference no: EM131214730
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.).
|
Where do the voltage maxima and minima in occur
: Application: Standing wave ratio and minima and maxima on the line. For a line with characteristic impedance Z0 = 50 Ω and a load R = 220 Ω
|
|
Find the pm
: Highway A and Highway B merge to form Highway C - Find the PM.- Is also a Poisson random varialbe or does it follow some other distribution?
|
|
What are the uses of context free grammars
: What are the uses of Context Free Grammars? What are the applications of Context Free Languages?
|
|
Find the maximum and minimum voltage on the line
: If the voltage at the load is 100 V, find the maximum and minimum voltage on the line.
|
|
Original array in place in time nk log
: 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].
|
|
Identify various social trends that affect marketing
: To complete this assignment, students must prepare a real-world marketing news example, event, or success story and communicate it to the class. Students should use popular resources such as The Wall Street Journal, Bloomberg Businessweek, Inc., e..
|
|
Analyse principles and trends in performance
: Performance Management and Control - Identify and critically analyse principles and trends in Performance Measurement and Control and Determine the different budgeting techniques and critically evaluate their use in short term decision making
|
|
What mechanism is responsible for the formation of products
: If k1 > k2, is the overall reaction SN1 or SN2? Research and Explain what chemical mechanism is responsible for the formation of the products.
|
|
Calculate and plot the line impedance as a function
: At the frequency at which the line operates, the reactance of the load is -j50 Ω and the phase constant on the line is 20π rad/m. Calculate and plot the line impedance as a function of distance from load.
|