Midterm Exam-103-code2-solution

pdf

School

University of Notre Dame *

*We aren’t endorsed by this school

Course

30331

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by DeaconSteel13534

Number on the list Midterm Exam CS610-103 Grade Time: 2 hours Exam code: 2 Name: Instruction: 1. Smart devices (cellphones, smart watches, AirPods, ...) are not allowed during the exam. Please ensure that they are turned off and left your cellphones at the designated area before the exam. 2. Under no circumstances are students allowed to leave the exam room during the exam, for any reason. 3. The exam is closed book, and using any study materials, laptops, notes, or textbooks during the exam is prohibited. 4. Backpacks and other personal belongings (like jacket, laptop, ...) should be placed under your desk before the exam starts. Accessing your backpack during the exam is not allowed, so please make sure you have all necessary items on your desk before the exam begins. 5. Please check that the number on this paper matches your assigned number on the list, and that you sit on the correct seat. 6. You are not allowed to use your own paper during the exam. If you need extra paper, please ask the instructor.

1. We implement six algorithms (Heapsort, Insertion sort, Radix sort, Quick sort, Merge sort and Selection sort) to sort the following list. Input: 79, 139, 169, 97, 137, 119, 77, 151 At an intermediate step, we print the state of the list and obtain the following lists, A,B,C,D, E and F. For each list, determine which sorting algorithm has been applied to the list? (25 points) A: 77, 79, 97, 169, 137, 119, 139, 151 B: 139, 119, 77, 151, 169, 97, 79, 137 C: 79, 97, 137, 139, 169, 119, 77, 151 D: 77, 79, 97, 137, 119, 139, 151, 169 E: 79, 97, 139, 169, 119, 137, 77, 151 F: 79, 97, 119, 139, 137, 169, 77, 151 A: Selection B: Radix C: Insertion D: Quick E: Merge F:Heapsort

2 . We introduce a new field called ' size ' to the AVL Node structure, which stores the number of nodes in the subtree rooted at that specific node, including the node itself. Rewrite the ' insert ' function for AVL trees to maintain size field. The goal is to ensure that the time complexity of this modified function remains O(log n) . Please refer to the example below, where we have provided the number of nodes in the subtree rooted at each node. (25 points) InsertAVL(int k){ // Creating a new node to insert new_node.parent=NULL; new_node.leftchild=NULL; new_node.rightchild=NULL; new_node.element=k; new_node.size=0; new_node.BF=0; // inserting new node insert new_node to T as usual; // updating size fields after insertion temp=new_node; while(temp!=NULL){ temp.size=temp.size+1; temp=temp.parent; } // check if it is an AVL update balance factors; // if it is not an AVL, change it to an AVL if(there is a node whose balance factor is +-2){ determine A, B and C; Perform necessary rotations; // after performing rotations, A and B and C will have new children, so we need to update their sizes A.size=A.leftchid.size+ A.rightchid.size +1; B.size=B.leftchid.size+ B.rightchid.size +1; C.size=C.leftchid.size+ C.rightchid.size +1; } } 1 1 3 1 1 3 7

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

3. We are given a list of 6 keys: (1,3,1), (2,1,2), (2,2,1), (1,1,3), (3,1,1), (1,2,2) . By using Summing Component, try to store these keys in a lookup table of size 7. What is the most suitable hashing method to use in order to avoid collisions when Summing Components method is not effective? Explain your idea using the above list. (25 points) By summing component, all these keys will be hashed to 5 A better hash code in such cases should somehow take into consideration the positions of the 𝑥 𝑖 ’s. That is, each index, i, should play a role in the hash function in some way. Choose a nonzero constant, 𝑎 ≠ 1 , and use as a hash function the following: (Polynomial-Evaluation Functions) For example here: ℎ(𝑥 1 , 𝑥 2 , 𝑥 3 ) = 4𝑥 1 + 2𝑥 2 + 𝑥 3 h(1,3,1)= 11%7=4, h (2,1,2)=12%7=5, h(2,2,1)=13%7=6, h(1,1,3)=9%7=2, h(3,1,1)=15%7=1, h(1,2,2)=10%7=3 .

4. You are given a grid of size ? × ? , where each cell can be either empty or blocked. You are also given a robot located at the top-left cell (0, 0) and a destination cell at the bottom-right cell (m-1, n-1). The robot can move in only two directions: right and down. Start and destination cells are not blocked. Write a recursive function to count the number of unique paths the robot can take from the top-left cell to the bottom-right cell, given the following constraints: (25 points) 1. The robot cannot pass through blocked cells. 2. The robot can only move right or down. Blocked Blocked Blocked Blocked We define a matrix T[m][n] such that T[i][j]=0 if cell (i,j) is blocked, otherwisw T[i][j]=1 Path takes start cell (i,j) path(i,j){ if T[i][j]==0 return 0 if i==m-2 and j==n-1 return 1 if i==m-1 and j==n-2 return 1 if i>m-1 or j>n-1 return 0; return path(i+1,j)+path(i,j+1) } We call path(0,0) Destination

Related Documents

CSCI N207 Quiz One Answers.docx

CSCI N207 Quiz Four Answers.docx

CSCI N207 Quiz Two Answers.docx

README.md.docx

4347 Project Description(1).docx

Midterm Exam-103-code1-solution.pdf

5-1 Module Five Assignment_ Impact of Cybercrime-2.pdf

Lab04.pdf

hw1.docx

Chicka chicka boom boom lesson plan 5:23.docx

Understanding Alpha-Beta Pruning Enhancing Game Tree Search Efficiency.docx

Carmen Quiz 4 - Chapter 4 - Countif(s)_Sumif(s)_Averageif(s)_Large_Small_Rank_ AU23 CSE 2111 - Sprea

Recommended textbooks for you

Enhanced Discovering Computers 2017 (Shelly Cashm...

Computer Science

ISBN:9781305657458

Author:Misty E. Vermaat, Susan L. Sebok, Steven M. Freund, Mark Frydenberg, Jennifer T. Campbell

Publisher:Cengage Learning

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

Microsoft Windows 10 Comprehensive 2019

Computer Science

ISBN:9780357392607

Author:FREUND

Publisher:Cengage

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

CMPTR

Computer Science

ISBN:9781337681872

Author:PINARD

Publisher:Cengage

Oracle 12c: SQL

Computer Science

ISBN:9781305251038

Author:Joan Casteel

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

Enhanced Discovering Computers 2017 (Shelly Cashm...
Computer Science
ISBN:9781305657458
Author:Misty E. Vermaat, Susan L. Sebok, Steven M. Freund, Mark Frydenberg, Jennifer T. Campbell
Publisher:Cengage Learning
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
Microsoft Windows 10 Comprehensive 2019
Computer Science
ISBN:9780357392607
Author:FREUND
Publisher:Cengage
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
CMPTR
Computer Science
ISBN:9781337681872
Author:PINARD
Publisher:Cengage
Oracle 12c: SQL
Computer Science
ISBN:9781305251038
Author:Joan Casteel
Publisher:Cengage Learning