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.
ALGORITHM 6 Naive String Matcher.
procedure string match (n, m: positive integers, m ≤ n, t1, t2,… , tn, p1, p2,… , pm: characters)
for s := 0 to n − m
j := 1
while ( j ≤ m and ts+j = pj)
j := j + 1
if j > m then print “s is a valid shift”
When this pattern begins at position s + 1 in the text T,
we say that P occurs with shift s in T, that is, when ts+1 = p1, ts+2 = p2, … , ts+m = pm.
Greedy Algorithm:
Algorithms that make what seems to be the “best” choice at each step are called greedy algorithms.
Once we know that a greedy algorithm finds
a feasible solution, we need to determine whether it has found an optimal solution
we call the algorithm “greedy” whether or not it finds an optimal solution.
ALGORITHM 7 Cashier’s Algorithm:
procedure change(c1, c2,… , cr: values of denominations of coins, where c1 > c2 > ⋯ > cr; n: a positive integer)
for i := 1 to r
di := 0 {di counts the coins of denomination ci used}
while n ≥ ci
di := di + 1 {add a coin of denomination ci}
n := n − ci
{di is the number of coins of denomination ci in the change for i = 1, 2, … , r}prove tht cashier’s algo doesn’t always give an optimal solution.
Counterexample:
For example, if we have only quarters, dimes, and pennies (and
no nickels) to use, the cashier’s algorithm would make change for 30 cents using six coins—a
quarter and five pennies—whereas we could have used three coins, namely, three dimes.
The lemma of n cents change:
and prove it.
If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies
using the fewest coins possible has at most two dimes, at most one nickel, at most four pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels, and
pennies cannot exceed 24 cents.
Thereom of cashiers Algo:
Prove it:
The cashier’s algorithm (Algorithm 7) always makes changes using the fewest coins possible
when change is made from quarters, dimes, nickels, and pennies.
ALGORITHM 8 Greedy Algorithm for Scheduling Talks.
procedure schedule(s1 ≤ s2 ≤ ⋯ ≤ sn: start times of talks,e1 ≤ e2 ≤ ⋯ ≤ en: ending times of talks)
sort talks by finish time and reorder so that e1 ≤ e2 ≤ ⋯≤ en
S := ∅
for j := 1 to n
if talk j is compatible with S then
S := S ∪ {talk j}
return S{S is the set of talks scheduled}
The Halting Problem:
Halting problem. It
asks whether there is a procedure that does this:
It takes as input a computer program and
input to the program and determines whether the program will eventually stop when run with
this input.
What u need to know before the proof pf halting problem:
we cannot
simply run a program and observe what it does to determine whether it terminates when run with the given input. If the program halts, we have our answer, but if it is still running after any
fixed length of time has elapsed, we do not know whether it will never halt or we just did not
wait long enough for it to terminate. After all, it is not hard to design a program that will stop
only after more than a billion years has elapsed
Prove the halting problem:
there is no procedure that solves the halting problem. Textbook page 213. 1. program can be thought of as data. so it can be its inout. Say H is solution to this prob, devise K such that it does opp pf H. Now feed k as K's input and H will produce contradictions. Hence H is not a solution.
Median and mean:
The median of a set of integers is the middle element in the list when these integers are listed in order of increasing size.
The mean of a set of integers is the sum of the integers divided by the number of integers in the set.
Palindrome:
A palindrome is a string that reads the same forward
and backward
Ternary Search:
procedure ternary search(s: integer, a1,a2,… , an:
increasing integers)
i := 1
j := n
while i < j − 1
l := ⌊(i + j)∕3⌋
u := ⌊2(i + j)∕3⌋
if x > au then i := u + 1
else if x > al then
i := l + 1
j := u
else j := l
if x = ai then location := i
else if x = aj then location := j
else location := 0
return location {0 if not found}Mode:
In a list of elements the same element may appear several
times. A mode of such a list is an element that occurs at least
as often as each of the other elements; a list has more than
one mode when more than one element appears the maximum
number of times.
Anagrams:
Two strings are anagrams if each can be formed from the other string by rearranging its characters.
Adapt the bubble sort algorithm so that it stops when no
interchanges are required. Express this more efficient version of the algorithm in pseudocode.
procedure betterbubblesort( ai, . .. , an)
i := 1
stilLinterchanging :=true
while i < n and stilLinterchanging
stilLinterchanging := false
for j : = 1 to n - i
if a1 > a1+1 then
stilLinterchanging := true
interchange a1 and a1+1
i := i + 1
{ a 1 •... , an is in nondecreasing order}Selection Sort:
The selection sort begins by finding the least element in the list. This element is moved to the front. Then the least element among the remaining elements is found and put into the second position. This procedure is repeated until the entire list
has been sorted.
Binary Insertion Sort:
The binary insertion sort is a variation of the insertion sort
that uses a binary search technique (see Exercise 46) rather
than a linear search technique to insert the ith element in the
correct place among the previously sorted elements.
