1. Within a Python file named recursion.py, write the following functions:
(a) (4 points) power(b, n)
Returns the value of bn for any numeric b and any integer n (including negative integers). Do not use any loops, and do not use any built-in ways of computing powers. This function must be recursive.
(b) (4 points) count positives(stuff)
Returns how many positive integers (i.e., > 0) are contained in stuff. You may assume that stuff is a list of integers. Do not use any loops, and do not use any built-in ways of searching a list. This function must be recursive.
(c) (4 points) all even(stuff)
Returns whether or not stuff contains only even integers. If stuff is empty, this should return True. You may assume that stuff is a list of integers. Do not use any loops, and do not use any built-in ways of searching a list. This function must be recursive.
(d) (6 points) binary search(stuff, target)
Returns the index of target within the list stuff if it exists, or -1 if it doesn’t exist. You may assume that stuff is a sorted list of integers, and target is an integer. Do not use any loops, and do not use any built-in ways of searching a list. This must be done recursively; you can write a recursive helper function if needed.
(e) (6 points) After your function definitions in recursion.py, write some tests for your func- tions. Be sure to test at least the following scenarios:
• power - Negative, zero, and positive exponents
• count positives - List contains all positive integers, list contains all non-positive integers, list contains a mix of positive/non-positive integers, list is empty
1
• all even - List contains all even integers, list contains all odd integers, list contains a mix of even/odd integers, list is empty
• binary search - Target is in the list, target is too low for the list, target is too high for the list, target is within the range of the list but not present, list is empty
2. As discussed in class, the quicksort algorithm starts by partitioning the list: a pivot value is selected, and the list is partitioned around that pivot. For this problem we’ll assume that
• The pivot is always the element at index 0 of the original list (i.e., before any rearranging of elements is performed).
• After partitioning, all the elements to the left of the pivot are the pivot, and all the elements to the right of the pivot are > the pivot.
In the following parts, assume that stuff is a list of integers.
(a) (7 points) Consider this naive algorithm for partitioning a list stuff:
1. Create two new low and high lists. These will be used to store the elements of stuff
that are ≤ or > the pivot, respectively.
2. Loop through all elements of stuff besides the pivot. If the element is the pivot, copy it into low. If the element is > the pivot, copy it into high.
3. Copy the elements of low back into stuff, then the pivot back into stuff, and finally the elements of high back into stuff.
Within a Python file named partitioning.py, write a function partition naive(stuff) that implements the above algorithm. The function should return the final index of the pivot, after partitioning is complete. Note that partition naive doesn’t need to return the partitioned list because the actions that it performs will affect the original list argu- ment. Make sure that your function works for a list of any length ≥ 1.
(b) (7 points) The partitioning algorithm from the previous part is not very efficient. Creating the two lists low and high requires extra time as well as memory. A better way is to perform the partition in-place, which means that no new lists are created. Instead, we just modify the elements of the original list directly.
Suppose we have a list a containing the elements [10, 5, 16, 14, 2, 10, 13]. As before, we want to use the first element (10) as the pivot. Here’s an algorithm to perform an in-place partition:
1. Create two indices, L and U. Start L from the beginning of the list; start U from the end.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
