lOMoARcPSD|8521469
Lecture notes, lectures 1 - 4
Data Structures and Algorithms (Harvard
University)
, lOMoARcPSD|8521469
CS 124 Course Notes 1
An algorithm is a recipe or a well-defined procedure for performing a calculation, or in general, for transforming
some input into a desired output. Perhaps the most familiar algorithms are those those for adding and multiplying
integers. Here is a multiplication algorithm that is different from the standard algorithm you learned in school:
write the multiplier and multiplicand side by side. Repeat the following operations - divide the first number by 2
(throw out any fractions) and multiply the second by 2, until the first number is 1. This results in two columns of
numbers. Now cross out all rows in which the first entry is even, and add all entries of the second column that
haven’t been crossed out. The result is the product of the two numbers.
75 29 2
37 58 9 x
1001011
18 116 29
9 232 58
4 464 232
2 928 1856
1 1856 2175
2175
Figure 1.1: A different multiplication algorithm.
In this course we will ask a number of basic questions about algorithms:
• Does it halt?
The answer for the algorithm given above is clearly yes, provided we are multiplying positive integers. The
reason is that for any integer greater than 1, when we divide it by 2 and throw out the fractional part, we
always get a smaller integer which is greater than or equal to 1. Hence our first number is eventually
reduced to 1 and the process halts.
• Is it correct?
To see that the algorithm correctly computes the product of the integers, observe that if we write a 0 for
each crossed out row, and 1 for each row that is not crossed out, then reading from bottom to top just
gives us the first number in binary. Therefore, the algorithm is just doing standard multiplication, with the
multiplier written in binary.
• Is it fast?
, lOMoARcPSD|8521469
1-2
It turns out that the above algorithm is about as fast as the standard algorithm you learned in school. Later in
the course, we will study a faster algorithm for multiplying integers.
• How much memory does it use?
The memory used by this algorithm is also about the same as that of standard algorithm.
The history of algorithms for simple arithmetic is quite fascinating. Although we take these algorithms for
granted, their widespread use is surprisingly recent. The key to good algorithms for arithmetic was the positional
number system (such as the decimal system). Roman numerals (I, II, III, IV, V, VI, etc) are just the wrong data
structure for performing arithmetic efficiently. The positional number system was first invented by the Mayan
Indians in Central America about 2000 years ago. They used a base 20 system, and it is unknown whether they
had invented algorithms for performing arithmetic, since the Spanish conquerors destroyed most of the Mayan
books on science and astronomy.
The decimal system that we use today was invented in India in roughly 600 AD. This positional number system,
together with algorithms for performing arithmetic, were transmitted to Persia around 750 AD, when several
impor- tant Indian works were translated into Arabic. Around this time the Persian mathematician Al-Khwarizmi
wrote his Arabic textbook on the subject. The word “algorithm” comes from Al-Khwarizmi’s name. Al-
Khwarizmi’s work was translated into Latin around 1200 AD, and the positional number system was propagated
throughout Europe from 1200 to 1600 AD.
The decimal point was not invented until the 10 th century AD, by a Syrian mathematician al-Uqlidisi from
Damascus. His work was soon forgotten, and five centuries passed before decimal fractions were re-invented by
the Persian mathematician al-Kashi.
With the invention of computers in this century, the field of algorithms has seen explosive growth. There are
a number of major successes in this field:
• Parsing algorithms - these form the basis of the field of programming languages
• Fast Fourier transform - the field of digital signal processing is built upon this algorithm.
• Linear programming - this algorithm is extensively used in resource scheduling.
• Sorting algorithms - until recently, sorting used up the bulk of computer cycles.
• String matching algorithms - these are extensively used in computational biology.
, lOMoARcPSD|8521469
1-3
• Number theoretic algorithms - these algorithms make it possible to implement cryptosystems such as the
RSA public key cryptosystem.
• Compression algorithms - these algorithms allow us to transmit data more efficiently over, for example,
phone lines.
• Geometric algorithms - displaying images quickly on a screen often makes use of sophisticated algorithmic
techniques.
In designing an algorithm, it is often easier and more productive to think of a computer in abstract terms. Of
course, we must carefully choose at what level of abstraction to think. For example, we could think of computer
operations in terms of a high level computer language such as C or Java, or in terms of an assembly language. We
could dip further down, and think of the computer at the level AND and NOT gates.
For more on algorithms generally, you can start with the Wikipedia page: http://en.wikipedia.
org/wiki/Algorithm.
For most algorithm design we undertake in this course, it is generally convenient to work at a fairly high
level. We will usually abstract away even the details of the high level programming language, and write our
algorithms in ”pseudo-code”, without worrying about implementation details. (Unless, of course, we are dealing
with a program- ming assignment!) Sometimes we have to be careful that we do not abstract away essential
features of the problem. To illustrate this, let us consider a simple but enlightening example.
1.1 Computing the nth Fibonacci number
Remember the famous sequence of numbers invented in the 15th century by the Italian mathematician Leonardo
Fibonacci? The sequence is represented as F0, F1, F2 . . ., where F0 = 0, F1 = 1, and for all n ≥ 2, Fn is defined as
Fn−1 + Fn−2. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... The value of F30 is greater
than a
million! It is easy to see that the Fibonacci numbers grow exponentially. As an exercise, try to show that Fn ≥ 2n/2
for sufficiently large n by a simple induction.
The Wikipedia page for Fibonacci numbers is also full of useful information: http://en.wikipedia.
org/wiki/Fibonacci number.
Here is a simple program to compute Fibonacci numbers that slavishly follows the definition.
Lecture notes, lectures 1 - 4
Data Structures and Algorithms (Harvard
University)
, lOMoARcPSD|8521469
CS 124 Course Notes 1
An algorithm is a recipe or a well-defined procedure for performing a calculation, or in general, for transforming
some input into a desired output. Perhaps the most familiar algorithms are those those for adding and multiplying
integers. Here is a multiplication algorithm that is different from the standard algorithm you learned in school:
write the multiplier and multiplicand side by side. Repeat the following operations - divide the first number by 2
(throw out any fractions) and multiply the second by 2, until the first number is 1. This results in two columns of
numbers. Now cross out all rows in which the first entry is even, and add all entries of the second column that
haven’t been crossed out. The result is the product of the two numbers.
75 29 2
37 58 9 x
1001011
18 116 29
9 232 58
4 464 232
2 928 1856
1 1856 2175
2175
Figure 1.1: A different multiplication algorithm.
In this course we will ask a number of basic questions about algorithms:
• Does it halt?
The answer for the algorithm given above is clearly yes, provided we are multiplying positive integers. The
reason is that for any integer greater than 1, when we divide it by 2 and throw out the fractional part, we
always get a smaller integer which is greater than or equal to 1. Hence our first number is eventually
reduced to 1 and the process halts.
• Is it correct?
To see that the algorithm correctly computes the product of the integers, observe that if we write a 0 for
each crossed out row, and 1 for each row that is not crossed out, then reading from bottom to top just
gives us the first number in binary. Therefore, the algorithm is just doing standard multiplication, with the
multiplier written in binary.
• Is it fast?
, lOMoARcPSD|8521469
1-2
It turns out that the above algorithm is about as fast as the standard algorithm you learned in school. Later in
the course, we will study a faster algorithm for multiplying integers.
• How much memory does it use?
The memory used by this algorithm is also about the same as that of standard algorithm.
The history of algorithms for simple arithmetic is quite fascinating. Although we take these algorithms for
granted, their widespread use is surprisingly recent. The key to good algorithms for arithmetic was the positional
number system (such as the decimal system). Roman numerals (I, II, III, IV, V, VI, etc) are just the wrong data
structure for performing arithmetic efficiently. The positional number system was first invented by the Mayan
Indians in Central America about 2000 years ago. They used a base 20 system, and it is unknown whether they
had invented algorithms for performing arithmetic, since the Spanish conquerors destroyed most of the Mayan
books on science and astronomy.
The decimal system that we use today was invented in India in roughly 600 AD. This positional number system,
together with algorithms for performing arithmetic, were transmitted to Persia around 750 AD, when several
impor- tant Indian works were translated into Arabic. Around this time the Persian mathematician Al-Khwarizmi
wrote his Arabic textbook on the subject. The word “algorithm” comes from Al-Khwarizmi’s name. Al-
Khwarizmi’s work was translated into Latin around 1200 AD, and the positional number system was propagated
throughout Europe from 1200 to 1600 AD.
The decimal point was not invented until the 10 th century AD, by a Syrian mathematician al-Uqlidisi from
Damascus. His work was soon forgotten, and five centuries passed before decimal fractions were re-invented by
the Persian mathematician al-Kashi.
With the invention of computers in this century, the field of algorithms has seen explosive growth. There are
a number of major successes in this field:
• Parsing algorithms - these form the basis of the field of programming languages
• Fast Fourier transform - the field of digital signal processing is built upon this algorithm.
• Linear programming - this algorithm is extensively used in resource scheduling.
• Sorting algorithms - until recently, sorting used up the bulk of computer cycles.
• String matching algorithms - these are extensively used in computational biology.
, lOMoARcPSD|8521469
1-3
• Number theoretic algorithms - these algorithms make it possible to implement cryptosystems such as the
RSA public key cryptosystem.
• Compression algorithms - these algorithms allow us to transmit data more efficiently over, for example,
phone lines.
• Geometric algorithms - displaying images quickly on a screen often makes use of sophisticated algorithmic
techniques.
In designing an algorithm, it is often easier and more productive to think of a computer in abstract terms. Of
course, we must carefully choose at what level of abstraction to think. For example, we could think of computer
operations in terms of a high level computer language such as C or Java, or in terms of an assembly language. We
could dip further down, and think of the computer at the level AND and NOT gates.
For more on algorithms generally, you can start with the Wikipedia page: http://en.wikipedia.
org/wiki/Algorithm.
For most algorithm design we undertake in this course, it is generally convenient to work at a fairly high
level. We will usually abstract away even the details of the high level programming language, and write our
algorithms in ”pseudo-code”, without worrying about implementation details. (Unless, of course, we are dealing
with a program- ming assignment!) Sometimes we have to be careful that we do not abstract away essential
features of the problem. To illustrate this, let us consider a simple but enlightening example.
1.1 Computing the nth Fibonacci number
Remember the famous sequence of numbers invented in the 15th century by the Italian mathematician Leonardo
Fibonacci? The sequence is represented as F0, F1, F2 . . ., where F0 = 0, F1 = 1, and for all n ≥ 2, Fn is defined as
Fn−1 + Fn−2. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... The value of F30 is greater
than a
million! It is easy to see that the Fibonacci numbers grow exponentially. As an exercise, try to show that Fn ≥ 2n/2
for sufficiently large n by a simple induction.
The Wikipedia page for Fibonacci numbers is also full of useful information: http://en.wikipedia.
org/wiki/Fibonacci number.
Here is a simple program to compute Fibonacci numbers that slavishly follows the definition.
