Introduction to information Security.ppt

qewqe wqe wqe qewq wq qe q qe wqewqe qe wq wqeqwewq ewq qe qewq wqe wqe qeqw qw eqw qe

1. 1
What is an algorithm?What is an algorithm?
An An algorithmalgorithm is a sequence of unambiguous instructions is a sequence of unambiguous instructions
for solving a problem, i.e., for obtaining a required for solving a problem, i.e., for obtaining a required
output for any legitimate input in a finite amount of output for any legitimate input in a finite amount of
time.time.
“computer”
problem
algorithm
input output

2. What is an algorithm?What is an algorithm?
•is any well-defined computational procedure is any well-defined computational procedure
that takes some value, or set of values, as input that takes some value, or set of values, as input
and produces some value, or set of values, as and produces some value, or set of values, as
output.output.
•is thus a sequence of computational steps that is thus a sequence of computational steps that
transform the input into the output.transform the input into the output.
•is a tool for solving a well - specified is a tool for solving a well - specified
computational problem.computational problem.
•Any special method of solving a certain kind of Any special method of solving a certain kind of
problem (Webster Dictionary)problem (Webster Dictionary)
2

3. What is a problem?What is a problem?

DefinitionDefinition
•A mapping/relation between a set of input instances A mapping/relation between a set of input instances
(domain) and an output set (range)(domain) and an output set (range)

Problem SpecificationProblem Specification
•Specify what a typical input instance isSpecify what a typical input instance is
•Specify what the output should be in terms of the input Specify what the output should be in terms of the input
instanceinstance

Example: SortingExample: Sorting
•Input: A sequence of N numbers aInput: A sequence of N numbers a
11…a…a
nn
•Output: the permutation (reordering) of the input Output: the permutation (reordering) of the input
sequence such that asequence such that a
11  a a
22  … …  a a
nn . .
3

4. Types of ProblemsTypes of Problems

Search: find X in the input satisfying property YSearch: find X in the input satisfying property Y

Structuring: Transform input X to satisfy property YStructuring: Transform input X to satisfy property Y

Construction: Build X satisfying YConstruction: Build X satisfying Y

Optimization: Find the best X satisfying property YOptimization: Find the best X satisfying property Y

Decision: Does X satisfy Y?Decision: Does X satisfy Y?
4

5. What do we analyze aboutWhat do we analyze about algorithms algorithms

CorrectnessCorrectness
•Does the input/output relation match algorithm requirement?Does the input/output relation match algorithm requirement?

Amount of work done Amount of work done (aka complexity) (aka complexity)
•Basic operations to do task Basic operations to do task

Amount of space usedAmount of space used
•Memory used Memory used
5

6. What do we analyze aboutWhat do we analyze about algorithms algorithms

Simplicity, claritySimplicity, clarity
•Verification and implementation. Verification and implementation.

OptimalityOptimality
•Is it impossible to do better? Is it impossible to do better?
6

7. 7
Euclid’s AlgorithmEuclid’s Algorithm
Problem: Find gcd(Problem: Find gcd(m,nm,n), the greatest common divisor of two ), the greatest common divisor of two
nonnegative, not both zero integers nonnegative, not both zero integers m m and and nn
Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ? Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ?
Euclid’s algorithm is based on repeated application of equalityEuclid’s algorithm is based on repeated application of equality
gcd(gcd(m,nm,n) = gcd() = gcd(n, m n, m mod mod nn))
until the second number becomes 0, which makes the problemuntil the second number becomes 0, which makes the problem
trivial.trivial.
Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12

8. 8
Two descriptions of Euclid’s algorithmTwo descriptions of Euclid’s algorithm
Step 1 If Step 1 If nn = 0, return = 0, return mm and stop; otherwise go to Step 2 and stop; otherwise go to Step 2
Step 2 Step 2 Divide Divide mm by by n n and assign the value fo the remainder toand assign the value fo the remainder to r r
Step 3 Assign the value of Step 3 Assign the value of n n to to mm and the value of and the value of rr to to n. n. Go toGo to
Step 1. Step 1.

