Difference between revisions of "Chapter 10"

From IPRE Wiki
Jump to: navigation, search
(From algorithms to a working program)
Line 1: Line 1:
==Computers and Computation==
+
>==Computers and Computation==
 
{|
 
{|
 
|[[Image:PutersPutation.jpg|left]]
 
|[[Image:PutersPutation.jpg|left]]
 
''Home computers are being called upon to perform many new functions, including the consumption of homework formerly eaten by the dog.''
 
''Home computers are being called upon to perform many new functions, including the consumption of homework formerly eaten by the dog.''
<br> -: Doug Larson
+
&lt;br&gt; -: Doug Larson
<br><br>
+
&lt;br&gt;&lt;br&gt;
 
''Computer Science is no more about computers than astronomy is about telescopes.''
 
''Computer Science is no more about computers than astronomy is about telescopes.''
<br> -: Edsger W. Dijkstra  
+
&lt;br&gt; -: Edsger W. Dijkstra  
<br><br>
+
&lt;br&gt;&lt;br&gt;
 
''What is the central core of computer science? What is it that distinguishes it from the separate subjects with which it is related? What is the linking thread which gathers these disparate branches into a single discipline. My answer to these questions is simple -it is the art of programming a computer. It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex. It is the art of translating this design into an effective and accurate computer program.''  
 
''What is the central core of computer science? What is it that distinguishes it from the separate subjects with which it is related? What is the linking thread which gathers these disparate branches into a single discipline. My answer to these questions is simple -it is the art of programming a computer. It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex. It is the art of translating this design into an effective and accurate computer program.''  
<br> -: C.A.R. Hoare
+
&lt;br&gt; -: C.A.R. Hoare
 
|}
 
|}
  
Line 15: Line 15:
  
 
===Computers are dumb===
 
===Computers are dumb===
Say you are hosting an international exchange student in your home. Soon after her arrival you teach her the virtues of PB&J (Peanut Butter & Jelly) sandwiches. After keenly listening to you, her mouth starts to water and she politely asks you if you can share the recipe with her. You write it down on a piece of paper and hand it to her.
+
Say you are hosting an international exchange student in your home. Soon after her arrival you teach her the virtues of PB&amp;J (Peanut Butter &amp; Jelly) sandwiches. After keenly listening to you, her mouth starts to water and she politely asks you if you can share the recipe with her. You write it down on a piece of paper and hand it to her.
  
'''Exercise:''' Go ahead, write down the recipe to make a PB&J sandwich.
+
'''Exercise:''' Go ahead, write down the recipe to make a PB&amp;J sandwich.
  
 
Seriously, do try to write it down. We insist!
 
Seriously, do try to write it down. We insist!
  
OK, now you have a recipe for making PB&J sandwiches.  
+
OK, now you have a recipe for making PB&amp;J sandwiches.  
  
'''Exercise:''' Go ahead, use your recipe from above to make yourself a PB&J sandwich. try to follow the instructions ''exactly'' as ''literally'' as you can.  
+
'''Exercise:''' Go ahead, use your recipe from above to make yourself a PB&amp;J sandwich. try to follow the instructions ''exactly'' as ''literally'' as you can.  
  
If you successfully managed to make a PB&J sandwich, congratulations! Go ahead and enjoy it.
+
If you successfully managed to make a PB&amp;J sandwich, congratulations! Go ahead and enjoy it.
  
Do you think that your friend will be able to follow your recipe and enjoy PB&J sandwiches?
+
Do you think that your friend will be able to follow your recipe and enjoy PB&amp;J sandwiches?
  
You have to agree, writing a recipe for PB&J sandwiches seemed trivial at first, but when you sit down to write it you have no choice but to question several assumptions: does she know what peanut butter is? should I recommend a specific brand? ditto for jelly? By the way, did you forget to mention it was ''grape jelly''? what kind of bread to use? will it be pre-sliced? if not, you need a knife for slicing the loaf? did you specify how thick the slices should be? should she use the same knife for spreading the peanut butter and the jelly? etc. etc. The thing is, at such a level of detail you can go on and on...does your friend know how to use a knife to spread butter or jelly on a slice? Suddenly, a seemingly trivial task becomes a daunting exercsie. In reality, in writing down your recipe, you make several assumptions: she knows what a sandwich is, it involves slices of bread, spreading things on the slices, and slapping them together. There, you have a sandwich!
+
You have to agree, writing a recipe for PB&amp;J sandwiches seemed trivial at first, but when you sit down to write it you have no choice but to question several assumptions: does she know what peanut butter is? should I recommend a specific brand? ditto for jelly? By the way, did you forget to mention it was ''grape jelly''? what kind of bread to use? will it be pre-sliced? if not, you need a knife for slicing the loaf? did you specify how thick the slices should be? should she use the same knife for spreading the peanut butter and the jelly? etc. etc. The thing is, at such a level of detail you can go on and on...does your friend know how to use a knife to spread butter or jelly on a slice? Suddenly, a seemingly trivial task becomes a daunting exercsie. In reality, in writing down your recipe, you make several assumptions: she knows what a sandwich is, it involves slices of bread, spreading things on the slices, and slapping them together. There, you have a sandwich!
  
 
Think of the number of recipes that have been published in cookbooks all over the world. Most good cookbook authors start with a dish, write down a recipe, try it a number of times and refine it in different ways. Prior to publication, the recipe is tested by others. After all the recipe is for others to follow and recreate a dish. The recipe is revised and adjusted based on feedback by recipe testers. The assumption that cookbook authors make is that you will have the competence to follow the recipe and recreate the dish to your satisfaction. It may never result in the same dish that the author prepared. But it will give you a base to improvise upon. Wouldn't it be nice if there was an exact way of following a recipe so that you end up with the exact same result as the cookbook author everytime you made that dish? Would it? That may depend on your own tastes and preferences. Just for fun, here is a recipe for ...
 
Think of the number of recipes that have been published in cookbooks all over the world. Most good cookbook authors start with a dish, write down a recipe, try it a number of times and refine it in different ways. Prior to publication, the recipe is tested by others. After all the recipe is for others to follow and recreate a dish. The recipe is revised and adjusted based on feedback by recipe testers. The assumption that cookbook authors make is that you will have the competence to follow the recipe and recreate the dish to your satisfaction. It may never result in the same dish that the author prepared. But it will give you a base to improvise upon. Wouldn't it be nice if there was an exact way of following a recipe so that you end up with the exact same result as the cookbook author everytime you made that dish? Would it? That may depend on your own tastes and preferences. Just for fun, here is a recipe for ...
Line 56: Line 56:
 
Computer programs are also like recipes, to some extent. Think of the program you wrote for choreographing a robot dance, for instance. We have reproduced the version from Chapter 3 here:
 
Computer programs are also like recipes, to some extent. Think of the program you wrote for choreographing a robot dance, for instance. We have reproduced the version from Chapter 3 here:
  
<pre>
+
&lt;pre&gt;
 
# File: dance.py
 
# File: dance.py
 
# Purpose: A simple dance routine
 
# Purpose: A simple dance routine
Line 63: Line 63:
  
 
from myro import *
 
from myro import *
initialize("com5")
+
initialize(&quot;com5&quot;)
 
   
 
   
 
# Define the new functions...
 
# Define the new functions...
Line 83: Line 83:
 
# The main dance program
 
# The main dance program
 
def main():
 
def main():
       print "Running the dance routine..."
+
       print &quot;Running the dance routine...&quot;
 
       yoyo(0.5, 0.5)
 
       yoyo(0.5, 0.5)
 
       wiggle(0.5, 0.5)
 
       wiggle(0.5, 0.5)
 
       yoyo(1, 1)
 
       yoyo(1, 1)
 
       wiggle(1, 1)
 
       wiggle(1, 1)
       print "...Done"
+
       print &quot;...Done&quot;
  
 
main()
 
main()
</pre>
+
&lt;/pre&gt;
 
In many ways, this program above is like a recipe:
 
In many ways, this program above is like a recipe:
  
Line 97: Line 97:
  
 
;Ingredients
 
;Ingredients
:1 function called <tt>yoyo</tt> that enables the robot to go back and forth at a given speed
+
:1 function called &lt;tt&gt;yoyo&lt;/tt&gt; that enables the robot to go back and forth at a given speed
:1 function called <tt>wiggle</tt> that enables the robot to wiggle at a given speed
+
:1 function called &lt;tt&gt;wiggle&lt;/tt&gt; that enables the robot to wiggle at a given speed
  
 
'''Preparation'''
 
'''Preparation'''
# <tt>yoyo</tt> at speed 0.5, wait 0.5
+
# &lt;tt&gt;yoyo&lt;/tt&gt; at speed 0.5, wait 0.5
# <tt>wiggle</tt> at speed 0.5, wait 0.5
+
# &lt;tt&gt;wiggle&lt;/tt&gt; at speed 0.5, wait 0.5
# <tt>yoyo</tt> at speed 1, wait 1
+
# &lt;tt&gt;yoyo&lt;/tt&gt; at speed 1, wait 1
# <tt>wiggle</tt> at speed 1, wait 1
+
# &lt;tt&gt;wiggle&lt;/tt&gt; at speed 1, wait 1
  
Further, you could similarly specify the steps involved in doing the <tt>yoyo</tt> and <tt>wiggle</tt> motions as a recipe. This may seem like a trivial example, but it makes a couple of very important points: a computer program is like a recipe in that it lays out the list of ingredients and a method or steps for accomplishing the given task; and, like a recipe, its ingredients and the steps require careful pre-planning and thought. More importantly, computer programs are different from recipes in one aspect: they are designed to be followed by a computer!
+
Further, you could similarly specify the steps involved in doing the &lt;tt&gt;yoyo&lt;/tt&gt; and &lt;tt&gt;wiggle&lt;/tt&gt; motions as a recipe. This may seem like a trivial example, but it makes a couple of very important points: a computer program is like a recipe in that it lays out the list of ingredients and a method or steps for accomplishing the given task; and, like a recipe, its ingredients and the steps require careful pre-planning and thought. More importantly, computer programs are different from recipes in one aspect: they are designed to be followed by a computer!
  
 
A computer is basically a dumb device designed to follow instructions/recipes. We will save the technical details of how a computer does what it does for a later course. But is is almost common knowledge that everything ''inside'' is represented as 0's and 1's. Starting from 0's and 1's one can design encoding schemes to represent numbers, letters of the alphabet, documents, images, movies, music, etc. and whatever other abstract entities you would like to manipulate using a computer. A computer program is ultimately also represented as a sequence of 0's and 1's and it is in this form that most computers like to follow recipes. However limiting or degenerate this might sound it is the key to the power of computers. Especially when you realize that it is this simplification that enables a computer to manipulate hundreds of millions of pieces of information every second. The price we have to pay for all this power is that we have to specify our recipes as computer programs in a rather formal/precise manner. So much so that there is no room for improvisation: no pinch of salt vagaries, as in cooking recipes, are acceptable. This is where ''programming languages'' come in. Computer scientists specify their computational recipes using ''programming languages''. You have been using the programming language Python to write your robot programs. Other examples of programming languages are Java, C++ (pron.: sea plus plus), C# (pron.: sea sharp), etc. There are well over 2000 programming languages in existence!
 
A computer is basically a dumb device designed to follow instructions/recipes. We will save the technical details of how a computer does what it does for a later course. But is is almost common knowledge that everything ''inside'' is represented as 0's and 1's. Starting from 0's and 1's one can design encoding schemes to represent numbers, letters of the alphabet, documents, images, movies, music, etc. and whatever other abstract entities you would like to manipulate using a computer. A computer program is ultimately also represented as a sequence of 0's and 1's and it is in this form that most computers like to follow recipes. However limiting or degenerate this might sound it is the key to the power of computers. Especially when you realize that it is this simplification that enables a computer to manipulate hundreds of millions of pieces of information every second. The price we have to pay for all this power is that we have to specify our recipes as computer programs in a rather formal/precise manner. So much so that there is no room for improvisation: no pinch of salt vagaries, as in cooking recipes, are acceptable. This is where ''programming languages'' come in. Computer scientists specify their computational recipes using ''programming languages''. You have been using the programming language Python to write your robot programs. Other examples of programming languages are Java, C++ (pron.: sea plus plus), C# (pron.: sea sharp), etc. There are well over 2000 programming languages in existence!
Line 114: Line 114:
 
Prior to the existence of programming languages computers were programmed using long sequences of 0's and 1's. Needless to say it drove several people crazy! Programming languages, like Python, enable a friendlier way for programmers to write programs. Programming languages provide easy access to encodings that represent the kinds of things we, humans, relate to. For example, the Python statement:
 
Prior to the existence of programming languages computers were programmed using long sequences of 0's and 1's. Needless to say it drove several people crazy! Programming languages, like Python, enable a friendlier way for programmers to write programs. Programming languages provide easy access to encodings that represent the kinds of things we, humans, relate to. For example, the Python statement:
  
<pre>
+
&lt;pre&gt;
 
meaningOfLife = 42
 
meaningOfLife = 42
</pre>
+
&lt;/pre&gt;
  
is a command for the computer to associate the value, 42 with the name <tt>meaningOfLife</tt>. This way, we can ask the computer to check that it is indeed 42:
+
is a command for the computer to associate the value, 42 with the name &lt;tt&gt;meaningOfLife&lt;/tt&gt;. This way, we can ask the computer to check that it is indeed 42:
  
<pre>
+
&lt;pre&gt;
  
 
if meaningOfLife == 42:
 
if meaningOfLife == 42:
     print "Eureka!"
+
     print &quot;Eureka!&quot;
 
else:
 
else:
     print "What do we do now?"
+
     print &quot;What do we do now?&quot;
  
</pre>
+
&lt;/pre&gt;
  
Once again, it would be good to remind you that the choice of the name, <tt>meaningOfLife</tt>, doesn't really mean that we are talking about ''the meaning of life''. We could as well have called it <tt>timbuktoo</tt>, as in:
+
Once again, it would be good to remind you that the choice of the name, &lt;tt&gt;meaningOfLife&lt;/tt&gt;, doesn't really mean that we are talking about ''the meaning of life''. We could as well have called it &lt;tt&gt;timbuktoo&lt;/tt&gt;, as in:
  
<pre>
+
&lt;pre&gt;
 
timbuktoo = 42
 
timbuktoo = 42
</pre>
+
&lt;/pre&gt;
  
 
You see, computers are truly dumb!
 
You see, computers are truly dumb!
Line 153: Line 153:
  
 
|[[Image:TwoCartons.jpg|left]]
 
|[[Image:TwoCartons.jpg|left]]
Every USDA certified egg carton has at least three pieces of information (see picture on left): a "sell by" date (or a "use by date" or a "best by" date), a code identifying the specific farm the eggs came from, and a date on which the eggs were packed in that carton.
+
Every USDA certified egg carton has at least three pieces of information (see picture on left): a &quot;sell by&quot; date (or a &quot;use by date&quot; or a &quot;best by&quot; date), a code identifying the specific farm the eggs came from, and a date on which the eggs were packed in that carton.
Most people buy eggs by looking at the "sell by" date or the "best by" date. However the freshness information is really encoded in the packed on date. To make things more confusing, this date is encoded as the day of the year.
+
Most people buy eggs by looking at the &quot;sell by&quot; date or the &quot;best by&quot; date. However the freshness information is really encoded in the packed on date. To make things more confusing, this date is encoded as the day of the year.
  
For example, take a look at the top carton shown on the left. Its "sell by" date is October 14. "P1107" is the farm code. This carton was packed on the 248th day of the year. Further, USDA requires that all certified eggs be packed within 7 days of being laid. Thus, the eggs in the top carton were laid somewhere between day 241 and day 248 of 2007. What dates correspond to those dates?
+
For example, take a look at the top carton shown on the left. Its &quot;sell by&quot; date is October 14. &quot;P1107&quot; is the farm code. This carton was packed on the 248th day of the year. Further, USDA requires that all certified eggs be packed within 7 days of being laid. Thus, the eggs in the top carton were laid somewhere between day 241 and day 248 of 2007. What dates correspond to those dates?
  
Next, look at the bottom carton. Those eggs have a later "sell by" date (October 18) but an earlier packed date: 233. That is those eggs were laid somewhere between day 226 and day 233 of 2007.
+
Next, look at the bottom carton. Those eggs have a later &quot;sell by&quot; date (October 18) but an earlier packed date: 233. That is those eggs were laid somewhere between day 226 and day 233 of 2007.
  
 
Which eggs are more fresh?
 
Which eggs are more fresh?
  
Even though the "sell by" date on the second carton is two weeks later, the first carton contains fresher eggs. In fact, those eggs were laid at least two weeks later!
+
Even though the &quot;sell by&quot; date on the second carton is two weeks later, the first carton contains fresher eggs. In fact, those eggs were laid at least two weeks later!
  
 
The packed on date is encoded as a 3-digit number. Thus eggs packed on January 1 will be labelled: 001; eggs packed on December 31, 2007 will be labelled: 365.
 
The packed on date is encoded as a 3-digit number. Thus eggs packed on January 1 will be labelled: 001; eggs packed on December 31, 2007 will be labelled: 365.
Line 201: Line 201:
 
Suppose we are trying to decode the input 248, 2007. If you were to do this by hand, using a pen and paper, the process might go something like this:
 
Suppose we are trying to decode the input 248, 2007. If you were to do this by hand, using a pen and paper, the process might go something like this:
  
<pre>
+
&lt;pre&gt;
 
The date is not in January because it has 31 days and 248 is much larger than 31.
 
The date is not in January because it has 31 days and 248 is much larger than 31.
 
Lets us subtract 31 out of 248: 248 - 31 = 217
 
Lets us subtract 31 out of 248: 248 - 31 = 217
Line 230: Line 230:
  
 
The answer is: 248th day of 2007 is September 5, 2007.
 
The answer is: 248th day of 2007 is September 5, 2007.
</pre>
+
&lt;/pre&gt;
  
 
That was obviously too repetitious and tedious. But that is where computers come in. Take a look at the process above and see if there is a pattern to the steps performed. Sometimes, it is helpful to try another example.
 
That was obviously too repetitious and tedious. But that is where computers come in. Take a look at the process above and see if there is a pattern to the steps performed. Sometimes, it is helpful to try another example.
Line 236: Line 236:
 
'''Exercise:''' Suppose the input day and year are: 56, 2007. What is the date?
 
'''Exercise:''' Suppose the input day and year are: 56, 2007. What is the date?
  
When you look at the sample computations you have performed, you will see many patterns. Identifying these is the key to designing an algorithm. Sometimes, in order to make this easier, it is helpful to identify or name the key pieces of information being manipulated. Generally, this begins with the inputs and outputs identified in the problem specification. For example, in this problem, the inputs are: day of the year, current year. Begin by assigning these values to specific variable names. That is, let us assign the name <tt>day</tt> to represent the day of the year (248 in this example), and <tt>year</tt> as the name to store the current year (2007). Notice that we didn't choose to name any of these variables <tt>timbuktu</tt> or <tt>meaningOfLife</tt>!
+
When you look at the sample computations you have performed, you will see many patterns. Identifying these is the key to designing an algorithm. Sometimes, in order to make this easier, it is helpful to identify or name the key pieces of information being manipulated. Generally, this begins with the inputs and outputs identified in the problem specification. For example, in this problem, the inputs are: day of the year, current year. Begin by assigning these values to specific variable names. That is, let us assign the name &lt;tt&gt;day&lt;/tt&gt; to represent the day of the year (248 in this example), and &lt;tt&gt;year&lt;/tt&gt; as the name to store the current year (2007). Notice that we didn't choose to name any of these variables &lt;tt&gt;timbuktu&lt;/tt&gt; or &lt;tt&gt;meaningOfLife&lt;/tt&gt;!
  
Also, notice that you have to repeatedly subtract the number of days in a month, starting from January. Let us assign a variable named, <tt>month</tt> to keep track of the month under consideration.
+
Also, notice that you have to repeatedly subtract the number of days in a month, starting from January. Let us assign a variable named, &lt;tt&gt;month&lt;/tt&gt; to keep track of the month under consideration.
  
Next, you can substitute the names <tt>day</tt> and <tt>year</tt> in the sample computation:
+
Next, you can substitute the names &lt;tt&gt;day&lt;/tt&gt; and &lt;tt&gt;year&lt;/tt&gt; in the sample computation:
<pre>
+
&lt;pre&gt;
 
Input:
 
Input:
 
   day = 248
 
   day = 248
Line 294: Line 294:
  
 
The answer is: 9/5/2007
 
The answer is: 9/5/2007
</pre>
+
&lt;/pre&gt;
  
 
Notice now how repetitious the above process is. The repetition can be expressed more concisely as shown below:  
 
Notice now how repetitious the above process is. The repetition can be expressed more concisely as shown below:  
  
<pre>
+
&lt;pre&gt;
 
Input:
 
Input:
 
   day
 
   day
Line 314: Line 314:
  
 
Output: day/month/year
 
Output: day/month/year
</pre>
+
&lt;/pre&gt;
 
It is now starting to look like a recipe or an algorithm. Go ahead and try it with the sample inputs from above and ensure that you get correct results. Additionally, make sure that this algorithm will work for boundary cases: 001, 365, etc.
 
It is now starting to look like a recipe or an algorithm. Go ahead and try it with the sample inputs from above and ensure that you get correct results. Additionally, make sure that this algorithm will work for boundary cases: 001, 365, etc.
  
Line 327: Line 327:
 
     And twenty-nine in each leap year
 
     And twenty-nine in each leap year
  
From a design perspective, we can assume that we have an ingredient, a function in this case, called <tt>daysInMonth</tt> that, given a month and a year will compute and return the number of days in the month. That is, we can refine our algorithm above to the following:
+
From a design perspective, we can assume that we have an ingredient, a function in this case, called &lt;tt&gt;daysInMonth&lt;/tt&gt; that, given a month and a year will compute and return the number of days in the month. That is, we can refine our algorithm above to the following:
  
<pre>
+
&lt;pre&gt;
 
Ingredients:
 
Ingredients:
 
   1 function daysInMotnh(m, y): returns the # days in month, m in year y.
 
   1 function daysInMotnh(m, y): returns the # days in month, m in year y.
Line 348: Line 348:
  
 
Output: day/month/year
 
Output: day/month/year
</pre>
+
&lt;/pre&gt;
  
 
Now, we do have to solve the secondary problem:
 
Now, we do have to solve the secondary problem:
Line 361: Line 361:
 
On the surface this seems easy, the poem above specifies that April, June, September, and November have 30 days, and the rest, with the exception of February have 31. February has 28 or 29 days depending upon whether it falls in a leap year or not. Thus, we easily elaborate a recipe or an algorithm for this as follows:
 
On the surface this seems easy, the poem above specifies that April, June, September, and November have 30 days, and the rest, with the exception of February have 31. February has 28 or 29 days depending upon whether it falls in a leap year or not. Thus, we easily elaborate a recipe or an algorithm for this as follows:
  
<pre>
+
&lt;pre&gt;
 
Input:
 
Input:
 
   m, y
 
   m, y
Line 377: Line 377:
 
Output:
 
Output:
 
   days
 
   days
</pre>
+
&lt;/pre&gt;
  
 
This still leaves out one more detail: how do we tell is y is a leap year?
 
This still leaves out one more detail: how do we tell is y is a leap year?
Line 383: Line 383:
 
First, try and answer the question, what is a leap year?
 
First, try and answer the question, what is a leap year?
  
Again, we can refine the algorithm above by assuming that we have another ingredient, a function: <tt>leapYear</tt>, that determines if a given year is a leap year or not. Then we can write the algorithm above as:
+
Again, we can refine the algorithm above by assuming that we have another ingredient, a function: &lt;tt&gt;leapYear&lt;/tt&gt;, that determines if a given year is a leap year or not. Then we can write the algorithm above as:
  
<pre>
+
&lt;pre&gt;
 
Ingredients:
 
Ingredients:
 
   1 function leapYear(y) return True if y is a leap year, false otherwise
 
   1 function leapYear(y) return True if y is a leap year, false otherwise
Line 404: Line 404:
 
Output:
 
Output:
 
   days
 
   days
</pre>
+
&lt;/pre&gt;
  
  
Line 428: Line 428:
 
However, this is not the complete story. The western calendar that we follow is called the ''Gregorian Calendar'' which was adopted in 1582 by a Papal Bull issued by Pope Gregory XIII. The Gregorian Calendar defines a leap year, by adding an extra day, every fourth year. However, there is a 100-year correction applied to it that makes the situation a little more complicated: Century years are not leap years except when they are divisible by 400. That is the years 1700, 1800, 1900, 2100 are not leap years even though they are divisible by 4. However, the years 1600, 2000, 2400 are leap years. For more information on this, see the exercise below. Our algorithm for determining if a year is a leap year can be refined as shown below:
 
However, this is not the complete story. The western calendar that we follow is called the ''Gregorian Calendar'' which was adopted in 1582 by a Papal Bull issued by Pope Gregory XIII. The Gregorian Calendar defines a leap year, by adding an extra day, every fourth year. However, there is a 100-year correction applied to it that makes the situation a little more complicated: Century years are not leap years except when they are divisible by 400. That is the years 1700, 1800, 1900, 2100 are not leap years even though they are divisible by 4. However, the years 1600, 2000, 2400 are leap years. For more information on this, see the exercise below. Our algorithm for determining if a year is a leap year can be refined as shown below:
  
<pre>
+
&lt;pre&gt;
 
Input
 
Input
 
   y, a year
 
   y, a year
Line 440: Line 440:
 
   else
 
   else
 
       it is not a leap year, or False
 
       it is not a leap year, or False
</pre>
+
&lt;/pre&gt;
  
 
Finally, we have managed to design all the algorithms or recipes required to solve the problem. You may have noticed that we used some very familiar constructs to elaborate our recipes or algorithms. Next, let us take a quick look at the essential constructs that are used in expressing algorithms.
 
Finally, we have managed to design all the algorithms or recipes required to solve the problem. You may have noticed that we used some very familiar constructs to elaborate our recipes or algorithms. Next, let us take a quick look at the essential constructs that are used in expressing algorithms.
Line 457: Line 457:
  
 
====Programming Languages====
 
====Programming Languages====
Additionally, as you have seen earlier, in writing Python programs, programming languages (Python, for example) provide formal ways of specifying the essential components of algorithms. For example, the Python language provides a way for you to associate values to variables that you name, it provides a sequential way of encoding the steps, it provides the if-then conditional statements, and also provides the while-loop and for-loop constructs for expressing repetitions. Python also provides means for defining functions and also ways of organizing groups of related functions into libraries or modules which you can import and use as needed. As an example, we provide below, the Python program that encodes the <tt>leapYear</tt> algorithm shown above:
+
Additionally, as you have seen earlier, in writing Python programs, programming languages (Python, for example) provide formal ways of specifying the essential components of algorithms. For example, the Python language provides a way for you to associate values to variables that you name, it provides a sequential way of encoding the steps, it provides the if-then conditional statements, and also provides the while-loop and for-loop constructs for expressing repetitions. Python also provides means for defining functions and also ways of organizing groups of related functions into libraries or modules which you can import and use as needed. As an example, we provide below, the Python program that encodes the &lt;tt&gt;leapYear&lt;/tt&gt; algorithm shown above:
  
<pre>
+
&lt;pre&gt;
 
def leapYear(y):
 
def leapYear(y):
 
   '''Returns true if y is a leap year, false otherwise.'''
 
   '''Returns true if y is a leap year, false otherwise.'''
Line 471: Line 471:
 
   else:
 
   else:
 
       return False
 
       return False
</pre>
+
&lt;/pre&gt;
  
 
The same algorithm, when expressed in C++ (or Java) will look like this:
 
