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.
- The Euler Project
- Coding Bat
- The Cow Competition has a great training program if you are interested in programming contests.
Algorithms
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.
input: a list of numbers output: total start a running total = 0 for each item in the list add it to the total output will be the total
Count the number of elements in a numerical list larger than some specified value
inputs: a list (x), a threshhold value (value)
set a counter to 0.
for each item in the list
if it's bigger than the threshhold value
increment the count
return the count
Compute the product of a list of numbers.
input : a list
product = 1
for each item in the list
mulitply prodcut by item
ret product
Tell how many times a character occurs in a string.
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 stirings
start with an empty list.
for each item in the input list:
if it's in the first half of the alphabet:
add it to output list
return the output list
output: a list of strings that has been filtered
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.
input: list (x), item sought (quarry)
for each item in x:
return True if that item is the quarry
return False
If the list is twice as long, about how much harder does this function have to work?
It works about twice a long.
This algorithm is called O(n) because the amount of work it takes is as worst proportional to the size of the list. (n is the "size" of the problem) This is a linear-time algorithm.
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.
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.
- Given a decimal number n, calculate its binary representation as a string.
- Compute the sum of a number's decimal digits.
- Compute the sum of a number's base \(b\) digits.
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!\).
Sorting
Why do we sort collections?
Time for some Bubble Tea
Big O