def selection_sort(L): Pre: L is a list of numbers Post: L is sorted in non-decreasing order II III # i indicates how many items were sorted for i in range (len(L)): # To find the minimum value of the unsorted segment # We first assume that the first element is the lowest min_index = i # We then use j to loop through the remaining elements for j in range (i+1, len(L)): # Update the min_index if the element at j is lower than it if L[j] < L[min_index]: min_index j # After finding the lowest item of the unsorted regions, # swap with the first unsorted item L[i], L[min_index] L [min_index], L[i] %3D The loop invariant for the outer loop is rather simple: 0 < i < len(L) and L[0 : i] is sorted. Clearly, once the loop finishes and i = len(L), this implies the postcondi- tion, and L is sorted. State and prove the loop invariant for the inner loop that can be used to prove the loop invariant for the outer loop. However, you do not need to prove how it is connected to the outer loop (though this is good practice). Hint: You should start by fixing a value for i, and assuming the outer loop in- variant holds for that i. You should use this assumption in your proof for the inner loop invariant.

def selection_sort(L): Pre: L is a list of numbers Post: L is sorted in non-decreasing order II III # i indicates how many items were sorted for i in range (len(L)): # To find the minimum value of the unsorted segment # We first assume that the first element is the lowest min_index = i # We then use j to loop through the remaining elements for j in range (i+1, len(L)): # Update the min_index if the element at j is lower than it if L[j] < L[min_index]: min_index j # After finding the lowest item of the unsorted regions, # swap with the first unsorted item L[i], L[min_index] L [min_index], L[i] %3D The loop invariant for the outer loop is rather simple: 0 < i < len(L) and L[0 : i] is sorted. Clearly, once the loop finishes and i = len(L), this implies the postcondi- tion, and L is sorted. State and prove the loop invariant for the inner loop that can be used to prove the loop invariant for the outer loop. However, you do not need to prove how it is connected to the outer loop (though this is good practice). Hint: You should start by fixing a value for i, and assuming the outer loop in- variant holds for that i. You should use this assumption in your proof for the inner loop invariant.

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

Recamán's sequence def recaman(n): Compute and return the first n terms of the Recamán's sequence, starting from the term a1 = 1.Note how the definition for the current next element depends on whether a particular number is already part of the previously generated part of the sequence. To let your function execute in a speedy fashion even when generating a sequence that contains millions of elements, you should use a set to keep track of which values are already part of the previously generated sequence. This way you can generate each element in constant time, instead of having to iterate through the entire previously generated list. The better technique that saves time by using more memory can create this list arbitrarily far in linear time, and should therefore be fast even for millions of elements, at least until it runs out of memory. n Expected result 10 [1, 3, 6, 2, 7, 13, 20, 12, 21, 11] 1000000 (a list of million elements whose last five elements are [2057162,1057165,…
X40: sum3 Given an array containing three ints, return the sum of all the elements. Examples: sum3({1, 2, 3}) -> 6 sum3({5, 11, 2}) -> 18 Your Answer: 1 public int sum3(int[] nums) 2{ 3 4} Check my answer! Reset Next exercise
Q2 You have a dynamic array with 3 elements in it and a capacity of 4. The capacity doubles when additional space is needed and shrinks by 50% (rounding down) when the size is at or below 1/3 capacity. Answer the questions below for the following operation sequence: Add, Add, Remove, Remove, Remove Q2.1 What will be the capacity of the list when the whole sequence is completed? Answer= Enter your answer here
Tradng SelCLOon Write the state of the elements of the vector below after each of the first 3 passes of the outermost loop of the selection sort algorithrm // index 0 1 2 3 4 5 6 7 Vector numbers = {29, 17, 3, 94, 46, 8, -4, 12}; selectionSort(numbers); For example, if the vector was {(43125), you would write: {4 3 1 2 5} {1 3 4 2 5} (1 2 4 3 5} {1 2 3 4 5} Thought: How many vectors would I need here if I were to implement this in code? Write your answer here. hp
# Initialize sets A and BA = { 'a', 'b', 'c', 'd', 'e', 'f' }B = { 'c', 'd', 'f', 'h', 'j', 'k' } print('A = ', sorted(A))print('B = ',sorted(B))print(' ') AsymdiffB = set()# put your code here to compute the symmetric difference of A and B# first add all the elements that are in A but not B# then add all the elements that are in B but not A print('Symmetric Difference of A and B = ', sorted(AsymdiffB))