CS311 Assessment EX14A 2023 v2-1

Instructor use only Score 1 (5) Score 2 (5) Score 3 (5) Score 4 (5) Final Score (20) 5 5 2.5 5 17.5 FALL 23 CS311 Week 14 A: Summary Exercise due by 10 AM the next day to Canvas. Your name: Kaden Gore Your major: CS _ x _ CIS __ SE __ Other ___ (mark one) First, you must complete the Advising HW to have this EX graded. I have completed the Advising HW on __ 11/28/2023 ___ This exercise will test you to see if you can apply what you have learned in this course, and thus it will prepare you for the final. Q1) You are writing a program that simulates a hospital emergency department’s triage. Two tasks that need to be performed efficiently are: a) inserting a new patient’s information into the waiting list when they arrive (which patient is next seen by a doctor is determined by the severity of their ailment .) b) removing the patient information from the waiting list. Which data structures should be used to store this waiting list? A, B, C, or D. Fill in the blank. __ C_ _ [2pts] A. Regular Queue B. Stack C. Heap-Sort Tree D. BST (balanced) Explain why by how quickly a) and b) can be accomplished by it in terms of O-notations where N is the number of patients. a) can be done per patient in O(_ logN ___) [1.5pts] b) can be done per patient in O(_ logN_ ___) [1.5pts] Q2) We want a Binary Search Tree storing 1,2,3,4,5,6,7 so that it models Binary Search with O(logN). Give the tree here: [2.5pts]

4 / \ 2 6 / \ / \ 1 3 5 7 We want a Binary Search Tree storing 1,2,3,4,5 so that it models Linear Search with O(N). Give the tree here: [2.5pts] 1 \ 2 \ 3 \ 4 \ 5 Q3) We want an airline flight map as a directed graph with 10 nodes ( N = 10). At most how many flights can be included without duplicating flights? Give the formula in terms of N and then the number [2.5pts]: Max flight = N*(N-1)/2 N = 10 10 * 9/2 = 45 is the maximum number of flights directed -1.5 We want to eliminate some flights to reduce costs but still want the graph connected. How many flights will remain? Give the formula in terms of N and then the number [2.5pts]: N – 1 = 10 – 1 = 9 flights would remain directed -1 Q4) My program must examine every path in the Chess game tree which has a branching factor of 35 and a depth/bottom level of 80. How many paths does it have to examine? Give the formula with the numbers plugged in [5pts]: