Data Structures and Algorithms

Lecture 2. Introduction to Algorithms

and Types of Algorithms
Reading and Acknowledgments
Chapter 1 in Chaffer (2009) A practical introduction to data structures and
●

algorithm analysis, 3rd edition

— http://courses.cs.vt.edu/cs3114/Spring09/book.pdf

Chapter 1 in Corman, Leiserson, and Rivest (2001) Introduction to Algorithms,

●

2nd edition
— http://www.mif.vu.lt/~valdas/ALGORITMAI/LITERATURA/Cormen/Cormen.pdf

Lecture Notes
●

— http://www.cis.upenn.edu/~matuszek/cit594-2014/

Chapter 1 in Levitin (2012) Introduction to the Design and Analysis of

●

Algorithms, 3rd edition

2
Learning Outcomes

To appreciate and differentiate between the different types of

●

algorithms

3
What is an algorithm?

●An algorithm is a sequence of unambiguous instructions for

solving a problem, i.e., for obtaining a required output for any
legitimate input in a finite amount of time.

problem

algorithm

input computer output

4
What are algorithms used for?

●To solve computation problems

●Specifies an input-output relationship in general terms

— What does the input look like?

— What should the output be for each input?

●Example

— Input: an integer number N

— Output: Is the number prime?

●Example

— Input: A list of names of people

— Output: The same list sorted alphabetically

●Example

— Input: A picture in digital format

— Output: An English description of what the picture shows

We seek algorithms which are correct and efficient.

5
Properties of algorithms

●It must be correct. In other words, it must compute the desired

function, converting each input to the correct output.
●It is composed of a series of concrete steps. Concrete means that
the action described by that step is completely understood — and
doable — by the person or machine that must perform the algorithm.
Each step must also be doable in a finite amount of time.
There can be no ambiguity as to which step will be performed next.
●

Often it is the next step of the algorithm description.

●It must be composed of a finite number of steps. If the description for
the algorithm were made up of an infinite number of steps, we could
never hope to write it down, nor implement it as a computer program.
● It must terminate. In other words, it may not go into an infinite loop.

6
Algorithm Correctness

For any algorithm, we must prove that it always returns the

●

desired output for all legal instances of the problem.

●Example: A sorting algorithm must return the correct output even
if the input is already sorted, or the input contains repeated
elements

Algorithm correctness may not be obvious in some optimization

●

problems

7
Are the following algorithms?

Shampoo instructions
● Cooking recipe
●
— “Lather. Rinse. Repeat.” — “Stir-fry until crisp-tender.”

8
Are the following algorithms?

● Shampoo instructions ● Cooking recipe

— “Lather. Rinse. Repeat.” — “Stir-fry until crisp-tender.”
— Does not terminate — Next step ambiguous

● If not an algorithm, then what are they?

— A procedure
— A heuristic

9
Is the following an algorithm?

●Long division
14
●58 / 4 4 58
= 14 + remainder 2 4
18
16
2

10
Example of algorithm

● To sort a sequence of numbers into ascending order

● Here is how we formally define the sorting problem:

E.g. given the input sequence {31, 41, 59, 26, 41, 58}, a sorting
●

algorithm returns as output the sequence {26, 31, 41, 41, 58, 59}.

An algorithm is said to be correct if, for every input instance, it halts

●

with the correct output.

11
Other computational problems:
The Human Genome Project
One of the initiatives of the Human Genome Project consists of
●

— identifying all the 100,000 genes in human DNA

— determining the sequences of the 3 billion base pairs (A,T,C,G) that
make up human DNA
— storing this information in databases
— developing tools for data analysis.
Each of these steps requires sophisticated algorithms.
●

●Many methods to solve these biological problems use ideas from several of
the topics to be discussed in this module, thereby enabling scientists to
accomplish tasks while using resources efficiently.

●The savings are in time, both human and machine, and in money, as more
information can be extracted from data produced by laboratory techniques.

12
Other computational problems:
The Internet
●The Internet enables people all around the world to quickly access and
retrieve large amounts of information.

With the aid of clever algorithms, sites on the Internet are able to manage and
●

manipulate this large volume of data.

Examples of problems that make essential use of algorithms include:

●

— finding good routes on which the data will travel

— using a search engine to quickly find pages on which information of
interest resides

13
Other computational problems:
E-commerce
●Electronic commerce enables goods and services to be negotiated and
exchanged electronically, and it depends on the privacy of personal
information such as credit card numbers, passwords, and bank statements.

The core technologies used in electronic commerce include public-key

●

cryptography and digital signatures, which are based on numerical

algorithms and number theory.

14
Other computational problems:
Manufacturing and other commercial applications
●Manufacturing and other commercial enterprises often need to allocate scarce
resources in the most beneficial way.
— An oil company may wish to know where to place its wells in order to
maximize its expected profit.
— A political candidate may want to determine where to spend money
buying campaign advertising in order to maximize the chances of
winning an election.
— An airline may wish to assign crews to flights in the least expensive way
possible, making sure that each flight is covered and that government
regulations regarding crew scheduling are met.
— An Internet service provider may wish to determine where to place
additional resources in order to serve its customers more effectively.

All of these are examples of problems that can be solved using linear
●

programming.

15
Describing Algorithms

Algorithms can be implemented in any programming language

●

Usually we use “pseudo-code” to describe algorithms

●

Testing whether input N is prime:

for j = 2 .. N-1
if N mod j == 0
Output “N is composite” and halt
Output “N is prime”

However, in this module we will describe algorithms in Java

●

16
Programs VERSUS Algorithms

A program is an implementation of an algorithm in a

●

programming language
Many programs can exist for the same algorithm
●

— Different programming languages

— Different programming standards
— Different details, e.g., error checking
Algorithm: Abstract mathematical object
●

Program: Practical realization of an algorithm

●

17
Problem, Algorithm and Program

Problem problem
Given n, find n!

Algorithm algorithm
If n = 0, n! = 1
Else n! = n * (n – 1)!

Program in Java
public long factorial(int n) { input computer output
if(n == 0) return 1; program
else return n * factorial(n – 1);
}

18
Activity – Greatest Common Divisor
●The first algorithm “invented” in history was Euclid’s algorithm for finding
the greatest common divisor (GCD) of two natural numbers
●Definition: The GCD of two numbers, when at least one of them is not
zero, is the largest positive integer that divides the numbers without a
remainder.
● For example, the GCD of 8 and 12 is 4.

The GCD Problem

Input: natural numbers x, y

Output: GCD(x,y) – their GCD

Activity: Write the GCD algorithm (pseudo-code)

19
Activity – Greatest Common Divisor

Activity: Write the GCD program in Java

20
Activity – Greatest Common Divisor

public int gcd(int x, int y) {

while (y!=0) {
int temp = x%y;
x = y;
y = temp;
}
return x;
}

Activity: Draw the trace table for gcd(72, 120)

21
Activity – Greatest Common Divisor
public int gcd(int x, int y) {
while (y!=0) {
int temp = x%y;
x = y;
y = temp;
}
return x;
}

GCD(72, 120)
temp x y
After 0 rounds -- 72 120
After 1 round 72 120 72
After 2 rounds 48 72 48
After 3 rounds 24 48 24
After 4 rounds 0 24 0
Output: 24
22
Algorithm classification

Algorithms that use a similar problem-solving approach can be

●

grouped together
This classification scheme is neither exhaustive nor disjoint
●

●The purpose is not to be able to classify an algorithm as one type

or another, but to highlight the various ways in which a problem
can be solved

23
Recursive Dynamic Progr. Brute-Force Randomized

A short list of categories

● Algorithm types we will consider include:

(1) Simple recursive algorithms
(2) Backtracking algorithms
(3) Divide and conquer algorithms
(4) Dynamic programming algorithms
(5) Greedy algorithms
(6) Branch and bound algorithms
(7) Brute force algorithms
(8) Randomized algorithms

24
Recursive Dynamic Progr. Brute-Force Randomized

Simple recursive algorithms

● A simple recursive algorithm

— Solves the base cases directly

— Recurs with a simpler subproblem

—Does some extra work to convert the solution to the simpler

subproblem into a solution to the given problem

“Simple” because several of the other algorithm types

●

are inherently recursive

25
Recursive Dynamic Progr. Brute-Force Randomized

Example recursive algorithms

● To count the number of elements in a list

— If the list is empty, return zero; otherwise
—Step past the first element, and count the remaining elements in
the list
— Add one to the result

26
Recursive Dynamic Progr. Brute-Force Randomized

Example recursive algorithms

● To test if a value occurs in a list:

—If the list is empty, return false; otherwise
—If the first thing in the list is the given value,

return true; otherwise

—Step past the first element, and test whether the

value occurs in the remainder of the list

27
Recursive Dynamic Progr. Brute-Force Randomized

Recursion versus Iteration

●In general, an iterative version of a method will execute more efficiently

in terms of time and space than a recursive version.

●This is because the overhead involved in entering and exiting a

function in terms of stack I/O is avoided in iterative version.

Sometimes we are forced to use iteration because stack cannot handle

●

enough activation records

● E.g. power(2, 5000)

28
Recursive Dynamic Progr. Brute-Force Randomized

Why recursion?
Usually recursive algorithms have less code, therefore algorithms can
●

be easier to write and understand – e.g. Towers of Hanoi. However,

avoid using excessively recursive algorithms.
●Sometimes recursion provides a much simpler solution. Obtaining the
same result using iteration requires complicated coding – e.g. Quicksort,
Towers of Hanoi, etc.
●Recursive methods provide a very natural mechanism for processing
recursive data structures. A recursive data structure is a data structure
that is defined recursively – e.g. Tree.
●Functional programming languages such as Haskell do not have explicit
loop constructs. In these languages looping is achieved by recursion.
Some recursive algorithms are more efficient than equivalent iterative
●

algorithms. Example, each of the following recursive power methods

evaluate xn more efficiently than the iterative one.

29
Recursive Dynamic Progr. Brute-Force Randomized

Why recursion?
Some recursive algorithms are more efficient than equivalent iterative
●

algorithms.
Example, each of the following recursive power methods evaluate xn
●

more efficiently than the iterative one.

// iterative

