3.1 Algorithms Flashcards
Algorithm:
An algorithm is a finite sequence of precise instructions for performing a computation or for
solving a problem.
Pseudocode :
Pseudocode provides an intermediate step between an English language description of an algorithm and an implementation of
this algorithm in a programming language.
A key difference between this pseudocode and code in a
programming language is that we can use any well-defined instruction even if it would take
many lines of code to implement this instruction.
Algorithm Vs Pseudocode:
The steps of the algorithm are specified using
instructions resembling those used in programming languages. However, in pseudocode, the
instructions used can include any well-defined operations or statements
ALGORITHM 1 Finding the Maximum Element in a Finite Sequence.
procedure max(a1, a2,… , an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
return max{max is the largest element}Trace:
To gain insight into how an algorithm works it is useful to construct a trace that shows its
steps when given specific input.
PROPERTIES OF ALGORITHMS:
7
▶ Input. An algorithm has input values from a specified set.
▶ Output. From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.
▶ Definiteness. The steps of an algorithm must be defined precisely.
▶ Correctness. An algorithm should produce the correct output values for each set of input
values.
▶ Finiteness. An algorithm should produce the desired output after a finite (but perhaps
large) number of steps for any input in the set.
▶ Effectiveness. It must be possible to perform each step of an algorithm exactly and in a
finite amount of time.
▶ Generality. The procedure should be applicable for all problems of the desired form, not
just for a particular set of input values.
ABU JA‘FAR MOHAMMED IBN MUSA AL-KHOWARIZMI (C. 780 – C. 850) al-Khowarizmi,
an astronomer and mathematician, was a member of the House of Wisdom, an academy of scientists in Baghdad.
The name al-Khowarizmi means “from the town of Kowarizm,” which was then part of Persia, but is now called
Khiva and is part of Uzbekistan. al-Khowarizmi wrote books on mathematics, astronomy, and geography. Western Europeans first learned about algebra from his works. The word algebra comes from al-jabr, part of the title
of his book Kitab al-jabr w’al muquabala. This book was translated into Latin and was a widely used textbook.
His book on the use of Hindu numerals describes procedures for arithmetic operations using these numerals.
European authors used a Latin corruption of his name, which later evolved to the word algorithm, to describe
the subject of arithmetic with Hindu numerals
Searching Algorithm:
General problem statement:
and what’s solution?
Locate an element x in a list of
distinct elements a1, a2, … , an, or determine that it is not in the list. The solution to this search
problem is the location of the term in the list that equals x (that is, i is the solution if x = ai) and
is 0 if x is not in the list.
ALGORITHM 2 The Linear Search Algorithm.
procedure linear search(x: integer, a1, a2,… , an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location{location is the subscript of the term that equals x, or is 0 if x is not found}
ALGORITHM 3 The Binary Search Algorithm:
procedure binary search (x: integer, a1, a2,… , an: increasing integers)
i := 1{i is left endpoint of search interval}
j := n {j is right endpoint of search interval}
while i < j
m := ⌊(i + j)∕2⌋
if x > am then i := m + 1
else j := m
if x = ai then location := i
else location := 0
return location{location is the subscript i of the term ai equal to x, or 0 if x is not found}
Sorting:
Sorting is putting these elements into a list in which the elements are in increasing
order.
ALGORITHM 4 The Bubble Sort.
procedure bubblesort(a1,… , an : real numbers with n ≥ 2)
for i := 1 to n − 1
for j := 1 to n − i
if aj > aj+1 then interchange aj and aj+1
{a1,… , an is in increasing order}
We can imagine the elements
in the list placed in a column. In the bubble sort, the smaller elements “bubble” to the top
as they are interchanged with larger elements. The larger elements “sink” to the bottom
ALGORITHM 5 The Insertion Sort.
procedure insertion sort(a1, a2,… , an: real numbers with n ≥ 2)
for j := 2 to n
i := 1
while aj > ai
i := i + 1
m := aj
for k := 0 to j − i − 1
aj−k := aj−k−1
ai := m
{a1,… , an is in increasing order}String Matching:
Finding where a pattern occurs in a text string is called string matching.
where a particular
string of characters P, called the pattern, occurs, if it does, within another string T, called the text.
Question about genome:
Problems in Bioinformatics:
4 bases of DNA:
Many problems in bioinformatics arise in the study of DNA molecules, which are
made up of four bases: thymine (T), adenine (A), cytosine (C), and guanine (G). The process of
DNA sequencing is the determination of the order of the four bases in DNA. This leads to string
matching problems involving strings made up from the four letters T, A, C, and G. For instance,
we can ask whether the pattern CAG occurs in the text CATCACAGAGA. The answer is yes,
because it occurs with a shift of five characters. Solving questions about the genome requires
the use of efficient algorithms for string matching, especially because a string representing a
human genome is about 3 × 109 characters long.
