Here are the notes for the first lesson. These are just the first lines; the whole document can be found HERE.
Algorithms are at the core of Computer Science and, in particular, of string pattern recognition. However, the word “algorithm” does not possess a generally accepted definition. For the purposes of these notes, we will adopt an informal definition, which will be flexible enough to describe the solutions to problems in string pattern recognition but not so formal as to be lengthy and unfriendly. An algorithm is a procedure that takes an input and, after performing a series of well-defined computational operations, produces an output. Knuth [Knu73] has identified five properties –widely accepted– that an algorithm should have:
- Input: The initial values or input instance of the problem.
- Definiteness: Every algorithm must be precisely defined so that there is no ambiguity.
- Finiteness: An algorithm must terminate after a finite number of steps.
- Output: An algorithm must produce a set of final values out of the input.
- Efectiveness: All the operations must be sufficiently basic.
Berlinski in his year-2000 book [Ber00] provides a snappy, humoresque definition of an algorithm:
“In the logician’s voice:
“an algorithm is
a finite procedure,
written in a fixed symbolic vocabulary,
governed by precise instructions,
moving in discrete steps, 1, 2, 3, . . .,
whose execution requires no insight, cleverness,
intuition, intelligence, or perspicuity,
and that sooner or later comes to an end.”
..........................................................................................................................................................
..........................................................................................................................................................
[Ber00] D. Berlinski. The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer. Harcourt, Inc., San Diego, 1. edition, 2000. 1. editon 2000.
[Knu73] Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley, 1973.
Read more HERE