whilewhile nn ≠ 0 ≠ 0 do do
r ← m r ← m mod mod nn
m← n m← n
n ← rn ← r
returnreturn mm

9. 9
Other methods for computing gcd(Other methods for computing gcd(m,nm,n))
Consecutive integer checking algorithmConsecutive integer checking algorithm
Step 1 Assign the value of min{Step 1 Assign the value of min{m,nm,n} to } to tt
Step 2 Step 2 Divide Divide mm by by t. t. If the remainder is 0, go to Step 3;If the remainder is 0, go to Step 3;
otherwise, go to Step 4 otherwise, go to Step 4
Step 3 Step 3 Divide Divide nn by by t. t. If the remainder is 0, return If the remainder is 0, return tt and stop; and stop;
otherwise, go to Step 4 otherwise, go to Step 4
Step 4 Decrease Step 4 Decrease t t by 1 and go to Step 2by 1 and go to Step 2

10. 10
Other methods for gcd(Other methods for gcd(m,nm,n) [cont.]) [cont.]
Middle-school procedureMiddle-school procedure
Step 1 Find the prime factorization of Step 1 Find the prime factorization of mm
Step 2 Find the prime factorization of Step 2 Find the prime factorization of nn
Step 3 Find all the common prime factorsStep 3 Find all the common prime factors
Step 4 Compute the product of all the common prime factorsStep 4 Compute the product of all the common prime factors
and return it as gcd and return it as gcd(m,n(m,n))
Is this an algorithm?Is this an algorithm?

11. 11
Sieve of EratosthenesSieve of Eratosthenes
Input: Input: Integer Integer n n ≥ 2≥ 2
Output: List of primes less than or equal to Output: List of primes less than or equal to nn
for for p p ← 2← 2 to to nn do do AA[[pp] ← ] ← pp
for for p p ← 2← 2 to to nn do do
if if AA[[pp] ]  0 // 0 //p p hasn’t been previously eliminated from the listhasn’t been previously eliminated from the list
j j ← ← pp** pp
while while j j ≤≤ n n dodo
AA[[jj] ] ← 0 ← 0 //mark element as eliminated//mark element as eliminated
j j ← ← jj + p+ p
Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

12. Algorithm design and analysis process.Algorithm design and analysis process.
12

13. 13
Two main issues related to algorithmsTwo main issues related to algorithms

How to design algorithmsHow to design algorithms

How to analyze algorithm efficiencyHow to analyze algorithm efficiency

14. Algorithm design techniques/strategiesAlgorithm design techniques/strategies

An algorithm design technique (or “strategy” or An algorithm design technique (or “strategy” or
“paradigm”) is a general approach to solving problems “paradigm”) is a general approach to solving problems
algorithmically that is applicable to a variety of problems algorithmically that is applicable to a variety of problems
from different areas of computing.from different areas of computing.
14

15. 15
Algorithm design techniques/strategiesAlgorithm design techniques/strategies

Brute forceBrute force

Divide and conquerDivide and conquer

Decrease and conquerDecrease and conquer

Transform and conquerTransform and conquer

Space and time tradeoffsSpace and time tradeoffs

Greedy approachGreedy approach

Dynamic programmingDynamic programming

Iterative improvementIterative improvement

Backtracking Backtracking

Branch and boundBranch and bound

16. Algorithm design techniques/strategiesAlgorithm design techniques/strategies

Brute force Brute force is a straightforward approach to solving a is a straightforward approach to solving a
problem, usually directly based on the problem statement problem, usually directly based on the problem statement
and definitions of the concepts involved.and definitions of the concepts involved.

The The decrease-and-conquer decrease-and-conquer technique is based on reducing technique is based on reducing
the size of the input instance.the size of the input instance.

