task09

pdf

School

Brigham Young University, Idaho *

*We aren’t endorsed by this school

Course

341

Subject

Computer Science

Date

Nov 24, 2024

Type

pdf

Pages

Uploaded by PrivateStarPartridge3

WEEK 09 Name: Collaborators (if any): 1. Tasks 1.1. True or False. Choose T or F for each of the following statements and briefly explain why. (1) T/F Searching in a skip list takes Θ(log n ) time with high probability, but could take Ω(2 n ) time with nonzero probability. (Note: this statement could actually be answered as either true or false with proper justification) (2) To implement a dictionary, you should always use a hash table over an AVL tree if your main priority is speed. (3) The number of collisions in a hash table is solely dependent on the table capacity and the hash function. (1) True. The purpose of a skip list is to jump over some items in the list and not go over each one. In the worse case scenario, we may have skipped the item we want and in that case we need to go back some how. (2) False. AVL can be faster. (3) False. IT depends of the size and quality of the hash funtion. 2. Exercises/Problems 2.1. Calculate Hash Values for Given Keys. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i. 9679, 1989, 4199 hash to the same value ii. 1471, 6171 hash to the same value iii. All elements hash to the same value iv. Each element hashes to a different value (A) i only (B) ii only (C) i and ii only (D) iii or iv Date : November 12, 2023. 1

2 WEEK 09 2.2. Given a hash table with keys, verify/find possible sequence of keys. For a given hash table, we can verify which sequence of keys can lead to that hash table. However, to find possible sequences leading to a given hash table, we need to consider all possibilities. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below. 0 1 2 42 3 23 4 34 5 52 6 46 7 33 8 9 Which one of the following choices gives a possible order in which the key values could have been inserted in the table? (A) 46, 42, 34, 52, 23, 33 (B) 34, 42, 23, 52, 33, 46 (C) 46, 34, 42, 23, 52, 33 It follows the sequence (D) 42, 46, 33, 23, 34, 52

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

15 post.docx

James Hemson.docx

Lucas DuBoisModuleSevenLessonSevenActivity.ipynb - Colaboratory.pdf

Screenshot_15-2-2024_115427_app.sophia.org.jpeg

Quiz_Practice_3_ANSWERS.pdf

For the Final Paper.docx

Programming assignment.docx

Long Quiz 003 - (2).png

phpQILUBk.png

Short Quiz 009 - 1 (5).png

4-2 Activity Critical Analysis Reimagine.docx

INFORMACION COMPLETA DE LA UNIDAD- FORO DE PRESENTACION.pdf

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

New Perspectives on HTML5, CSS3, and JavaScript

Computer Science

ISBN:9781305503922

Author:Patrick M. Carey

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:9781305503922
Author:Patrick M. Carey
Publisher:Cengage Learning