Lab6_21W

docx

School

Centennial College *

*We aren’t endorsed by this school

Course

254

Subject

Computer Science

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by ChefPorcupineMaster87

Data Structures and Algorithms COMP-254 Lab Assignment #6 – Using Trees, Maps and Hash Tables Due Date: Friday, Week 12 Purpose: The purpose of this Lab assignment is to:  Design algorithms that describe operations on ADT Maps  Investigate the efficiency of hash table implementations  Implement and test appropriate methods in Java References: Read the course’s text chapter 10 and the lecture slides. This material provides the necessary information that you need to complete the exercises. Be sure to read the following general instructions carefully: - This assignment must be completed individually by all the students. - You will have to demonstrate your solution in a scheduled lab session and upload the solution on eCentennial through the assignment link. Exercise 1 The use of null values in a map is problematic, as there is then no way to differentiate whether a null value returned by the call get(k) represents the legitimate value of an entry (k, null), or designates that key k was not found. The java.util.Map interface includes a boolean method, containsKey(k) , that resolves any such ambiguity. Implement the containKey(k) method for the SortedTableMap class. Hint: Use the existing findIndex(k) method. Write a Java application to test your solution. (5 marks) Exercise 2 Give an efficient algorithm that computes and prints, for every position p of a tree T, the element of p followed by the height of p’s subtree. Write a Java program to test your solution. Hint : Use a postorder traversal to find the height of each subtree. The height for a subtree at p will be 0 if p is a leaf and otherwise one more than the height of the max child. Print out the element at p and its computed height during the postorder visit. (5 marks) Evaluation: Lab #6 Page 1 of 2

Data Structures and Algorithms COMP-254 Correct implementation of requirements:  Correct ADT data structure algorithm  Correct Java implementation  Explanation of algorithm when asked 90% Friendly I/O 10% Total 100% You must name your Eclipse project according to the following rule: YourFullname_COMP254Labnumber_Exercisenumber . Example: JohnSmith_ COMP254Lab6_Ex1 Submission rules: Submit your modules as zip files that are named according to the following rule: YourFullname_ COMP254Labnumber_Exercisenumber.zip Example: JohnSmith_ COMP254Lab6_Ex1.zip Lab #6 Page 2 of 2

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

4.5 assignment.pdf

IT 505 Milestone1.docx

9-1 Final Project.docx

ART_NationalBlueprint.docx

ASTRO_horsesProposal.docx

Recommended textbooks for you

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

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

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

Microsoft Visual C#

Computer Science

ISBN:9781337102100

Author:Joyce, Farrell.

Publisher:Cengage Learning,

SEE MORE TEXTBOOKS

Recommended textbooks for you

Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
Microsoft Visual C#
Computer Science
ISBN:9781337102100
Author:Joyce, Farrell.
Publisher:Cengage Learning,