Divide-and-ConquerDivide-and-Conquer
•A problem is divided into several subproblems of the same type, A problem is divided into several subproblems of the same type,
ideally of about equal size.ideally of about equal size.
•The subproblems are solved separately.The subproblems are solved separately.
•the solutions to the subproblems are combined to get a solution to the solutions to the subproblems are combined to get a solution to
the original problem.the original problem.
16

17. Algorithm design techniques/strategiesAlgorithm design techniques/strategies

Transform-and-ConquerTransform-and-Conquer: Firstly, the problem instance is : Firstly, the problem instance is
modified to be more Appropriate to solution. Then, in the modified to be more Appropriate to solution. Then, in the
second or conquering stage, it is solved.second or conquering stage, it is solved.

Dynamic programming Dynamic programming is a technique for solving problems is a technique for solving problems
with overlapping subproblems.with overlapping subproblems.

The The greedy approach greedy approach suggests constructing a solution suggests constructing a solution
through a sequence of steps until a complete solution to the through a sequence of steps until a complete solution to the
problem is reached.problem is reached.

Iterative improvement Iterative improvement starts with some feasible solution starts with some feasible solution
and proceeds to improve it by repeated applications of and proceeds to improve it by repeated applications of
some simple step.some simple step.
17

18. 18
Analysis of algorithmsAnalysis of algorithms

How good is the algorithm?How good is the algorithm?
•time efficiencytime efficiency
•space efficiencyspace efficiency

Does there exist a better algorithm?Does there exist a better algorithm?
•lower boundslower bounds
•optimalityoptimality

19. Properties as important as performanceProperties as important as performance

ModularityModularity

MaintainabilityMaintainability

FunctionalityFunctionality

Robustness and ReliabilityRobustness and Reliability

User-friendlinessUser-friendliness
19

20. 20
Important problem typesImportant problem types

SortingSorting
rearrange the items of a given list in non-decreasing order.rearrange the items of a given list in non-decreasing order.

SearchingSearching
deals with f inding a given value, called a search key, in a given setdeals with f inding a given value, called a search key, in a given set

string processingstring processing: Eg, string matching: Eg, string matching
graph problemsgraph problems
graph-traversal algorithmsgraph-traversal algorithms
shortest-path algorithmsshortest-path algorithms

21. Important problem typesImportant problem types

Combinatorial problemsCombinatorial problems: find a combinatorial object—: find a combinatorial object—
such as a permutation, a combination, or a subset—that such as a permutation, a combination, or a subset—that
satisfies certain constraints.satisfies certain constraints.

Geometric problemsGeometric problems: deal with geometric objects such as : deal with geometric objects such as
points, lines, and polygons.points, lines, and polygons.

Numerical problemsNumerical problems: involve mathematical objects of : involve mathematical objects of
continuous nature: continuous nature:
solving equations and systems of equations, solving equations and systems of equations,
computing definite integrals, computing definite integrals,
evaluating functions, and evaluating functions, and
…….. so on... so on.
21

22. 22
Fundamental data structuresFundamental data structures

listlist
•arrayarray
•linked listlinked list

23. Fundamental data structuresFundamental data structures

stackstack

queuequeue

priority queuepriority queue
23

24. Fundamental data structuresFundamental data structures

GraphGraph
Adjacency matrix Adjacency listAdjacency matrix Adjacency list
24

25. Fundamental data structuresFundamental data structures

TreeTree: is a connected acyclic graph : is a connected acyclic graph
•Rooted Trees: for every two vertices in a tree, there always exists Rooted Trees: for every two vertices in a tree, there always exists
exactly one simple path from one of these vertices to the other.exactly one simple path from one of these vertices to the other.

Set and dictionarySet and dictionary: an unordered collection (possibly : an unordered collection (possibly
empty) of distinct items called elements of the set. empty) of distinct items called elements of the set.
•The operations we need to perform for a set often are searching The operations we need to perform for a set often are searching
for a given item, adding a new item, and deleting an item from for a given item, adding a new item, and deleting an item from
the collection. the collection.
•A data structure that implements these three operations is called A data structure that implements these three operations is called
the dictionary.the dictionary.
25