Places to Hone Skills Python gives you a means to tell the computer how to carry out a complex task. This chapter is full of examples and problems that will build your coding skill. You are Turing-complete! I encourage you to try some of these things.
An algorithm is just a precise set of instructions for performing a task. Cookbooks are full of 'em. Are you hungry now?
Your algorithm is a plan for accomplishing a task. Today we will look at some basic computing tasks and have you come up with ideas for solutions.
This is a looping operation.
$$\sum_{k=1}^n a_k$$So is this.
$$\prod_{k=1}^n a_k$$As we shall see, Python defangs these fearsome-looking things into simple loops.
What is "work?" The unit of computer work is the byte-second. That is a measure of how much memory you are using for how long. The two resources used in computing are memory and time. Using tons of memory makes things run faster. You can use less memory if you are willing to wait.
Accumulation Tasks Compute the sum of number in a numerical list or tuple from scratch.
adding every index of the list together
sum =0
for k in list:
sum = sum + item at index k
accumulator variable:
input: some list
set running total to zero
for each item in the list
add the item to the running total
sumbody
Count the number of elements in a numerical list larger than some specified value
input: some specified value
a numerical list
set a count to 0
for aech item in the list:
if value is large enough,
icrement the countn
Compute the product of a list of numbers.
input: a list of numbers
Product = 1
For k in x
Product *= k
Return product
product = 1
for an element in the list:
multiply element by product
return product once loop ends
Tell how many times a character occurs in a string.
inputs: string and a character we are counting
set a counter to zero.
for each ch in the string:
if ch matches the specified character:
increment the count
return count
Filtering Task Get all of the strings in a list of strings in the first half of the alphabet, and return them in a list whilst leaving the original list untouched.
input: a list of strings Here is a quick trick brick stack. >>> s = "nature" >>> s[0].lower() <= "m" False
Go through a word list and return a list of words beginning with reguar vowels (aeiou)
Searching Tasks Search a list for an item and return True if the item is present.
inputs: the list and the item
for each item inthe list:
if the item matches the quarry, return True
return False if we make it all the way through.
If the list is twice as long, about how much harder does this function have to work?
The amount of work is at most proportional to the size of the list. In that case we say this algorithm is O(n). This is a linear time algorithm.
Search a list for an item and return the index of the first instance of that item, or a -1 if it is not present.
inputs: list, the specified item ( x, item) FRANKENCODE
Search a list for an item and return the index of the last instance of that item, or a -1 if it is not present.
Assorted Bonbons Here is a motley assortment of problems.
Interesting challenge problem. The number of subsets of size \(k\) of a set of size \(n\) is
$${n\choose k} = {n!\over k!(n-k)!} = {n\cdot (n-1)\cdot(n-2) \cdots (n-k+1)\over 1\cdot 2 \cdot 3 \cdots k}.$$if \(0\le k \le n\) and 0 otherwise.
Here is a useful fact: the product of \(k\) consecutive integers is always divisible by \(k!\).
Why do we sort collections?
Time for some Bubble Tea
Big O