Find Jobs
Hire Freelancers

Algorithms

$10-30 USD

処理中
投稿日: 7年近く前

$10-30 USD

完了時にお支払い
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? 2) Consider inserting 15 distinct letters into a Hash Table of size m=9 using open-addressing with auxiliary function h'(k)=position_in_alphabet(k). For example, h'(A)=1, h'(B)=2, h'(C)=2, etc. a) Choose 15 unique letters to be your keys. Then, illustrate the result of inserting these keys in the order defined in a) using: b) Linear probing; c) Quadratic probing with c1=1 and c2=3; d) Double hashing with h1(k)=h'(k) and h2(k)=1+(h'(k) mod (m-1)) Show your calculations. 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: a) To implement an operation called TREE-HEIGHT(x) that (efficiently) calculates the height h of a node x in the BST of Chapter 12 (i.e., h=#levels-1); b) Next, answer what the time and space complexity of your implementation is; After a few tests though, you realize that your time complexity is still too high for the application. Therefore, you decide to approach the problem from a different perspective. You decide to add an extra field to each node in the BST that stores the height of that node in the tree. That should allow you to look up the tree height in constant time. So your second job is: c) To make all necessary changes to TREE-INSERT(T,z) and TREE-DELETE(T,z) to accommodate an extra field for the height of each node; 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.
プロジェクト ID: 13588233

プロジェクトについて

9個の提案
リモートプロジェクト
アクティブ 7年前

お金を稼ぎたいですか?

Freelancerで入札する利点

予算と期間を設定してください
仕事で報酬を得る
提案をご説明ください
登録して仕事に入札するのは無料です
アワード者:
ユーザーアバター
boss ...................................................................................................................................................................................................................................................................................................
$35 USD 1日以内
5.0 (82 レビュー)
5.8
5.8
この仕事に9人のフリーランサーが、平均$70 USDで入札しています
ユーザーアバター
hi Hope you're doing well. Lets get started on that. I am expert programmer and i am sure i would be right fit for this job. Thanks :)
$77 USD 3日以内
4.7 (15 レビュー)
4.8
4.8
ユーザーアバター
Hi, I am professional freelancer and student of theoretic informatics, I have several experience with algorithms design, your project description is pretty long but is really simple. Hire me and you will get a TOP quality product! Regards, Bc. Martin Risa
$90 USD 1日以内
5.0 (2 レビュー)
1.0
1.0
ユーザーアバター
A proposal has not yet been provided
$66 USD 5日以内
4.0 (1 レビュー)
0.0
0.0
ユーザーアバター
A proposal has not yet been provided
$15 USD 2日以内
0.0 (0 レビュー)
0.0
0.0

クライアントについて

UNITED STATESのフラグ
Rancho Cordova, United States
5.0
1
お支払い方法確認済み
メンバー登録日:4月 1, 2017

クライアント確認

ありがとうございます!無料クレジットを受け取るリンクをメールしました。
メールを送信中に問題が発生しました。もう一度お試しください。
登録ユーザー 投稿された仕事の合計
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
プレビューを読み込み中
位置情報へのアクセスが許可されました。
あなたのログインセッションの有効期限がきれ、ログアウトされました。もう一度ログインしてください。