Design and Analysis of Algorithm Brute Force 1.ppt

Design and Analysis of Algorithm Brute Force 1.ppt

1. Department of Computer Science
COMSATS University, Islamabad
Design and Analysis of Algorithm
TanveerAhmed Siddiqui

2. Department of Computer Science
Algorithm Design and Analysis Process
Understand the problem
Decide on : algorithm
design techniques etc.
Design an algorithm
Prove correctness
Analyze efficiency etc
Code the algorithm
Decide on : algorithm
design techniques etc.
Recap and Today Covered

3. Department of Computer Science
Reading Material
Read Chapter 3
Brute Force and Exhaustive Search

4. Department of Computer Science
HowtoDesignAlgorithmusingBruteForce(BF)Approach
Swapping two numbers
Computing a
n
(a > 0, n a nonnegative integer)
Computing n!
Add n numbers
Decimal to Binary conversion
Finding Maximum/Minimum Element in a list
Multiply two n by n Matrices
Selection Sort
Bubble Sort
Sequential Search/Linear Search
Conversion of a 2D array into 1D array
Find the value of polynomial
Objectives

5. Department of Computer Science
Designinganalgorithmisessentiallya
creativeeffortcontainingalltheingredients
ofathriller:
Adventure
Excitement
Challenge
Suspense.
Designing an Algorithm

6. Department of Computer Science
Designinganalgorithmiseasyifyou
know
design
techniques

7. Department of Computer Science
Analgorithmdesigntechniques(or“strategy”
or“paradigm”)isageneralapproachtosolve
problemsalgorithmically
Itcanbeapplicabletoavarietyofproblems
fromdifferentareaofcomputing.
Thedesignapproachdependsmainlyonthe
modelchosen.
What is algorithm designing technique?

8. Department of Computer Science
Theyprovideusguidanceindesigning
algorithmsfornewproblems
Theyrepresentacollectionoftoolsusefulfor
applications
Why do we need to know such techniques?

9. Department of Computer Science 9
Brute force
Decrease and conquer
Divide and conquer
Greedy technique
Dynamic programming
Backtracking
What are the most used techniques?

10. Department of Computer Science
Howyousolvethispuzzle:
Givena3×3boardwith8tiles(everytilehas
onenumberfrom1to8)andoneemptyspace.
Theobjectiveistoplacethenumbersontilesto
matchthefinalconfigurationusingtheempty
space.Wecanslidefouradjacent(left,right,
above,andbelow)tilesintotheemptyspace.
Initialstate:anyconfiguration
Goalstate:tilesinaspecificorder
10
Motivation Discussion

11. Department of Computer Science
Motivation Discussion
State Space

12. Department of Computer Science
What is Brute Force?
Astraightforwardapproachtosolvingaproblem,
usuallydirectlybasedontheproblem’sstatement
anddefinitionsoftheconceptsinvolved.
“Brute Force” means “Just do it!”
Generally, it involved iterating through all possible
solutions until a valid one is found.
OtherNames
GenerateandTest
ExhaustiveSearch
Can you name some problems that can be solved
with BF
Examples:
12
What is Brute Force?

13. Department of Computer Science
What is Brute Force?
How many examples do you know?
Swapping two numbers
Computing a
n
(a > 0, n a nonnegative integer)
Computing n!
Add n numbers
Decimal to Binary conversion
Finding Maximum/Minimum Element in a list
Multiply two n by n Matrices
Selection Sort
Bubble Sort
Sequential Search/Linear Search
Conversion of a 2D array into 1D array
Find the value of polynomial
13
Known examples of Brute Force

14. Department of Computer Science
Designing
Algorithms
using Brute
Force

15. Department of Computer Science
Problem:DesignanalgorithmthatExchangethe
valuesoftwovariablessayxandy.
Solution:
Whatisinput
Twonumberssayxandy.
Whatshouldbetheoutput
Interchangethevalueofxandy
Whichdesigningtechnique?
Brute-Force
Logic/Idea
Example-1

16. Department of Computer Science
Logic/Idea
Takeatemporaryvariabletemptoswapthe
numbers.
Thecontentsofthefirstvariableiscopiedintothe
tempvariable.
Then,thecontentsofsecondvariableiscopiedtothe
firstvariable.
Finally,thecontentsofthetempvariableiscopied
backtothesecondvariablewhichcompletesthe
swappingprocess.
Example-1
Doyouhaveanother
idea to solve
exchangeproblem?

17. Department of Computer Science
Doyouhaveanotherideatosolveexchange
problem?
Example-1

18. Department of Computer Science
Brute Force Example
InRSA(RonRivest,AdiShamir,andLeonard
Adleman)encryptionalgorithmweneedto
computea
n
modmfora>1andlargen.
Designanalgorithmthatcomputesa
n
usingBF
Solution:
Whatisinput
Twonumberssayxandn.
Whatshouldbetheoutput
Interchangethevalueofx
n
Whichdesigningtechnique?
Brute-Force
Logic/Idea
18
Example-2: Computinga
n

19. Department of Computer Science
Brute Force Example
Logic/Idea:x
n
=
Firstresponse:Multiply1byxntimeswhichis
the“BruteForce”approach.
19
Computinga
n
x×x×… … ×x
n times

20. Department of Computer Science
Induction Examples (4/4)
3.3 Mathematical Induction
Example 3: Factorial of positive integer
Wewanttocomputen!=
1 ×2 ×… … ×n
Is there a
connection?

21. Department of Computer Science
Problem:Designanalgorithmforfindingthe
binaryrepresentationofapositivedecimal
integer.
Solution:
Whatisinput
Positiveintegern.
Whatshouldbetheoutput
Binarystringb
kb
kb
k-1b
k-2…………..b
1b
0
Whichdesigningtechnique?
Brute-Force
Logic/Idea
Example 4: Decimal to Binary Conversion

22. Department of Computer Science
Problem:Designanalgorithmforfindingthe
binaryrepresentationofapositivedecimal
integer.
Representation
Example 4: Decimal to Binary Conversion

23. Department of Computer Science
Problem:Designanalgorithmthatcount
numbersofbitsinabinaryrepresentationofa
givennumbern.
Representation
Your Turn

24. Department of Computer Science
Brute Force ExamplesSome Examples

25. Department of Computer Science
Problem:Designanalgorithmthatfindthe
maximumnumberinagivenarrayofnelements.
Solution:
Whatisinput
AnarrayAofnnumberse.g.
Whatshouldbetheoutput
ThevalueoflargestelementinA.e.g.,10
Whichdesigningtechnique?
Brute-Force
Logic/Idea
41893710231
Example-6: Largest element

26. Department of Computer Science
Problem:Designanalgorithmthatfindmaximum
numberinagiven2Darrayofnxnelements.
Solution:
Your Turn

27. Department of Computer Science
Problem:Designanalgorithmthatmultiplytwomatrices
AandB
Solution:
Whatisinput
Two2DarrayAandBofcompatiblesize.
Whatshouldbetheoutput
AmatrixCsuchthatC=AB.
Whichdesigningtechnique?
Brute-force
Logic/Idea?
5599629173
Example-7

28. Department of Computer Science
Brute Force ExamplesExample 7: Matrix Multiplication

29. Department of Computer Science
Brute Force ExamplesExample 7: Matrix Multiplication

30. Department of Computer Science
Problem:Designanalgorithmthatfindakeyina
givenarrayofnelements.
Solution:
Whatisinput
AnarrayAofnnumbersandakeysayK
Whatshouldbetheoutput
Thelocationofkeyiffoundotherwisereturnfalse
Whichdesigningtechnique?
Brute-Force
Logic/Idea
Example-8: Searching