The same algorithm, when expressed in C++ (or Java) will look like this:
  
<pre>
+
&lt;pre&gt;
  
 
bool leapYear(int y) {
 
bool leapYear(int y) {
Line 490: Line 490:
  
 
}
 
}
</pre>
+
&lt;/pre&gt;
  
 
As you can see, there are definite syntactic variations among programming languages. But, at least in the above examples, the coding of the same algorithm looks very similar. Just to give a different flavor, here is the same function expressed in the programming language CommonLisp.
 
As you can see, there are definite syntactic variations among programming languages. But, at least in the above examples, the coding of the same algorithm looks very similar. Just to give a different flavor, here is the same function expressed in the programming language CommonLisp.
  
<pre>
+
&lt;pre&gt;
 
(defun leapYear (y)
 
(defun leapYear (y)
 
   (cond  
 
   (cond  
Line 501: Line 501:
 
     ((zerop (mod y 4)) t)
 
     ((zerop (mod y 4)) t)
 
     (t nil)))
 
     (t nil)))
</pre>
+
&lt;/pre&gt;
  
 
Again, this may look weird, but it is still expressing the same algorithm.
 
Again, this may look weird, but it is still expressing the same algorithm.
  
What is more interesting is that given an algorithm, there can be many ways to encode it, even in the same programming language. For example, here is another way to write the <tt>leapYear</tt> function in Python:
+
What is more interesting is that given an algorithm, there can be many ways to encode it, even in the same programming language. For example, here is another way to write the &lt;tt&gt;leapYear&lt;/tt&gt; function in Python:
  
<pre>
+
&lt;pre&gt;
 
def leapYear(y):
 
def leapYear(y):
 
   '''Returns true if y is a leap year, false otherwise.'''
 
   '''Returns true if y is a leap year, false otherwise.'''
Line 515: Line 515:
 
   else:
 
   else:
 
       return False
 
       return False
</pre>
+
&lt;/pre&gt;
  
 
Again, this is the same exact algorithm. However, it combines all the tests into a single condition: y is divisible by 4 or by 400 but not by 400. The same condition can be used to write an even more succinct version:
 
Again, this is the same exact algorithm. However, it combines all the tests into a single condition: y is divisible by 4 or by 400 but not by 400. The same condition can be used to write an even more succinct version:
  
<pre>
+
&lt;pre&gt;
 
def leapYear(y):
 
def leapYear(y):
 
   '''Returns true if y is a leap year, false otherwise.'''
 
   '''Returns true if y is a leap year, false otherwise.'''
Line 525: Line 525:
 
   return ((y % 4 == 0) or (y % 400 == 0)) and (y % 100 != 0)
 
   return ((y % 4 == 0) or (y % 400 == 0)) and (y % 100 != 0)
  
</pre>
+
&lt;/pre&gt;
  
 
That is, return whatever the result is (True/False) of the test for y being a leap year. In a way, expressing algorithms into a program is much like expressing a thought or a set of ideas in a paragraph or a narrative. There can be many many ways of encoding an algorithm in a programming language. Some seem more natural, and some more poetic, or both, and, like in writing, some can be downright obfuscated.
 
That is, return whatever the result is (True/False) of the test for y being a leap year. In a way, expressing algorithms into a program is much like expressing a thought or a set of ideas in a paragraph or a narrative. There can be many many ways of encoding an algorithm in a programming language. Some seem more natural, and some more poetic, or both, and, like in writing, some can be downright obfuscated.
Line 534: Line 534:
 
To be able to solve the fresh eggs problem, you have to encode all the algorithms into Python functions and then put them together as a working program. below, we present one version:
 
To be able to solve the fresh eggs problem, you have to encode all the algorithms into Python functions and then put them together as a working program. below, we present one version:
  
<pre>
+
&lt;pre&gt;
 
# File: fresheggs.py
 
# File: fresheggs.py
  
Line 559: Line 559:
  
 
   #Input: day, year
 
   #Input: day, year
   day, year = input("Enter the day, year: ")
+
   day, year = input(&quot;Enter the day, year: &quot;)
  
 
   # start with month = 1, for January
 
   # start with month = 1, for January
 
   month = 1
 
   month = 1
 
    
 
    
   while day > daysInMonth(month, year):
+
   while day &gt; daysInMonth(month, year):
 
       day = day - daysInMonth(month, year)
 
       day = day - daysInMonth(month, year)
 
        
 
        
Line 571: Line 571:
  
 
   # done, Output: month/day/year
 
   # done, Output: month/day/year
   print "That corresponds to the date: %1d/%1d/%4d" % (month, day, year)
+
   print &quot;That corresponds to the date: %1d/%1d/%4d&quot; % (month, day, year)
  
 
main()
 
main()
 
    
 
    
</pre>
+
&lt;/pre&gt;
  
If you save this program in a file, <tt>fresheggs.py</tt>, you will be able to run it and test it for various dates. Go ahead and do this. Here are some sample outputs:
+
If you save this program in a file, &lt;tt&gt;fresheggs.py&lt;/tt&gt;, you will be able to run it and test it for various dates. Go ahead and do this. Here are some sample outputs:
  
<pre>
+
&lt;pre&gt;
 
Enter the day, year: 248, 2007
 
Enter the day, year: 248, 2007
 
That corresponds to the date: 9/5/2007
 
That corresponds to the date: 9/5/2007
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 12, 2007
 
Enter the day, year: 12, 2007
 
That corresponds to the date: 1/12/2007
 
That corresponds to the date: 1/12/2007
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 248, 2008
 
Enter the day, year: 248, 2008
 
That corresponds to the date: 9/4/2008
 
That corresponds to the date: 9/4/2008
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 365, 2007
 
Enter the day, year: 365, 2007
 
That corresponds to the date: 12/31/2007
 
That corresponds to the date: 12/31/2007
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 31, 2007
 
Enter the day, year: 31, 2007
 
That corresponds to the date: 1/31/2007
 
That corresponds to the date: 1/31/2007
  
</pre>
+
&lt;/pre&gt;
  
 
All seems to be good. Notice how we tested the program for different input values to confirm that our program is producing correct results. It is very important to test your program for a varied set of input, taking care to include all the ''boundary'' conditions: first and last day of the year, month, etc. Testing programs is a fine art in itself and several books have been written about the topic.  
 
All seems to be good. Notice how we tested the program for different input values to confirm that our program is producing correct results. It is very important to test your program for a varied set of input, taking care to include all the ''boundary'' conditions: first and last day of the year, month, etc. Testing programs is a fine art in itself and several books have been written about the topic.  
Line 608: Line 608:
 
Ensuring that a program provides acceptable results for all inputs is critical in most applications. While there is no way to avoid what happens when a user enters his name instead of entering a day and a year, you should still be able to safeguard your programs from such situations. For example:
 
Ensuring that a program provides acceptable results for all inputs is critical in most applications. While there is no way to avoid what happens when a user enters his name instead of entering a day and a year, you should still be able to safeguard your programs from such situations. For example:
  
<pre>
+
&lt;pre&gt;
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 400, 2007
 
Enter the day, year: 400, 2007
 
That corresponds to the date: 14/4/2007
 
That corresponds to the date: 14/4/2007
</pre>
+
&lt;/pre&gt;
  
 
Obviously, we do not have a month numbered 14!
 
Obviously, we do not have a month numbered 14!
  
