Provide answer to these questions:
1) Consider a Sorted Doubly-Linked List, which means that keys are kept always sorted and stored in a doubly linked list:
a) Implement an operation SD-LIST-INSERT(L,k) that inserts an integer key k into list L. What is the running time Θ(.) of your implementation?
b) Implement an operation SD-LIST-DELETE(L,k) that removes a key k from the list. What is the running time Θ(.) of your implementation?
c) Implement operations SD-LIST-SUCCESSOR(L,k) and SD-LIST-PREDECESSOR(L,k) that returns the successor and predecessor of a key k, respectively. What is the running time Θ(.) of your implementation?
d) Implement an operation SD-LIST-SEARCH(L,k) that searches for a key k in list L and returns its node position (e.g., 1 if first, 2 if second, etc). What is the running time Θ(.) of your implementation?
e) Implement an operation SD-LIST-REVERSE(L) that reverses the order of the keys in place (i.e., Θ(n) space complexity). What is the running time Θ(.) of your implementation?
3) Consider an application that frequently inserts data into a BST and even more frequently performs searches on these data. Because of the high demand for search operations, this application simply can't afford the worst-case searches of a BST (i.e., Θ(n)). To this end, it frequently has to check the height of the BST so it can rebalance it if necessary. It is your chance to show your value to the company and improve their application.
Your first job is:
d) To implement another operation called TREE-HEIGHT-LOOKUP(x) that retrieves the height h of the node x in constant time;
Now, your third and final job is:
e) To evaluate and discuss your 2 approaches by answering: "Which of the 2 applications is more efficient? The one with TREE-HEIGHT(x) or the one with TREE-HEIGHT-LOOKUP(x)?" Explain.
*Tip: Note that by allowing constant time height look-ups, you added some overhead in computing 2 other operations.
I, Jignesh Lakhani completed my masters from IIT Roorkee in Computer Engineering. I am having very good knowledge of C, C++, Java, JavaFX, Algorithm and Data Structure. I am having strong analytical power. I will complete your project before deadline
I am looking forward to discussing with you about this job post. Please feel free to contact me.
Respectfully,
Jignesh
$40 USD en 1 día
5,0 (2 comentarios)
2,2
2,2
3 freelancers están ofertando un promedio de $57 USD por este trabajo
Bid Summary
Hello Sir/ Ma’am
We are a group of Software Engineers having more than 5+ years of experience. Expert in java, C, C++. Please check our profile for reference.
Thank you
Project Requirements
Hello Sir/ Ma’am
We are a group of Software Engineers having more than 5+ years of experience. Expert in java, C, C++. Please check our profile for reference.
Thank you
Relevant Skills and Experience
Hello Sir/ Ma’am
We are a group of Software Engineers having more than 5+ years of experience. Expert in java, C, C++. Please check our profile for reference.
Thank you
Proposed Milestones
$30 USD - milestone