31. Department of Computer Science
Brute-Force Polynomial Evaluation
Problem:Designanalgorithmthatcomputethe
valueofpolynomial
p(x) = a
nx
n
+ a
n-1x
n-1
+… +a
1x
1
+ a
0
atapointx=x
0
Example-9

32. Department of Computer Science
Brute-Force Polynomial Evaluation
Problem:Findthevalueofpolynomial
p(x) = a
nx
n
+ a
n-1x
n-1
+… +a
1x
1
+ a
0
atapointx=x
0
Brute-force algorithm
p 0.0
for in downto0 do
power 1
for j 1 to ido //compute x
i
power power x
p p + a[i] power
returnp
Example-9

33. Department of Computer Science
Polynomial Evaluation: Improvement
We can do better by evaluating from right to left:
Better brute-force algorithm
pa[0]
power1
fori1 tondo
powerpowerx
pp+ a[i] power
returnp
Example-9

34. Department of Computer Science
Problem:Designanalgorithmconverta2Darray
into1Darray
Solution:
Whatisinput
An2D-arrayA[i][j].e.g.int[5][5]
Whatshouldbetheoutput
Youcouldpicturetheconversion
tothecorresponding1-Darray
likethis:
Example-10
:

35. Department of Computer Science
Whichdesigningtechnique?
Brute-Force
Logic/Idea
A1-Darraylookslikethis:int[5]:
Youcouldpicturetheconversiontothecorresponding1-Darray
likethis
Example-10
:

36. Department of Computer Science
Logic/Idea
Butanalternativewayofthinkingaboutitisto
picturetheoriginalarray,butre-labelled-likethis
Example-10
:
2-D array index [i][j] => 1-D array index [i*5 + j]

37. Department of Computer Science
Example-10
ALGORITHM Convert2d_into_1D(arr2D[i][j], arr1D [n*m])
Input:
OutPut:
for (i = 0; i < n; ++i)
{
for (j = 0; j < m; ++j)
{ // mapping 2D array to 1D array
arr1D[i * m + j] = arr2D[i][j];
}
}
2-D array index [i][j] => 1-D array index [i*5 + j]

38. Department of Computer Science
What is Brute Force?
Numerical problems, searching, sorting, etc.
Acceptable efficiency
Can be used for large problem instances
Combinatorial problems
Exhaustive search
Set of candidate solutions grows very fast
Used only for reduced size instances.
LetusapplyBruteforceapproachforsolving
sortingproblem.
38
Where to Apply?

39. Department of Computer Science
CONCLUSION

40. Department of Computer Science
What is Brute Force?
The(most)straightforwardapproachforsolving
aproblem.
“Brute Force” means “Just do it!”
Directly based on
The problem statement
The definitions involved
Generally,itinvolvediteratingthroughallpossible
solutionsuntilavalidoneisfound.
OtherNames
GenerateandTest
ExhaustiveSearch
40
What is Brute Force?

41. Department of Computer Science
What is Brute Force?
Strengths
Simplicity
Applicable to different kinds of problems
Weaknesses
(Very!) Low efficiency in some cases
Useful only for instances of (relatively) small size!
41
Strength and Weakness of Brute Force

42. Department of Computer Science 42
Algorithmsshouldbelearnatahigherlevel
withlinkagestopriorknowledgeandwitheach
othersoastoseehowonealgorithmisdifferent
fromtherestandwhatitdoesanddoesnot
perform,andwhy?
Inthisintegrativeapproachoflearningthe
initialinvestmentislargebutitisessentialfor
meaningfullearning
How we do it?

43. Department of Computer Science 43
Intuition First & Formalism Later
Common & Small Building Blocks
Design of Cruder versions providing a ladder
Visual patterns or puzzles
We do not tell the story of an algorithm?
The interesting story connects all characters and
provides a panoramic picture
Platforms for ComparisonsLadder
How we do it?