Find the smallest gap between two numbers in K. The algorithm should return the magnitude of the gap between the two closest integers. The algorithm(FINDGAP) should support Insert, delete and search in O(log n) time. And we maintain a dynamic set of integers. Example = [30, 5, 20, 9] Output = 9 - 5 = 4 a) Choose data structure to store the dynamic set of integers b) Create the algorithm FINDGAP and make it run as fast as possible. (PSEUDOCODE) c) Prove runningtime of FINDGAP and argue its optimal

Find the smallest gap between two numbers in K. The algorithm should return the magnitude of the gap between the two closest integers. The algorithm(FINDGAP) should support Insert, delete and search in O(log n) time. And we maintain a dynamic set of integers. Example = [30, 5, 20, 9] Output = 9 - 5 = 4 a) Choose data structure to store the dynamic set of integers b) Create the algorithm FINDGAP and make it run as fast as possible. (PSEUDOCODE) c) Prove runningtime of FINDGAP and argue its optimal

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 18PE

See similar textbooks

Similar questions

Write a function that shuffles the rows in a two-dimensional list using the following header:def shuffle(m):Write a test program that shuffles the following matrix:m = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]]
#The Iris Dataset import sklearn.datasetsimport matplotlib.pyplot as plt import numpy as np import scipy iris = sklearn.datasets.load_iris() Write a function that takes in an index i and prints out a verbose desciption of the species and measurements for data point i. For example:Data point 5 is of the species setosaIts sepal length (cm) is 5.4Its sepal width (cm) is 3.9Its petal length (cm) is 1.7Its petal width (cm) is 0.4
2) Hash Innards Homework • Unanswered Select all true statements from the below. Multiple answers: Multiple answers are accepted for this question Select one or more answers and submit. For keyboard navigation. SHOW MORE V a A hash function takes a key and produces an index into the hash table. The next step in this process is often something like 'h%SIZE' so that the hash value of the key will fit within the table b (having SIZE elements, you see). Common techniques involve exclusive or of bits within the key and folding different sections of bits within the key into each other. The best hash method for character strings is to simply add up the ASCIlI values of their individual characters. Coming up with a perfect hash for a given set of keys can be a difficult and time-consuming task.
Recamán's sequence def recaman_item(n):Compute and return the n:th term of the Recamán's sequence. See the linked definition for this sequence on Wolfram Mathworld. Note how the definition for the current element in this sequence depends on whether some particular number can be found in the previously generated prefix of the sequence. To allow your function to execute in a sure and speedy fashion even for millions of elements, you should use a set to keep track of which elements are already part of the prefix of the sequence generated so far. This way you can generate each element in constant time, instead of having to iterate through the entire previously generated list the way some "Shlemiel" might approach this problem. n Expected result 1 1 8 12 13 23 57 87 395743 258330 The previous version of this problem, simply called recaman in the very first versions of this problem collection,…
Let A and B be two integers valued arrays of sizes n1 & n2 respectively. The elements of the two arrays are sorted in increasing order and may contain duplicate elements.It is required to form a list, C, of distinct elements, in increasing order, that are in A but not in B and in B but not in A. (There shall be no duplicate elements in list C.)The two arrays, A & B, can only be traversed once.Example:A: -2, 2, 4, 4, 4, 7, 9, 9, 9, 12, 15,B: 1, 2, 5, 9, 15, 15, 15, 17, 17, 17C: -2, 1, 4, 5, 7, 12, 17
l JO 100 4G 2:02 AM @ 52% assignment_3 v2 AI and ML Assignment 3 Write a python program to cluster candidates into 2/3 groups. The program performs dimensionality reduction, then clustering of candidates based on top 2 PCs. The results are plotted to visually show the performance of candidates. The program performs the following tasks: Read input "pca cluster.csv" file. Use Panda library. Example of the file: candi cand2 cand3 cand4 cand5 cad6 experience 10 9 7 3 education 10 10 8 10 health 4 6 8 9 9. interview 9 6 6 8 7 test 4 9. 10 communication skills 7. 6 9 10 10 writing skills team player leadership 10 9 6 6. 8 7 4 10 9 4 10 4 9 6 8 5 9 7 enthusiasm 7. 7 7 9 ready to start 5 6 6. 9 1 flexible in hours 10 1 9. 5 6. able to relocate 6 6 6. 10 4 references 9 9 7 9 4 10 • Apply PCA analysis to identify top 2 PCs. Eigen No. 0 Eigen value (33.50+0j) Contribution % (40.87+0j) Points on new scale [5 5-8 3 0-5] Eigen No. I Eigen value- (22.65+Oj) Contribution % (27.63+0j) Points on new…
Write the state of the elements of the vector below after each of the first 4 passes of the outermost loop of the insertion sort algorithm. (After the first pass, 2 elements should be sorted. After the second pass, 3 elements should be sorted. And so on.) // index 0 1 2 3 4 5 6 7 vector<int> numbers{29, 17, 3, 94, 46, 8, -4, 12}; insertionSort(numbers); NOTE: Write your answer inside curly braces with numbers separated by commas {29, 17, 3, 94, 46, 8, -4, 12} after pass 1 after pass 2 after pass 3 after pass 4
Use Python. The pseudocode is given in figure 3.9 use that and do not change the function names. The output should be Moves: RDLDDRRNumber of Nodes expanded: 361TIme Taken: 0.238Memory Used: 704kb This is the search.py file that is also given you have to write the code in a main.py file using the pseudocode. class Search: def goal_test(self, cur_tiles): return cur_tiles == ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '0'] def solve(self, input): # Format : "1 0 2 4 5 7 3 8 9 6 11 12 13 10 14 15" initial_list = input.split(" ") # solution_moves = run_bfs(initial_list) print("Moves: " + " ".join(path)) print("Number of expanded Nodes: " + str("")) print("Time Taken: " + str("")) print("Max Memory (Bytes): " + str("")) return "".join(path) # Get the list of moves to solve the puzzle. Format is "RDLDDRR" if __name__ == '__main__': agent = Search()
Language: Python 3 Autocomplete Ready O 1 v import ast 3. Hybrid Sort input() lst %3D 3 lst = ast.literal_eval(lst) 4 Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. In each iteration, insertion sort inserts an element into an already sorted list (on left). The position where the item will be inserted is found through linear search. You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. 6 print(BinaryInsertionSort(lst)) Algorithm BinarylnsertionSort Input/output: takes an integer array a = {a[0], ..., a[n – 1]} of size n begin BinarylnsertionSort for i =1 to n val = a[i] p = BinarySearch(a, val, 0, i – 1) for j = i-1 to p a[j + 1]= a[i] j= j-1 end for a[p] = val i i+1 end for end BinarylnsertionSort Here, val = a[i] is the current value to be inserted at each step i into the already sorted part a[0], ..., ați – 1] of the array a. The binary search along that part…
Python help----- Using HASH sorting algothrim create only one function def sortstring(filename): that takes in a file which has a bunch of sentences, each line of sentence consting of different length. Sort the setences from the lower length senteces to the highest length sentence. Print it after ( DON'T USE ANY SORTING BULT-IN FUNCTION ). Note: Keep note of time complexity as it should be able to run few 10,000 lines of sentences in few seconds.
What is the value of the median-of-3 for the following list. [96, 90, 43, 94, 52, 82, 50, 31, 51, 58] Notes: • Your answer should be a single valid, non-negative, literal Python int value. For example, 123 is a valid int literal. • This question is asking about before any partition operation is carried out. • This is not asking for the median-of-3 index. • You can pre-check your answer (to check it's a valid, non-negative, literal int). Answer: (penalty regime: 10, 20, ... %) Precheck Check
#### Part 1 Write a Python function (`binary_search`) that implements the binary search algorithm. This function will take a list argument (`values`), a value to search for (`to_find`), a start index (`start_index`), and an end index (`end_index`). The function will return `True` if `to_find` is present in `values`, and `False` otherwise. Below, you will find some code to test your binary search: ```python values = [2,4,6,8,10,12,14,16,18,20] print(binary_search(values, 14, 0, len(values) - 1)) print(binary_search(values, 7, 0, len(values) - 1)) ``` The output of the test code is below: ``` True False ``` #### Part 2 Modify your `binary_search` function to count the number of comparisons (==, <, <=, >, or >=). The function will now return both the number of comparisons made and the `True` or `False` result. The code below calls your function, and creates a simple ASCII bar chart of the number of comparisons (divided by 10, to account for small differences). Some…