Very quickly we have moved past Unit 4. The Homework 4 series is quite challenging and might take a while to solve. But solving them just gave me a boost of adrenaline, which explains why I’ve started on Unit 5, 2 weeks ahead of schedule! Join me if you are on a roll too, if not you can always revisit this page and the subsequent articles.
Unit 5 starts with talking about the the cost of running programs. The problem of the cost is called Algorithm Analysis, and there are people with careers devoted to this field. It is actually a fundamental problem of computation. An algorithm is a well-defined procedure that can be executed mechanically, will always finish and produce the correct result.
The cost of an algorithm is not measured by dollars and cents, but rather by speed and storage. Algorithm analysis is about understanding how the inputs will affect the time taken and storage memory required for algorithm to complete. Or to phrase it different, when the inputs increase in size, how does the time and storage requirement scale with relation to size?
We are introduced to a new python library called time:
Measure how much time your program takes
Image courtesy of http://catherinethegame.wikia.com
import time
start = time.clock() # this will give us the current processor time of running clock() method
end = time.clock()
time_taken = end - start # finding the time taken is a matter of taking the difference between two calls of clock() method
There are many types of algorithms, but they can mainly be classified into how they scale with relation to their input size. The scaling of the cost of an algorithm in relation to the input size is something called the growth of an algorithm, and there is an specific notation called the Big O notation. The spin loop algorithm in Chapter 5 is an example of an algorithm that scales linearly, as input size doubles, the costs roughly doubles. Other types of algorithms include quadratic, exponential and logarithmic. All these algorithm analysis stuff is part of a bigger field called Computational Complexity theory, and will take you about a week just reading the Wikipedia entry, and maybe ten years to understand. Definitely not for the faint-hearted!
Anzai 