public long power(int x, int n) {

long product = 1;

for(int i=1; i<=n; i++)

product *= x

return product;

30
Recursive Dynamic Progr. Brute-Force Randomized

Why recursion?
// recursive

public long power(int x, int n) {

if (n==1)
return x;

if (n==0)
return 1;

long t = power(x, n/2);

if (n%2 == 0)

return t*t;

return x*t*t;
}

31
Recursive Dynamic Progr. Brute-Force Randomized

Backtracking
●Suppose you have to make a series of decisions, among various
choices, where
—You don’t have enough information to know what to choose

—Each decision leads to a new set of choices

—Some sequence of choices (possibly more than one) may be a

solution to your problem

●Backtracking is a methodical way of trying out various sequences

of decisions, until you find one that “works”

Recursive Dynamic Progr. Brute-Force Randomized

Example: Solving a maze

●Given a maze, find a path from start to finish
●At each intersection, you have to decide between three or fewer

choices:
—Go straight

—Go left

—Go right

●You don’t have enough information to choose correctly

●Each choice leads to another set of choices

●One or more sequences of choices may (or may not) lead to a

solution
●Many types of maze problem can be solved with backtracking
Recursive Dynamic Progr. Brute-Force Randomized

Backtracking algorithms

●For many real-world problems, the solution process consists of working

your way through a sequence of decision points in which each choice
leads you further along some path.
— If you make the correct set of choices, you end up at the solution.
— On the other hand, if you reach a dead end or otherwise discover
that you have made an incorrect choice somewhere along the
way, you have to backtrack to a previous decision point and try a
different path.
Algorithms that use this approach are called backtracking
●

algorithms.

34
Recursive Dynamic Progr. Brute-Force Randomized

Backtracking algorithms (contd)

Backtracking is a simple, yet elegant, recursive technique which can

●

be put to a variety of uses.

●While backtracking is useful for hard problems to which we do not know

more efficient solutions, it is a poor solution for the everyday problems
that other techniques are much better at solving.

However, dynamic programming and greedy algorithms can be thought

●

of as optimizations to backtracking, so the general technique behind

backtracking is useful for understanding these more advanced concepts.

35
Recursive Dynamic Progr. Brute-Force Randomized

Backtracking algorithms (contd)

If we think of a backtracking algorithm as the process of repeatedly

●

exploring paths until we encounter the correct solution, the process

appears to be of an iterative nature.
●As it happens, however, most problems of this form are easier to solve
recursively.
● The fundamental recursive insight is simply this:
— a backtracking problem has a solution if and only if at least one of
the smaller backtracking problems that results from making each
possible initial choice has a solution.

36
Recursive Dynamic Progr. Brute-Force Randomized

Backtracking algorithms (contd)

● Backtracking algorithms are based on a depth-first recursive search

● A backtracking algorithm:

— Tests to see if a solution has been found, and if so, return it;
otherwise
‣ For each choice that can be made at this point,
* Make that choice
* Recur
* If the recursion returns a solution, return it
‣ If no choices remain, return failure

37
Recursive Dynamic Progr. Brute-Force Randomized

Backtracking and the Tree structure

●Backtracking can be thought of as searching a tree for a particular “goal”
leaf node

● A tree is composed of nodes.

● There are three kinds of nodes:

The (one) root node

Internal nodes

Leaf nodes
Recursive Dynamic Progr. Brute-Force Randomized

Depth-First Search

●Depth-First Traversal:
— Preorder traversal
— Inorder traversal (for binary trees only)
— Postorder traversal

39
Recursive Dynamic Progr. Brute-Force Randomized

Depth-First Search

Name For each node

Preorder Visit the node.

(N-L-R) Visit the left subtree, if any.
Visit the right subtree, if any.

Inorder Visit the left subtree, if any. Visit the node

(L-N-R) Visit the right subtree, if any.

Postorder Visit the left subtree, if any.

(L-R-N) Visit the right subtree, if any.
Visit the node.

40
Recursive Dynamic Progr. Brute-Force Randomized

Depth-first Preorder Traversal

N-L-R
H

D L

B F J N

A C E G I K M O

H D B A C F E G L J I K N M O

41
Recursive Dynamic Progr. Brute-Force Randomized

Depth-first Inorder Traversal

L-N-R
H

D L

B F J N

A C E G I K M O

A B C D E F G H I J K L M N O

Note: An inorder traversal of a BST visits the keys sorted in increasing order.

42
Recursive Dynamic Progr. Brute-Force Randomized

Depth-first Postorder Traversal

L-R-N
H

D L

B F J N

A C E G I K M O

A C B E G F D I K J M O N L H

43
Recursive Dynamic Progr. Brute-Force Randomized

Example of backtracking algorithm

Solving a maze
●Consider a maze, shown in the diagram above, where a player has to

decide how to get from room A to room B.

●The player can move from room to room through the corridors

provided, but has no way of telling how many corridors a room is

connected to until he reaches that room.

44
Recursive Dynamic Progr. Brute-Force Randomized

Example of backtracking algorithm

We will now see a sample session to understand the approach the

●

player uses to solve the maze.

Maze Solved!!!

Dead End

Dead End

Dead End

45
Recursive Dynamic Progr. Brute-Force Randomized

Divide-and-Conquer

● A divide and conquer algorithm consists of two parts:

— Divide the problem into smaller subproblems of the same type,
and solve these subproblems recursively
— Combine the solutions to the subproblems into a solution to the
original problem
● Analogy: A successful military strategy
— Easier to defeat one army of 50,000 men, followed by another
army of 50,000 men than to beat a single 100,000 man army
— A wise general would attack so as to divide the enemy army into
two forces and then mop up one after the other

46
Recursive Dynamic Progr. Brute-Force Randomized

Divide-and-Conquer (contd)

●A divide and conquer algorithm is based on dividing problem into

sub-problems

● Approach

— Divide problem into smaller subproblems

‣ Subproblems must be of same type

‣ Subproblems do not need to overlap

— Solve each subproblem recursively

— Combine solutions to solve original problem

●Traditionally, an algorithm is only called “divide and conquer” if it

contains at least two recursive calls

47
Recursive Dynamic Progr. Brute-Force Randomized

Divide-and-Conquer (contd)
Problem of size n

Sub-problem 1 Sub-problem 2
of size n/2 of size n/2

Solution to Solution to
sub-problem 1 sub-problem 2

Solution to
original problem

Note:
● Divide and conquer algorithms often implemented using recursion
● But, not all recursive functions are divide-and-conquer algorithms

48
Recursive Dynamic Progr. Brute-Force Randomized

Example – Binary Search

●Find middle element from sorted array

●If middle element is the number being sought, return success

●Otherwise

— If number to be sought is smaller than middle element then

recursively search for number in first half of array (excluding

middle element)
— If number to be sought is larger than middle element then

recursively search for number in second half of array (excluding

middle element)

49
Recursive Dynamic Progr. Brute-Force Randomized

Example – Quicksort and Mergesort

● Quicksort:

— Partition the array into two parts (smaller numbers in one part,
larger numbers in the other part)

— Quicksort each of the parts

— No additional work is required to combine the two sorted parts

● Mergesort:

— Cut the array in half, and mergesort each half

— Combine the two sorted arrays into a single sorted array by

merging them

50
Recursive Dynamic Progr. Brute-Force Randomized

Dynamic Programming

●A dynamic programming algorithm remembers past results and uses

them to find new results
●Dynamic programming is generally used for optimization problems

— Multiple solutions exist, need to find the “best” one

— Requires “optimal substructure” and “overlapping subproblems”

‣ Optimal substructure: Optimal solution contains optimal

solutions to subproblems
‣ Overlapping subproblems: Solutions to subproblems can be
stored and reused in a bottom-up fashion
●Like divide and conquer, DP solves problems by combining solutions to

sub-problems.
●Unlike divide and conquer, sub-problems are not independent.

— Sub-problems may share sub-sub-problems, …

51
Recursive Dynamic Progr. Brute-Force Randomized

Dynamic Programming (contd)

● Approach
— Divide problem into smaller subproblems
‣ Sub-problems must be of same type
‣ Sub-problems must overlap
— Solve each sub-problem recursively
‣ May simply look up solution
— Combine solutions to solve original problem
— Store solution to problem

52
Recursive Dynamic Progr. Brute-Force Randomized

Fibonacci Numbers (Recall)

● Fibonacci numbers
— fibonacci(0) = 1
— fibonacci(1) = 1
— fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
● Recursive algorithm to calculate fibonacci(n)
— If n is 0 or 1, return 1
— Else compute fibonacci(n-1) and fibonacci(n-2)
— Return their sum
● Simple algorithm BUT
n
— Exponential time O(2 ) Very time-consuming!

53
Recursive Dynamic Progr. Brute-Force Randomized

Fib(5)
+

Fib(4) Fib(3)
+ +

Fib(3) Fib(2) Fib(2) Fib(1)

+ + +

Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)

+

Fib(1) Fib(0)

54
Recursive Dynamic Progr. Brute-Force Randomized

Example: Fibonacci Numbers

● Dynamic programming version of fibonacci(n)

● To find the nth Fibonacci number:
— If n is zero or one, return one; otherwise,
— Compute, or look up in a table, fibonacci(n-1) and fibonacci(n-2)
— Find the sum of these two numbers
— Store the result in a table and return it
Since finding the nth Fibonacci number involves finding all smaller
●

Fibonacci numbers, the second recursive call has little work to do

● The table may be preserved and used again later

55
Recursive Dynamic Progr. Brute-Force Randomized

Greedy algorithms

●A greedy algorithm is an algorithm that follows the problem solving

heuristic of making the locally optimal choice at each stage with the
hope of finding a global optimum.
●In many problems, a greedy strategy does not in general produce an

optimal solution, but nonetheless a greedy heuristic may yield locally

optimal solutions that approximate a global optimal solution in a
reasonable time.
●A greedy algorithm works in phases: At each phase:
—You take the best you can get right now, without regard for future

consequences
—You hope that by choosing a local optimum at each step, you will end

up at a global optimum

56
Recursive Dynamic Progr. Brute-Force Randomized

Example: Counting money

●Suppose you want to count out a certain amount of money, using the
fewest possible bills and coins. A greedy algorithm would do this would
be:
●At each step, take the largest possible bill or coin that does not

overshoot
—Example: To make $6.39, you can choose:

‣a $5 bill
‣a $1 bill, to make $6
‣a 25¢ coin, to make $6.25
‣A 10¢ coin, to make $6.35
‣four 1¢ coins, to make $6.39
●For US money, the greedy algorithm always gives the optimum solution

57
Recursive Dynamic Progr. Brute-Force Randomized

A failure of the greedy algorithm

In some (fictional) monetary system, “krons” come in 1 kron, 7 kron,

●

and 10 kron coins

● Using a greedy algorithm to count out 15 krons, you would get
— A 10 kron piece + Five 1 kron pieces
— This requires six coions
● A better solution would be to use
— Two 7 kron pieces + one 1 kron piece
— This only requires three coins
●The greedy algorithm results in a solution, but not in an optimal
solution

58
Recursive Dynamic Progr. Brute-Force Randomized

A scheduling problem

