Problem Set 1

The question has template files in the repository. You’ll need to grab the assignment from the link below and download the entire folder to your computer before proceeding. I would highly suggest then opening the entire folder in VS Code, as it will make it very easy to edit the different files and is necessary for VS Code to find certain libraries. When you are finished, upload your completed templates back to GitHub. Don’t worry about changing any file names, you want to overwrite the original template files.

Accept Assignment

Problem 1

A sequential search of a sorted list can halt when the target is less than a given element in the list. Define a modified version of this algorithm and state the computational complexity, using big-O notation, of its best-, worst-, and average-case performances.

Problem 2

The list method reverse reverses the elements in the list. Define a function named reverse that reverses the elements in its list argument (without using the method Python’s reverse). Try to make this function as efficient as possible, and state its computational complexity using big-O notation.

Problem 3

Python’s pow function returns the result of raising a number to a given power. Define a function expo that performs this task and state its computational complexity using big-O notation. The first argument of this function is the number, and the second argument is the exponent (nonnegative numbers only). You can use either a loop or a recursive function in your implementation, but do not use Python’s ** operator or Python’s pow function.

Problem 4

Python’s list method sort includes the keyword argument reverse, whose default value is False. The programmer can override this value to sort a list in descending order. Modify the selectionSort function discussed in this chapter so that it allows the programmer to supply this additional argument to redirect the sort.