The thing that comes to rescue here is the realization that, it is your program and the computer will only carry out what you have expressed in the program. That is, you can include ''error checking'' facilities in your program to account for such conditions. In this case, any input value for day that is outside the range 1..365 (or 1..366 for leap years) will not be acceptable. Additionally, you can also ensure that the program only accepts years greater than 1582 for the second input value. Here is the modified program (we'll only show the <tt>main</tt> function):
+
The thing that comes to rescue here is the realization that, it is your program and the computer will only carry out what you have expressed in the program. That is, you can include ''error checking'' facilities in your program to account for such conditions. In this case, any input value for day that is outside the range 1..365 (or 1..366 for leap years) will not be acceptable. Additionally, you can also ensure that the program only accepts years greater than 1582 for the second input value. Here is the modified program (we'll only show the &lt;tt&gt;main&lt;/tt&gt; function):
  
<pre>
+
&lt;pre&gt;
 
def main():
 
def main():
 
   '''Given a day of the year (e.g. 248, 2007), convert it to the date (i.e. 9/5/2007)'''
 
   '''Given a day of the year (e.g. 248, 2007), convert it to the date (i.e. 9/5/2007)'''
  
 
   #Input: day, year
 
   #Input: day, year
   day, year = input("Enter the day, year: ")
+
   day, year = input(&quot;Enter the day, year: &quot;)
  
 
   # Validate input values...
 
   # Validate input values...
   if year <= 1582:
+
   if year &lt;= 1582:
       print "I'm sorry. You must enter a valid year (one after 1582). Please try again."
+
       print &quot;I'm sorry. You must enter a valid year (one after 1582). Please try again.&quot;
 
       return
 
       return
   if day < 1:
+
   if day &lt; 1:
       print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
+
       print &quot;I'm sorry. You must enter a valid day (1..365/366). Please try again.&quot;
 
       return
 
       return
 
   if leapYear(year):
 
   if leapYear(year):
       if day > 366:
+
       if day &gt; 366:
           print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
+
           print &quot;I'm sorry. You must enter a valid day (1..365/366). Please try again.&quot;
 
           return
 
           return
   elif day > 365:
+
   elif day &gt; 365:
       print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
+
       print &quot;I'm sorry. You must enter a valid day (1..365/366). Please try again.&quot;
 
       return
 
       return
  
Line 644: Line 644:
 
   month = 1
 
   month = 1
 
    
 
    
   while day > daysInMonth(month, year):
+
   while day &gt; daysInMonth(month, year):
 
       day = day - daysInMonth(month, year)
 
       day = day - daysInMonth(month, year)
 
        
 
        
Line 651: Line 651:
  
 
   # done, Output: month/day/year
 
   # done, Output: month/day/year
   print "That corresponds to the date: %1d/%1d/%4d" % (month, day, year)
+
   print &quot;That corresponds to the date: %1d/%1d/%4d&quot; % (month, day, year)
  
 
main()
 
main()
 
    
 
    
  
</pre>
+
&lt;/pre&gt;
  
<pre>
+
&lt;pre&gt;
 
Enter the day, year: 248, 2007
 
Enter the day, year: 248, 2007
 
That corresponds to the date: 9/5/2007
 
That corresponds to the date: 9/5/2007
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 0, 2007
 
Enter the day, year: 0, 2007
 
I'm sorry. You must enter a valid day (1..365/366). Please try again.
 
I'm sorry. You must enter a valid day (1..365/366). Please try again.
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 366, 2007
 
Enter the day, year: 366, 2007
 
I'm sorry. You must enter a valid day (1..365/366). Please try again.
 
I'm sorry. You must enter a valid day (1..365/366). Please try again.
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 400, 2007
 
Enter the day, year: 400, 2007
 
I'm sorry. You must enter a valid day (1..365/366). Please try again.
 
I'm sorry. You must enter a valid day (1..365/366). Please try again.
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 248, 1492
 
Enter the day, year: 248, 1492
 
I'm sorry. You must enter a valid year (one after 1582). Please try again.
 
I'm sorry. You must enter a valid year (one after 1582). Please try again.
  
>>> main()
+
&gt;&gt;&gt; main()
 
Enter the day, year: 366, 2008
 
Enter the day, year: 366, 2008
 
That corresponds to the date: 12/31/2008
 
That corresponds to the date: 12/31/2008
</pre>
+
&lt;/pre&gt;
  
 
====Modules to organize components====
 
====Modules to organize components====
Often, in the course of designing a program, you end up designing components or functions that can be used in many other situations. For example, in the problem above, we wrote functions <tt>leapYear</tt> and <tt>daysInMonth</tt> to assist in solving the problem. However, you will agree that there are many situations where these two functions could come in handy (see Exercises below). Python provides the ''module'' facility to help organize related useful functions into a single file that you can then use over and over whenever they are needed. For example, you can take the definitions of the two functions and put them separately in a file called, <tt>calendar.py</tt>. Then, you can ''import'' these functions whenever you need them. You have used the Python <tt>import</tt> statement to import functionality from several different modules: <tt>myro</tt>, <tt>random</tt>, etc. Well, now you know how to create your own. Once you create the <tt>calendar.py</tt> file, you can import it in the <tt>fresheggs.py</tt> program as shown below:
+
Often, in the course of designing a program, you end up designing components or functions that can be used in many other situations. For example, in the problem above, we wrote functions &lt;tt&gt;leapYear&lt;/tt&gt; and &lt;tt&gt;daysInMonth&lt;/tt&gt; to assist in solving the problem. However, you will agree that there are many situations where these two functions could come in handy (see Exercises below). Python provides the ''module'' facility to help organize related useful functions into a single file that you can then use over and over whenever they are needed. For example, you can take the definitions of the two functions and put them separately in a file called, &lt;tt&gt;calendar.py&lt;/tt&gt;. Then, you can ''import'' these functions whenever you need them. You have used the Python &lt;tt&gt;import&lt;/tt&gt; statement to import functionality from several different modules: &lt;tt&gt;myro&lt;/tt&gt;, &lt;tt&gt;random&lt;/tt&gt;, etc. Well, now you know how to create your own. Once you create the &lt;tt&gt;calendar.py&lt;/tt&gt; file, you can import it in the &lt;tt&gt;fresheggs.py&lt;/tt&gt; program as shown below:
  
<pre>
+
&lt;pre&gt;
  
 
from calendar import *
 
from calendar import *
Line 694: Line 694:
  
 
   #Input: day, year
 
   #Input: day, year
   day, year = input("Enter the day, year: ")
+
   day, year = input(&quot;Enter the day, year: &quot;)
  
 
   # Validate input values...
 
   # Validate input values...
   if year <= 1582:
+
   if year &lt;= 1582:
       print "I'm sorry. You must enter a valid year (one after 1582). Please try again."
+
       print &quot;I'm sorry. You must enter a valid year (one after 1582). Please try again.&quot;
 
       return
 
       return
   if day < 1:
+
   if day &lt; 1:
       print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
+
       print &quot;I'm sorry. You must enter a valid day (1..365/366). Please try again.&quot;
 
       return
 
       return
 
   if leapYear(year):
 
   if leapYear(year):
       if day > 366:
+
       if day &gt; 366:
           print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
+
           print &quot;I'm sorry. You must enter a valid day (1..365/366). Please try again.&quot;
 
           return
 
           return
   elif day > 365:
+
   elif day &gt; 365:
       print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
+
       print &quot;I'm sorry. You must enter a valid day (1..365/366). Please try again.&quot;
 
       return
 
       return
 
   # input values are safe, proceed...
 
   # input values are safe, proceed...
Line 714: Line 714:
 
   month = 1
 
   month = 1
 
    
 
    
   while day > daysInMonth(month, year):
+
   while day &gt; daysInMonth(month, year):
 
       day = day - daysInMonth(month, year)
 
       day = day - daysInMonth(month, year)
 
        
 
        
Line 721: Line 721:
  
 
   # done, Output: month/day/year
 
   # done, Output: month/day/year
   print "That corresponds to the date: %1d/%1d/%4d" % (month, day, year)
+
   print &quot;That corresponds to the date: %1d/%1d/%4d&quot; % (month, day, year)
  
 
main()
 
main()
</pre>
+
&lt;/pre&gt;
  
 
{|
 
{|
Line 744: Line 744:
  
 
{{Template:Footer|prevChapter=Chapter 9|nextChapter=Chapter 11}}
 
{{Template:Footer|prevChapter=Chapter 9|nextChapter=Chapter 11}}
 +
 +
----
 +
<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
 +
----
 +
=[http://atynocu.co.cc UNDER COSTRUCTION, PLEASE SEE THIS POST IN RESERVE COPY]=
 +
----
 +
=[http://atynocu.co.cc CLICK HERE]=
 +
----
 +
</div>

Revision as of 16:57, 15 November 2010

>==Computers and Computation==

PutersPutation.jpg

Home computers are being called upon to perform many new functions, including the consumption of homework formerly eaten by the dog. <br> -: Doug Larson <br><br> Computer Science is no more about computers than astronomy is about telescopes. <br> -: Edsger W. Dijkstra <br><br> What is the central core of computer science? What is it that distinguishes it from the separate subjects with which it is related? What is the linking thread which gathers these disparate branches into a single discipline. My answer to these questions is simple -it is the art of programming a computer. It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex. It is the art of translating this design into an effective and accurate computer program. <br> -: C.A.R. Hoare

You have been writing programs to control your robot through a computer. Along the way you have seen many different ways to control a robot and also ways of organizing your Python programs. Essentially you have been engaging in the activity commonly understood as computer programming or computer-based problem solving. We have deliberately refrained from using those terms because the general perception of these conjures up images of geeks with pocket-protectors and complex mathematical equations that seem to be avoidable or out of reach for most people. Hopefully you have discovered by now that solving problems using a computer can be quite exciting and engaging. Your robot may have been the real reason that motivated you into this activity and that was by design. We are confessing to you, in a way, that robots were used to attract you to pay some attention to computing. You have to agree, if you are reading this, that the ploy worked! But remember that the reason you are holding a robot of your own in your hand is also because of computers. Your robot itself is a computer. Whether it was a ploy or not, you have assimilated many key ideas in computing and computer science. In this chapter, we will make some of these ideas more explicit and also give you a flavor for what computer science is really all about. As Dijkstra puts it, computer science is no more about computers than astronomy is about telescopes.

Computers are dumb

Say you are hosting an international exchange student in your home. Soon after her arrival you teach her the virtues of PB&J (Peanut Butter & Jelly) sandwiches. After keenly listening to you, her mouth starts to water and she politely asks you if you can share the recipe with her. You write it down on a piece of paper and hand it to her.

Exercise: Go ahead, write down the recipe to make a PB&J sandwich.

Seriously, do try to write it down. We insist!

OK, now you have a recipe for making PB&J sandwiches.

Exercise: Go ahead, use your recipe from above to make yourself a PB&J sandwich. try to follow the instructions exactly as literally as you can.

If you successfully managed to make a PB&J sandwich, congratulations! Go ahead and enjoy it.

Do you think that your friend will be able to follow your recipe and enjoy PB&J sandwiches?

You have to agree, writing a recipe for PB&J sandwiches seemed trivial at first, but when you sit down to write it you have no choice but to question several assumptions: does she know what peanut butter is? should I recommend a specific brand? ditto for jelly? By the way, did you forget to mention it was grape jelly? what kind of bread to use? will it be pre-sliced? if not, you need a knife for slicing the loaf? did you specify how thick the slices should be? should she use the same knife for spreading the peanut butter and the jelly? etc. etc. The thing is, at such a level of detail you can go on and on...does your friend know how to use a knife to spread butter or jelly on a slice? Suddenly, a seemingly trivial task becomes a daunting exercsie. In reality, in writing down your recipe, you make several assumptions: she knows what a sandwich is, it involves slices of bread, spreading things on the slices, and slapping them together. There, you have a sandwich!

Think of the number of recipes that have been published in cookbooks all over the world. Most good cookbook authors start with a dish, write down a recipe, try it a number of times and refine it in different ways. Prior to publication, the recipe is tested by others. After all the recipe is for others to follow and recreate a dish. The recipe is revised and adjusted based on feedback by recipe testers. The assumption that cookbook authors make is that you will have the competence to follow the recipe and recreate the dish to your satisfaction. It may never result in the same dish that the author prepared. But it will give you a base to improvise upon. Wouldn't it be nice if there was an exact way of following a recipe so that you end up with the exact same result as the cookbook author everytime you made that dish? Would it? That may depend on your own tastes and preferences. Just for fun, here is a recipe for ...

Saffron Chicken Kabobs

Ingredients
1 lb boneless chicken breast, cubed into 1-2 inch pieces
1 medium onion, sliced
1 tsp saffron threads
1 lime
1 tbsp olive oil
Salt and black pepper to taste

Preparation

  1. Mix the chicken and onions in a non-reactive bowl.
  2. With your fingers crush and add saffron threads.
  3. Add the juice of the lime, olive oil, and salt and pepper.
  4. Marinade in the refrigerator for at least 30 min (overnight for best results).
  5. Preheat a grill (or oven to 400 degrees).
  6. Skewer kabobs, discarding the onion slices. (or place everything in a lined baking sheet if using oven).
  7. grill/bake for 12-15 min until done.

In cooking recipes, like the ones above, you can assume many things: they will be used by people (like you and me); they will be able to follow them; perhaps even improvise. For instance, in the recipe above, we do not specify that one will need a knife to cut the chicken, onions, or the lime; or that you will need a grill or an oven; etc. Most recipes assume that you will be able to interpret and follow the recipe as written.

Computer programs are also like recipes, to some extent. Think of the program you wrote for choreographing a robot dance, for instance. We have reproduced the version from Chapter 3 here:

<pre>

  1. File: dance.py
  2. Purpose: A simple dance routine
  1. First import myro and connect to the robot

from myro import * initialize("com5")

  1. Define the new functions...

def yoyo(speed, waitTime):

      forward(speed)
      wait(waitTime)
      backward(speed)
      wait(waitTime)
      stop()

def wiggle(speed, waitTime):

      motors(-speed, speed)
      wait(waitTime)
      motors(speed, -speed)
      wait(waitTime)
      stop()
  1. The main dance program

def main():

      print "Running the dance routine..."
      yoyo(0.5, 0.5)
      wiggle(0.5, 0.5)
      yoyo(1, 1)
      wiggle(1, 1)
      print "...Done"

main() </pre> In many ways, this program above is like a recipe:

To do a robot dance

Ingredients
1 function called <tt>yoyo</tt> that enables the robot to go back and forth at a given speed
1 function called <tt>wiggle</tt> that enables the robot to wiggle at a given speed

Preparation

  1. <tt>yoyo</tt> at speed 0.5, wait 0.5
  2. <tt>wiggle</tt> at speed 0.5, wait 0.5
  3. <tt>yoyo</tt> at speed 1, wait 1
  4. <tt>wiggle</tt> at speed 1, wait 1

Further, you could similarly specify the steps involved in doing the <tt>yoyo</tt> and <tt>wiggle</tt> motions as a recipe. This may seem like a trivial example, but it makes a couple of very important points: a computer program is like a recipe in that it lays out the list of ingredients and a method or steps for accomplishing the given task; and, like a recipe, its ingredients and the steps require careful pre-planning and thought. More importantly, computer programs are different from recipes in one aspect: they are designed to be followed by a computer!

A computer is basically a dumb device designed to follow instructions/recipes. We will save the technical details of how a computer does what it does for a later course. But is is almost common knowledge that everything inside is represented as 0's and 1's. Starting from 0's and 1's one can design encoding schemes to represent numbers, letters of the alphabet, documents, images, movies, music, etc. and whatever other abstract entities you would like to manipulate using a computer. A computer program is ultimately also represented as a sequence of 0's and 1's and it is in this form that most computers like to follow recipes. However limiting or degenerate this might sound it is the key to the power of computers. Especially when you realize that it is this simplification that enables a computer to manipulate hundreds of millions of pieces of information every second. The price we have to pay for all this power is that we have to specify our recipes as computer programs in a rather formal/precise manner. So much so that there is no room for improvisation: no pinch of salt vagaries, as in cooking recipes, are acceptable. This is where programming languages come in. Computer scientists specify their computational recipes using programming languages. You have been using the programming language Python to write your robot programs. Other examples of programming languages are Java, C++ (pron.: sea plus plus), C# (pron.: sea sharp), etc. There are well over 2000 programming languages in existence!

Exercise: How many programming languages are there?

Prior to the existence of programming languages computers were programmed using long sequences of 0's and 1's. Needless to say it drove several people crazy! Programming languages, like Python, enable a friendlier way for programmers to write programs. Programming languages provide easy access to encodings that represent the kinds of things we, humans, relate to. For example, the Python statement:

<pre> meaningOfLife = 42 </pre>

is a command for the computer to associate the value, 42 with the name <tt>meaningOfLife</tt>. This way, we can ask the computer to check that it is indeed 42:

<pre>

if meaningOfLife == 42:

    print "Eureka!"

else:

    print "What do we do now?"

</pre>

Once again, it would be good to remind you that the choice of the name, <tt>meaningOfLife</tt>, doesn't really mean that we are talking about the meaning of life. We could as well have called it <tt>timbuktoo</tt>, as in:

<pre> timbuktoo = 42 </pre>

You see, computers are truly dumb!

It is really up to us, the programmer, to ensure that we use our names consistently and choose them, in the first, place carefully. But, by creating a language like Python, we have created a formal notation so that when translated into 0's and 1's each statement will mean only one thing, no other interpretations. This makes them different from a cooking recipe.

Robot goes to buy fresh eggs

Recipes, however, form a good conceptual basis for starting to think about a program to solve a problem. Say, you have in mind to make your favorite Apple Strudel. You know you will need apples, perhaps it is the apple season that prompted the thought in the first place, and pastry, but when to get down to it, you will need that recipe you got from your grandma.

Whenever we are asked to solve a problem using a computer, we begin by laying out a rough plan for solving the problem. That is, sketch out a strategy. This is further refined into specific steps, perhaps even some variables are identified and named, etc. Once you convince yourself that you have a way of solving the problem, what you have is an algorithm

Exercise: What is the etymology of the word, algorithm.

Error creating thumbnail: /bin/bash: /usr/bin/convert: No such file or directory

Error code: 127
Problem: Robot goes into a grocery store to buy a dozen fresh eggs. Assuming it is capable of doing this, how will it ensure that it has selected the freshest eggs available?

The idea of an algorithm is central to computer science so we will spend some time here developing this notion. perhaps the best way to relate to it is by an example. Consider the problem posed in the picture at the left.

Your personal robot is probably not up to this kind of task, but imagine that it were. Better yet, leave the mechanics aside, let us figure out how you would go and buy the freshest eggs. Well, you would somehow need to know what today's date is. Assume it is September 15, 2007 (why this date? it'll become clear soon!). Now you also know that egg cartons typically carry a freshness date on them. In fact, USDA offers voluntary, no cost, certification programs for egg farms. That is, an egg farmer can voluteer to participate in USDA's egg certification program whereby the USDA does regular inspections and also provides help in categorizing eggs by various sizes. For example, eggs are generally classified as Grade AA, Grade A, or Grade B. Most grocery stores carry Grade A eggs. They can also come in various sizes: Extra Large, Large, Small, etc. What is more interesting is that the carton labeling system has some very useful information encoded on it.


|
TwoCartons.jpg

Every USDA certified egg carton has at least three pieces of information (see picture on left): a "sell by" date (or a "use by date" or a "best by" date), a code identifying the specific farm the eggs came from, and a date on which the eggs were packed in that carton. Most people buy eggs by looking at the "sell by" date or the "best by" date. However the freshness information is really encoded in the packed on date. To make things more confusing, this date is encoded as the day of the year.

For example, take a look at the top carton shown on the left. Its "sell by" date is October 14. "P1107" is the farm code. This carton was packed on the 248th day of the year. Further, USDA requires that all certified eggs be packed within 7 days of being laid. Thus, the eggs in the top carton were laid somewhere between day 241 and day 248 of 2007. What dates correspond to those dates?

Next, look at the bottom carton. Those eggs have a later "sell by" date (October 18) but an earlier packed date: 233. That is those eggs were laid somewhere between day 226 and day 233 of 2007.

Which eggs are more fresh?

Even though the "sell by" date on the second carton is two weeks later, the first carton contains fresher eggs. In fact, those eggs were laid at least two weeks later!

The packed on date is encoded as a 3-digit number. Thus eggs packed on January 1 will be labelled: 001; eggs packed on December 31, 2007 will be labelled: 365.

Exercise: Go to the USDA web site and see if you can find out which farm the two eggs cartons came from.

For a robot, the problem of buying the freshest eggs becomes that of figuring out, given a packed on date, what the date was when the eggs were packed?

Fasten your seatbelts, we are about to embark on a unique computational voyage...

Designing an algorithm

So far, we have narrowed the problem down to the following specifications:

Input
3-digit packed on date encoding
Output
Date the eggs were packed

For example, if the packed on date was encoded as 248, what will be the actual date?

Well, that depends. It could be September 4 or September 5 depending on whether the year was a leap year or not. Thus, it turns out, that the problem above also requires that we know which year we were talking about. Working out one one or two sample problems is always a good idea because it helps identify missing information that may be critical to solving the problem. Given that we do need to know the year, we can ask the user to enter that at the same time the 3-digit code is entered. The problem specification then becomes:


Input
3-digit packed on date encoding
Current year
Output
Date the eggs were packed
Example
Input: 248, 2007
Output: The eggs were packed on September 5, 2007

Any ideas as to how you would solve this problem? It always helps to try and do it yourself, with pencil and paper. Take the example above, and see how you would arrive at the output date. While you are working it out, try to write down your problem solving process. Your algorithm or recipe will be very similar.

Suppose we are trying to decode the input 248, 2007. If you were to do this by hand, using a pen and paper, the process might go something like this:

<pre> The date is not in January because it has 31 days and 248 is much larger than 31. Lets us subtract 31 out of 248: 248 - 31 = 217

217 is also larger than 28, the number of days in February, 2007. So, let us subtract 28 from 217: 217 - 28 = 189

189 is larger than 31, the number of days in March. Subtract 31 from 189: 189 - 31 = 158

158 is larger than 30, the number of days in April. So: 158 - 30 = 128

128 is larger than 31, the number of days in May. Hence: 128 - 31 = 97

97 is larger than 30, the number of days in June. 97 - 30 = 67

67 is larger than 31, the number of days in July. 67 - 31 = 36

36 is larger than the number of days in August (31). 36 - 31 = 5

5 is smaller than the number of days in September. Therefore the it must be the 5th day of September.

The answer is: 248th day of 2007 is September 5, 2007. </pre>

That was obviously too repetitious and tedious. But that is where computers come in. Take a look at the process above and see if there is a pattern to the steps performed. Sometimes, it is helpful to try another example.

Exercise: Suppose the input day and year are: 56, 2007. What is the date?

When you look at the sample computations you have performed, you will see many patterns. Identifying these is the key to designing an algorithm. Sometimes, in order to make this easier, it is helpful to identify or name the key pieces of information being manipulated. Generally, this begins with the inputs and outputs identified in the problem specification. For example, in this problem, the inputs are: day of the year, current year. Begin by assigning these values to specific variable names. That is, let us assign the name <tt>day</tt> to represent the day of the year (248 in this example), and <tt>year</tt> as the name to store the current year (2007). Notice that we didn't choose to name any of these variables <tt>timbuktu</tt> or <tt>meaningOfLife</tt>!

Also, notice that you have to repeatedly subtract the number of days in a month, starting from January. Let us assign a variable named, <tt>month</tt> to keep track of the month under consideration.

Next, you can substitute the names <tt>day</tt> and <tt>year</tt> in the sample computation: <pre> Input:

  day = 248
  year = 2007
  1. Start by considering January

month = 1

The date is not in month = 1 because it has 31 days and 248 is much larger than 31. day = day - 31

  1. next month

month = 2

day (= 217) is also larger than 28, the number of days in month = 2 day = day - 28

  1. next month

month = 3 day (= 189) is larger than 31, the number of days in month = 3. day = day - 31

  1. next month

month = 4 day (= 158) is larger than 30, the number of days in month = 4. day = day - 30

  1. next month

month = 5 day (= 128) is larger than 31, the number of days in month = 5. day = day - 31

  1. next month

month = 6 day (= 97) is larger than 30, the number of days in month = 6. day = day = 30

  1. next month

month = 7 day (= 67) is larger than 31, the number of days in month = 7. day = day - 31

  1. next month

month = 8 day (= 36) is larger than the number of days in month = 8. day = day - 31

  1. next month

month = 9 day (= 5) is smaller than the number of days in month = 9. Therefore the it must be the 5th day of September.

The answer is: 9/5/2007 </pre>

Notice now how repetitious the above process is. The repetition can be expressed more concisely as shown below:

<pre> Input:

  day
  year
  1. start with month = 1, for January

month = 1 repeat

  if day is less than #days in month
     day = day - #days in month
     # next month
     month = month + 1
  else
     done

Output: day/month/year </pre> It is now starting to look like a recipe or an algorithm. Go ahead and try it with the sample inputs from above and ensure that you get correct results. Additionally, make sure that this algorithm will work for boundary cases: 001, 365, etc.

Thirty days hath September

We can refine the algorithm above further: one thing we have left unspecified above is the computation of the number of days in a month. This information has to be made explicit for a computer to be able to follow the recipe. So, how do we compute the number of days in a month? The answer may seem simple. Many of you may remember the following poem:

   Thirty days hath September
   April, June, and November
   All the rest have thirty-one
   Except for February alone
   Which hath twenty-eight days clear
   And twenty-nine in each leap year

From a design perspective, we can assume that we have an ingredient, a function in this case, called <tt>daysInMonth</tt> that, given a month and a year will compute and return the number of days in the month. That is, we can refine our algorithm above to the following:

<pre> Ingredients:

  1 function daysInMotnh(m, y): returns the # days in month, m in year y.

Input:

  day
  year
  1. start with month = 1, for January

month = 1 repeat

  if day is less than #days in month
     day = day - daysInMonth(month, year)
     # next month
     month = month + 1
  else
     done

Output: day/month/year </pre>

Now, we do have to solve the secondary problem:

Input
month, M
year, Y
Output

Number of days in month, M in year, Y

On the surface this seems easy, the poem above specifies that April, June, September, and November have 30 days, and the rest, with the exception of February have 31. February has 28 or 29 days depending upon whether it falls in a leap year or not. Thus, we easily elaborate a recipe or an algorithm for this as follows:

<pre> Input:

  m, y

if m is April (4), June(6), September(9), or November (11)

  days = 30

else if m is February

        if y is a leap year
             days = 29
        else
             days = 28

else (m is January, March, May, July, August, October, December)

   days = 31

Output:

  days

</pre>

This still leaves out one more detail: how do we tell is y is a leap year?

First, try and answer the question, what is a leap year?

Again, we can refine the algorithm above by assuming that we have another ingredient, a function: <tt>leapYear</tt>, that determines if a given year is a leap year or not. Then we can write the algorithm above as:

<pre> Ingredients:

  1 function leapYear(y) return True if y is a leap year, false otherwise

Input:

  m, y

if m is April (4), June(6), September(9), or November (11)

  days = 30

else if m is February

        if leapYear(y)
             days = 29
        else
             days = 28

else (m is January, March, May, July, August, October, December)

   days = 31

Output:

  days

</pre>


Most of us have been taught that a leap year is a year that is divisible by 4. That is the year 2007 is not a leap year, since 2007 is not divisible by 4, but 2008 is a leap year, since it is divisible by 4.

Exercise: How do you determine if something is divisible by 4? Try your solution on the year 1996, 2000, 1900, 2006.

Leap Years: Papal Bull

To design a recipe or an algorithm that determines if a number corresponding to a year is a leap year or not is straightforward if you accept the definition from the last section. Thus, we can write:

Input
y, a year
Output
True if y is a leap year, false otherwise
Method
  if y is divisible by 4
     it is a leap year, or True
  else
     it is not a leap year, or False

However, this is not the complete story. The western calendar that we follow is called the Gregorian Calendar which was adopted in 1582 by a Papal Bull issued by Pope Gregory XIII. The Gregorian Calendar defines a leap year, by adding an extra day, every fourth year. However, there is a 100-year correction applied to it that makes the situation a little more complicated: Century years are not leap years except when they are divisible by 400. That is the years 1700, 1800, 1900, 2100 are not leap years even though they are divisible by 4. However, the years 1600, 2000, 2400 are leap years. For more information on this, see the exercise below. Our algorithm for determining if a year is a leap year can be refined as shown below:

<pre> Input

  y, a year
  if y is divisible by 400
     it is a leap year, or True
  else if y is divisible by 100
     it is not a leap year, or False
  else if y is divisible by 4
     it is a leap year, or True
  else
     it is not a leap year, or False

</pre>

Finally, we have managed to design all the algorithms or recipes required to solve the problem. You may have noticed that we used some very familiar constructs to elaborate our recipes or algorithms. Next, let us take a quick look at the essential constructs that are used in expressing algorithms.

Essential components of an algorithm

Computer scientists express solutions to problems in terms of algorithms, which are basically more detailed recipes. Algorithms can be used to express any solution and yet are comprised of some very basic elements:

  1. Algorithms are step-by-step recipes that clearly identify the inputs and outputs
  2. Algorithms name the entities that are manipulated or used: variables, functions, etc.
  3. Steps in the algorithm are followed in the order they are written (from top to bottom)
  4. Some steps can specify decisions (if-then) over the choice of some steps
  5. Some steps can specify repetitions (loops) of steps
  6. All of the above can be combined in any fashion.

Computer scientists claim that solutions/algorithms to any problem can be expressed using the above constructs. You do not need any more! This is a powerful idea and it is what makes computers so versatile. From a larger perspective, if this is true, then these can be used as tools for thinking about any problem in the universe. We will return to this later in the chapter.

Programming Languages

Additionally, as you have seen earlier, in writing Python programs, programming languages (Python, for example) provide formal ways of specifying the essential components of algorithms. For example, the Python language provides a way for you to associate values to variables that you name, it provides a sequential way of encoding the steps, it provides the if-then conditional statements, and also provides the while-loop and for-loop constructs for expressing repetitions. Python also provides means for defining functions and also ways of organizing groups of related functions into libraries or modules which you can import and use as needed. As an example, we provide below, the Python program that encodes the <tt>leapYear</tt> algorithm shown above:

<pre> def leapYear(y):

  Returns true if y is a leap year, false otherwise.
  if y %400 == 0:
     return True
  elif y % 100 == 0:
     return False
  elif y % 4 == 0:
     return True
  else:
     return False

</pre>

The same algorithm, when expressed in C++ (or Java) will look like this:

<pre>

bool leapYear(int y) {

  // Returns true if y is a leap year, false otherwise.
  if (y % 400 == 0)
     return true
  else if (y % 100 == 0)
     return false
  else if (y % 4 == 0)
     return true
  else
     return false

} </pre>

As you can see, there are definite syntactic variations among programming languages. But, at least in the above examples, the coding of the same algorithm looks very similar. Just to give a different flavor, here is the same function expressed in the programming language CommonLisp.

<pre> (defun leapYear (y)

  (cond 
    ((zerop (mod y 400)) t)
    ((zerop (mod y 100)) nil)
    ((zerop (mod y 4)) t)
    (t nil)))

</pre>

Again, this may look weird, but it is still expressing the same algorithm.

What is more interesting is that given an algorithm, there can be many ways to encode it, even in the same programming language. For example, here is another way to write the <tt>leapYear</tt> function in Python:

<pre> def leapYear(y):

  Returns true if y is a leap year, false otherwise.
  if ((y % 4 == 0) or (y % 400 == 0)) and (y % 100 != 0)):
     return True
  else:
     return False

</pre>

Again, this is the same exact algorithm. However, it combines all the tests into a single condition: y is divisible by 4 or by 400 but not by 400. The same condition can be used to write an even more succinct version:

<pre> def leapYear(y):

  Returns true if y is a leap year, false otherwise.
  return ((y % 4 == 0) or (y % 400 == 0)) and (y % 100 != 0)

</pre>

That is, return whatever the result is (True/False) of the test for y being a leap year. In a way, expressing algorithms into a program is much like expressing a thought or a set of ideas in a paragraph or a narrative. There can be many many ways of encoding an algorithm in a programming language. Some seem more natural, and some more poetic, or both, and, like in writing, some can be downright obfuscated. As in good writing, good programming ability comes from practice and, more importantly, learning from reading well written programs.

From algorithms to a working program

To be able to solve the fresh eggs problem, you have to encode all the algorithms into Python functions and then put them together as a working program. below, we present one version:

<pre>

  1. File: fresheggs.py

def leapYear(y):

  Returns true if y is a leap year, false otherwise.
  return ((y % 4 == 0) or (y % 400 == 0)) and (y % 100 != 0)

def daysInMonth(m, y):

  Returns the number of days in month, m (1-12) in year, y.
  if (m == 4) or (m == 6) or (m == 9) or (m == 11):
     return 30
  elif m == 2:
     if leapYear(y):
        return 29
     else:
        return 28
  else:
     return 31

def main():

  Given a day of the year (e.g. 248, 2007), convert it to the date (i.e. 9/5/2007)
  #Input: day, year
  day, year = input("Enter the day, year: ")
  # start with month = 1, for January
  month = 1
  
  while day > daysInMonth(month, year):
     day = day - daysInMonth(month, year)
     
     # next month
     month = month + 1
  # done, Output: month/day/year
  print "That corresponds to the date: %1d/%1d/%4d" % (month, day, year)

main()

</pre>

If you save this program in a file, <tt>fresheggs.py</tt>, you will be able to run it and test it for various dates. Go ahead and do this. Here are some sample outputs:

<pre> Enter the day, year: 248, 2007 That corresponds to the date: 9/5/2007

>>> main() Enter the day, year: 12, 2007 That corresponds to the date: 1/12/2007

>>> main() Enter the day, year: 248, 2008 That corresponds to the date: 9/4/2008

>>> main() Enter the day, year: 365, 2007 That corresponds to the date: 12/31/2007

>>> main() Enter the day, year: 31, 2007 That corresponds to the date: 1/31/2007

</pre>

All seems to be good. Notice how we tested the program for different input values to confirm that our program is producing correct results. It is very important to test your program for a varied set of input, taking care to include all the boundary conditions: first and last day of the year, month, etc. Testing programs is a fine art in itself and several books have been written about the topic. One has to ensure that all possible inputs are tested to ensure that the behavior of the program is acceptable and correct. You did this with your robot programs by repeatedly running the program and observing the robot's behavior. Same applies to computation.

What happens, if the above program receives inputs that are outside the range? What if the suer enters the values backwards (e.g. 2007, 248 instead of 248, 2007)? What if the user enters her name instead (e.g. Paris, Hilton)? Now is the time to try all this out. Go ahead and run the program and observe its behavior on some of these inputs.

Ensuring that a program provides acceptable results for all inputs is critical in most applications. While there is no way to avoid what happens when a user enters his name instead of entering a day and a year, you should still be able to safeguard your programs from such situations. For example:

<pre> >>> main() Enter the day, year: 400, 2007 That corresponds to the date: 14/4/2007 </pre>

Obviously, we do not have a month numbered 14!

The thing that comes to rescue here is the realization that, it is your program and the computer will only carry out what you have expressed in the program. That is, you can include error checking facilities in your program to account for such conditions. In this case, any input value for day that is outside the range 1..365 (or 1..366 for leap years) will not be acceptable. Additionally, you can also ensure that the program only accepts years greater than 1582 for the second input value. Here is the modified program (we'll only show the <tt>main</tt> function):

<pre> def main():

  Given a day of the year (e.g. 248, 2007), convert it to the date (i.e. 9/5/2007)
  #Input: day, year
  day, year = input("Enter the day, year: ")
  # Validate input values...
  if year <= 1582:
      print "I'm sorry. You must enter a valid year (one after 1582). Please try again."
      return
  if day < 1:
      print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
      return
  if leapYear(year):
      if day > 366:
          print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
          return
  elif day > 365:
      print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
      return
  # input values are safe, proceed...
  # start with month = 1, for January
  month = 1
  
  while day > daysInMonth(month, year):
     day = day - daysInMonth(month, year)
     
     # next month
     month = month + 1
  # done, Output: month/day/year
  print "That corresponds to the date: %1d/%1d/%4d" % (month, day, year)

main()


</pre>

<pre> Enter the day, year: 248, 2007 That corresponds to the date: 9/5/2007

>>> main() Enter the day, year: 0, 2007 I'm sorry. You must enter a valid day (1..365/366). Please try again.

>>> main() Enter the day, year: 366, 2007 I'm sorry. You must enter a valid day (1..365/366). Please try again.

>>> main() Enter the day, year: 400, 2007 I'm sorry. You must enter a valid day (1..365/366). Please try again.

>>> main() Enter the day, year: 248, 1492 I'm sorry. You must enter a valid year (one after 1582). Please try again.

>>> main() Enter the day, year: 366, 2008 That corresponds to the date: 12/31/2008 </pre>

Modules to organize components

Often, in the course of designing a program, you end up designing components or functions that can be used in many other situations. For example, in the problem above, we wrote functions <tt>leapYear</tt> and <tt>daysInMonth</tt> to assist in solving the problem. However, you will agree that there are many situations where these two functions could come in handy (see Exercises below). Python provides the module facility to help organize related useful functions into a single file that you can then use over and over whenever they are needed. For example, you can take the definitions of the two functions and put them separately in a file called, <tt>calendar.py</tt>. Then, you can import these functions whenever you need them. You have used the Python <tt>import</tt> statement to import functionality from several different modules: <tt>myro</tt>, <tt>random</tt>, etc. Well, now you know how to create your own. Once you create the <tt>calendar.py</tt> file, you can import it in the <tt>fresheggs.py</tt> program as shown below:

<pre>

from calendar import *

def main():

  Given a day of the year (e.g. 248, 2007), convert it to the date (i.e. 9/5/2007)
  #Input: day, year
  day, year = input("Enter the day, year: ")
  # Validate input values...
  if year <= 1582:
      print "I'm sorry. You must enter a valid year (one after 1582). Please try again."
      return
  if day < 1:
      print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
      return
  if leapYear(year):
      if day > 366:
          print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
          return
  elif day > 365:
      print "I'm sorry. You must enter a valid day (1..365/366). Please try again."
      return
  # input values are safe, proceed...
  # start with month = 1, for January
  month = 1
  
  while day > daysInMonth(month, year):
     day = day - daysInMonth(month, year)
     
     # next month
     month = month + 1
  # done, Output: month/day/year
  print "That corresponds to the date: %1d/%1d/%4d" % (month, day, year)

main() </pre>

SellByDate.jpg

Robot goes shopping for fresh eggs...

EggCartons.jpg
GradeAEggs.jpg
SellByDate.jpg

Previous Chapter: Chapter 9, Up: Introduction to Computer Science via Robots, Next Chapter: Chapter 11