●You have to run nine jobs, with running times of 3, 5, 6, 10, 11, 14, 15,
18, and 20 minutes
●You have three processors on which you can run these jobs

●You decide to do the longest-running jobs first, on whatever processor

is available

P1 20 10 3

P2 18 11 6

P3 15 14 5

●Time to completion: 18 + 11 + 6 = 35 minutes

●This solution isn’t bad, but we might be able to do better

59
Recursive Dynamic Progr. Brute-Force Randomized

Another approach

●What would be the result if you ran the shortest job first?
●Again, the running times are 3, 5, 6, 10, 11, 14, 15, 18, and 20 minutes

P1 3 10 15

P2 5 11 18

P3 6 14 20

●That wasn’t such a good idea; time to completion is now 6 + 14 + 20 =

40 minutes
●Note, however, that the greedy algorithm itself is fast

●All we had to do at each stage was pick the minimum or maximum

60
Recursive Dynamic Progr. Brute-Force Randomized

An optimum solution
P1 20 14
P2
18 11 5
P3

15 10 6 3

● This solution is clearly optimal

● Clearly, there are other optimal solutions
● How do we find such a solution?
— One way: Try all possible assignments of jobs to processors
— Unfortunately, this approach can take exponential time
● Better solutions do exist. E.g. Huffman encoding

61
Recursive Dynamic Progr. Brute-Force Randomized

Traveling salesman
●A salesman must visit every city (starting from city A), and wants to
cover the least possible distance
—He can revisit a city (and reuse a road) if necessary

●He does this by using a greedy algorithm: He goes to the next nearest

city from wherever he is

A 2 B 4 C ●From A he goes to B
●From B he goes to D

●This is not going to result in a shortest

3 3
4 4 path!
●The best result he can get now will be

ABDBCE, at a cost of 16
D ●An actual least-cost path from A is

E ADBCE, at a cost of 14

62
Recursive Dynamic Progr. Brute-Force Randomized

Branch and bound algorithms

●Branch and bound algorithms are generally used for optimization

problems
●As the algorithm progresses, a tree of subproblems is formed

● The original problem is considered the “root problem”

A method is used to construct an upper and lower bound for a given
●

problem
● At each node, apply the bounding methods
— If the bounds match, it is deemed a feasible solution to that
particular subproblem
— If bounds do not match, partition the problem represented by that
node, and make the two subproblems into children nodes
●Continue, using the best known feasible solution to trim sections of the
tree, until all nodes have been solved or trimmed

63
Recursive Dynamic Progr. Brute-Force Randomized

Example branch and bound algorithm

● Travelling salesman problem

●Consider the root problem to be the problem of finding the shortest

route through a set of cities visiting each city once

● Split the node into two child problems:

— Shortest route visiting city A first

— Shortest route not visiting city A first

● Continue subdividing similarly as the tree grows

64
Recursive Dynamic Progr. Brute-Force Randomized

Brute-force Algorithm

●It is a straightforward approach, usually based directly on the problem’s

statement and definitions of the concepts involved.
● Examples
n
— Computing a (a > 0, n a nonnegative integer)
— Computing n!
— Multiplying two matrices
— Searching for a key of a given value in a list

65
Recursive Dynamic Progr. Brute-Force Randomized

Brute-force Algorithm (contd)

●A brute force algorithm simply tries all possibilities until a

satisfactory solution is found

Generate
Filter Solutions
Candidates

Trash

66
Recursive Dynamic Progr. Brute-Force Randomized

Brute-force Algorithm (contd)

A brute force algorithm can be:

●Optimizing: Find the best solution. This may require finding all solutions,
or if a value for the best solution is known, it may stop when any best
solution is found
— Example: Finding the best path for a traveling salesman
— Requires exponential time O(2n)
● Satisfying: Stop as soon as a solution is found that is good enough
— Example: Finding a traveling salesman path that is within 10% of
optimal
● Generally most expensive approach

67
Recursive Dynamic Progr. Brute-Force Randomized

Brute-force Algorithm (contd)

● Often, brute force algorithms require exponential time

● Various heuristics and optimizations can be used

— Heuristic: A “rule of thumb” that helps you decide which possibilities

to look at first

— Optimization: In this case, a way to eliminate certain possibilities

without fully exploring them

68
Recursive Dynamic Progr. Brute-Force Randomized

Heuristic Algorithm

