3.1 Algorithms

Question 1

Algorithm:

Answer 1

An algorithm is a finite sequence of precise instructions for performing a computation or for
solving a problem.

Question 2

Pseudocode :

Answer 2

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.

Question 3

Algorithm Vs Pseudocode:

Answer 3

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

Question 4

ALGORITHM 1 Finding the Maximum Element in a Finite Sequence.

Answer 4

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}

Question 5

Trace:

Answer 5

To gain insight into how an algorithm works it is useful to construct a trace that shows its
steps when given specific input.

Question 6

PROPERTIES OF ALGORITHMS:

7

Answer 6

▶ 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.

Question 7

ABU JA‘FAR MOHAMMED IBN MUSA AL-KHOWARIZMI (C. 780 – C. 850) al-Khowarizmi,

Answer 7

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

Question 8

Searching Algorithm:

General problem statement:
and what’s solution?

Answer 8

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.

Question 9

ALGORITHM 2 The Linear Search Algorithm.

Answer 9

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}

Question 10

ALGORITHM 3 The Binary Search Algorithm:

Answer 10

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}

Question 11

Sorting:

Answer 11

Sorting is putting these elements into a list in which the elements are in increasing
order.

Question 12

ALGORITHM 4 The Bubble Sort.

Answer 12

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

Question 13

ALGORITHM 5 The Insertion Sort.

Answer 13

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}

Question 14

String Matching:

Answer 14

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 15

Question about genome:
Problems in Bioinformatics:
4 bases of DNA:

Answer 15

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.

Question 16

ALGORITHM 6 Naive String Matcher.

Answer 16

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.

Question 17

Greedy Algorithm:

Answer 17

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.

Question 18

ALGORITHM 7 Cashier’s Algorithm:

Answer 18

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}

Question 19

prove tht cashier’s algo doesn’t always give an optimal solution.

Answer 19

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.

Question 20

The lemma of n cents change:

and prove it.

Answer 20

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.

Question 21

Thereom of cashiers Algo:

Prove it:

Answer 21

The cashier’s algorithm (Algorithm 7) always makes changes using the fewest coins possible
when change is made from quarters, dimes, nickels, and pennies.

Question 22

ALGORITHM 8 Greedy Algorithm for Scheduling Talks.

Answer 22

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}

Question 23

The Halting Problem:

Answer 23

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.

Question 24

What u need to know before the proof pf halting problem:

Answer 24

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

Question 25

Prove the halting problem:

Answer 25

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.

Question 26

Median and mean:

Answer 26

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.

Question 27

Palindrome:

Answer 27

A palindrome is a string that reads the same forward

and backward

Question 28

Ternary Search:

Answer 28

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}

Question 29

Mode:

Answer 29

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.

Question 30

Anagrams:

Answer 30

Two strings are anagrams if each can be formed from the other string by rearranging its characters.

Question 31

Adapt the bubble sort algorithm so that it stops when no

interchanges are required. Express this more efficient version of the algorithm in pseudocode.

Answer 31

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}

Question 32

Selection Sort:

Answer 32

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.

Question 33

Binary Insertion Sort:

Answer 33

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.