Mod 6 Lab - Ordered List ADT with Binary Search The Ordered List ADT is similar to a list, but adds the requirement that items remain sorted: add (item) - adds item to the list. • remove(item) - removes the first occurrence of item from the list. Raise a RuntimeError if the item is not present. • getitem(index) - returns the item with the given index in the sorted list. This is also known as selection. contains (item) - returns True iff there is an item of the list equal to item. iter - returns an iterator over the ordered list that yields the items in sorted order. len - returns the length of the ordered list. . We have provided a working Ordered List in lab6.py . The starter code includes 3 ways of implementing contains : _bs (???) - up to you to implement. Should be O(logn). _contains_list(item) - uses python's built-in list search. O(n). contains_bs_slow(item) - uses a binary search built on slicing. O(n). def _contains_(self, item): return self._bs (item, 0, len(self)) # alternative search algorithms: # return self._contains_list(item) # return self._contains_bs_slow(item) # Requires _bs() for this to work # uses python's default list-search # uses a slow version of binary-search (slicing)

Mod 6 Lab - Ordered List ADT with Binary Search The Ordered List ADT is similar to a list, but adds the requirement that items remain sorted: add (item) - adds item to the list. • remove(item) - removes the first occurrence of item from the list. Raise a RuntimeError if the item is not present. • getitem(index) - returns the item with the given index in the sorted list. This is also known as selection. contains (item) - returns True iff there is an item of the list equal to item. iter - returns an iterator over the ordered list that yields the items in sorted order. len - returns the length of the ordered list. . We have provided a working Ordered List in lab6.py . The starter code includes 3 ways of implementing contains : _bs (???) - up to you to implement. Should be O(logn). _contains_list(item) - uses python's built-in list search. O(n). contains_bs_slow(item) - uses a binary search built on slicing. O(n). def _contains_(self, item): return self._bs (item, 0, len(self)) # alternative search algorithms: # return self._contains_list(item) # return self._contains_bs_slow(item) # Requires _bs() for this to work # uses python's default list-search # uses a slow version of binary-search (slicing)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

check_equivalency(tokens): Takes a list as input. Returns True if the list contains three elements, the second element is an equals sign ('='), and the first and third elements are equal to each other. Returns False otherwise.
python help Q5: Compose Write the procedure composed, which takes in procedures f and g and outputs a new procedure. This new procedure takes in a number x and outputs the result of calling f on g of x. (define (composed f g) 'YOUR-CODE-HERE ) Q6: Remove Implement a procedure remove that takes in a list and returns a new list with all instances of item removed from lst. You may assume the list will only consist of numbers and will not have nested lists. Hint: You might find the filter procedure useful. (define (remove item lst) 'YOUR-CODE-HERE ) ;;; Tests (remove 3 nil) ; expect () (remove 3 '(1 3 5)) ; expect (1 5) (remove 5 '(5 3 5 5 1 4 5 4)) ; expect (3 1 4 4)
Arithmetic progression def arithmetic_progression(items): An arithmetic progression is a numerical sequence so that the stride between each two consecutive elements is constant throughout the sequence. For example, [4, 8, 12, 16, 20] is an arithmetic progression of length 5, starting from the value 4 with a stride of 4. Given a non-empty list items of positive integers in strictly ascending order, find and return the longest arithmetic progression whose all values exist somewhere in that sequence. Return the answer as a tuple (start, stride, n) of the values that define the progression. To ensure unique results to facilitate automated testing, if there exist several progressions of the same length, this function should return the one with the lowest start. If several progressions of equal length emanate from the lowest start, return the progression with the smallest stride. items expected results [42] (42, 0, 1) [2, 4, 6, 7, 8, 12, 17] (2, 2, 4) [1, 2, 36, 49, 50, 70, 75, 98,…
find_last(my_list, x): Takes two inputs: the first being a list and the second being any type. Returns the index of the last element of the list which is equal to the second input; if it cannot be found, returns None instead. >>> find_last(['a', 'b', 'b', 'a'], 'b') 2 >>> ind = find_last(['a', 'b', 'b', 'a'], 'c') >>> print(ind) None • find_first(my_list, x): Takes two inputs: the first being a list and the second being any type. Returns the index of the first element of the list which is equal to the second input; if it cannot be found, returns None instead. >>> find_first(['a', 'b', 'b', 'a'], 'b') 1 >>> ind = find_first(['a', 'b', 'b', 'a'], 'c') >>> print(ind) None In python
find_last(my_list, x): Takes two inputs: the first being a list and the second being any type. Returns the index of the last element of the list which is equal to the second input; if it cannot be found, returns None instead. >>> find_last(['a', 'b', 'b', 'a'], 'b') 2 >>> ind = find_last(['a', 'b', 'b', 'a'], 'c') >>> print(ind) None
Count dominators def count_dominators(items): An element of items is said to be a dominator if every element to its right (not just the one element that is immediately to its right) is strictly smaller than it. By this definition, the last item of the list is automatically a dominator. This function should count how many elements in items are dominators, and return that count. For example, dominators of [42, 7, 12, 9, 13, 5] would be the elements 42, 13 and 5. Before starting to write code for this function, you should consult the parable of "Shlemiel the painter" and think how this seemingly silly tale from a simpler time relates to today's computational problems performed on lists, strings and other sequences. This problem will be the first of many that you will encounter during and after this course to illustrate the important principle of using only one loop to achieve in a tiny fraction of time the same end result that Shlemiel achieves with two nested loops. Your workload…
Split - Filter - Sort romeo = 'But soft what light through yonder window breaks It is the east and Juliet is the sun Arise fair sun and kill the envious moon Who is already sick and pale with grief Split the long string romeo into a list of words using the split function. For each word, check to see if the word is already in a list. If the word is not in the list, add it to the list. When the program completes, sort and print the resulting words in alphabetical order. The result will be like this: ['Arise', 'But', 'It', 'Juliet', "Who', 'already', 'and', 'breaks', 'east', 'envious', 'fair', 'grief', 'is', 'kill', "'ight', 'moon', 'pale', 'sick', 'soft', 'sun', 'the', 'through', 'what', 'window', 'with', 'yonder']
Remove Char This function will be given a list of strings and a character. You must remove all occurrences of the character from each string in the list. The function should return the list of strings with the character removed. Signature: public static ArrayList<String> removeChar(String pattern, ArrayList<String> list) Example:list: ['adndj', 'adjdlaa', 'aa', 'djoe']pattern: a Output: ['dndj', 'djdl', '', 'djoe']
Array List.
5 partition_list (head) This is a little like split_list() from the Short problem, except that, instead of splitting the list into two by cutting it into the middle, you will now build two lists to return, using alternate values. The first value in the input list should be returned at the head of the first new list; the second value should be the head of the second list. Keep on alternating from there, putting one new value on the first list, and one on the second. (But remember that the length of the input list might be odd.) Example Suppose you have the following input list: 10 - 13 -> -1 -> 1000 - 0 It should return the following two lists: 10 1 0 13 -> 1000
Write the following function that returns true if the list is already sorted in increasing order:def isSorted(lst):Write a test program that prompts the user to enter a list and displays whether the list is sorted or not.
Array List: Write a program that reads in words and prints them out in reverse order. Complete this code.