●Heuristic: “rule of thumb”

●The term heuristic is used for algorithms which find solutions among all
possible ones, but they do not guarantee that the best will be found, therefore
they may be considered as approximate and not accurate algorithms.

●Heuristic algorithms

— Based on trying to guide search for solution

— Approach

‣ Generate and evaluate possible solutions

* Using “rule of thumb”

* Stop if satisfactory solution is found

— Can reduce complexity

— Not guaranteed to yield best solution

— Heuristics used frequently in real applications 69

Recursive Dynamic Progr. Brute-Force Randomized

Heuristic Algorithm (contd)

●These algorithms, usually find a solution close to the best one and they
find it fast and easily.
●Sometimes these algorithms can be accurate, that is they actually find
the best solution, but the algorithm is still called heuristic until this best
solution is proven to be the best.
The method used from a heuristic algorithm is one of the known
●

methods, such as greediness, but in order to be easy and fast the

algorithm ignores or even suppresses some of the problem's demands.

70
Recursive Dynamic Progr. Brute-Force Randomized

Heuristic for TSP

● Find possible paths using recursive backtracking

— Search 2 lowest cost edges at each node first
● Calculate cost of each path
● Return lowest cost path from first 100 solutions

● Not guaranteed to find best solution

● Heuristics used frequently in real applications

71
Recursive Dynamic Progr. Brute-Force Randomized

Randomized algorithms

●A randomized algorithm is just one that depends on random numbers

for its operation

● Examples of randomized algorithms

— Using random numbers to help find a solution to a problem

— Using random numbers to improve a solution to a problem

● Related topics

— How to generate “random” numbers

— How to generate random data for testing (or other) purposes

72
Recursive Dynamic Progr. Brute-Force Randomized

Randomized algorithms

●A randomized algorithm uses a random number at least once during

the computation to make a decision
● Example
— In Quicksort using a random number to choose a pivot
—Trying to factor a large prime by choosing random numbers as
possible divisors

73
Recursive Dynamic Progr. Brute-Force Randomized

Pseudo-random numbers

● The computer is not capable of generating truly random numbers

The computer can only generate pseudorandom numbers --

●

numbers that are generated by a formula

●Pseudorandom numbers look random, but are perfectly predictable if

you know the formula

— Pseudorandom numbers are good enough for most purposes, but

not all -- e.g.not for serious security applications
● Devices for generating truly random numbers do exist
— They are based on radioactive decay, or on lava lamps

“Anyone who attempts to generate random numbers by deterministic

●

means is, of course, living in a state of sin.”

—John von Neumann

74
Recursive Dynamic Progr. Brute-Force Randomized

Generating random numbers

●Perhaps the best way of generating “random” numbers is by the linear
congruential method

— r = (a * r + b) % m; where a and b are large prime numbers, and m is 232

or 264

— The initial value of r is called the seed

— If you start over with the same seed, you get the same sequence of
“random” numbers

●One advantage of the linear congruential method is that it will (eventually)

cycle through all possible numbers

●Almost any “improvement” on this method turns out to be worse

— “Home-grown” methods typically have much shorter cycles

●There are complex mathematical tests for “randomness” which you should
know if you want to “roll your own”
75
Recursive Dynamic Progr. Brute-Force Randomized

Getting pseudo-random numbers in Java

●Java package
— java.security.SecureRandom
●Constructor
— new SecureRandom()
— SecureRandom(byte[] seed)
●Methods
— void setSeed(long seed)
— nextBoolean()
— nextFloat(), nextDouble() // 0.0 < return value < 1.0
32 64
— nextInt(), nextLong() // all 2 or 2 possibilities
— nextInt(int n) // 0 < return value < n
— nextGaussian()
‣ Returns a double, normally distributed with a mean of 0.0 and a
standard deviation of 1.0 76
Recursive Dynamic Progr. Brute-Force Randomized

Example: Shuffling an array

● Shuffle every item
public void shuffle(int[] array) {
for (int i = array.length; i > 0; i--) {
int j = random.nextInt(i);
swap(array, i - 1, j);
}
}
// all permutations are equally likely
● Shuffle with every item moved elsewhere:

public void shuffle(int[] array) {

for (int i = array.length; i > 1; i--) {
int j = random.nextInt(i - 1);
swap(array, i - 1, j);
}
}
// all permutations are not equally likely
77