Scribd
Upload
5 views7 pages

Discrete Math: Algorithms Overview

This document discusses algorithms and their analysis. It begins by defining algorithms and their key characteristics, such as precision, determinism, finiteness, correctness, inputs, outputs and generality. Examples of algorithms for tasks like searching, sorting and shuffling are provided. Methods for analyzing algorithms' time and space complexity in best, worst and average cases are covered. The document also introduces randomized algorithms that incorporate randomness.

Uploaded by

陳展揚
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
5 views7 pages

Discrete Math: Algorithms Overview

This document discusses algorithms and their analysis. It begins by defining algorithms and their key characteristics, such as precision, determinism, finiteness, correctness, inputs, outputs and generality. Examples of algorithms for tasks like searching, sorting and shuffling are provided. Methods for analyzing algorithms' time and space complexity in best, worst and average cases are covered. The document also introduces randomized algorithms that incorporate randomness.

Uploaded by

陳展揚
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Chapter 4 Algorithms

4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
4.4 Recursive Algorithms

Spring'16 TWHou

Discrete Math 7th


ed.

4.1 Introduction
An algorithm is a finite set of instructions having the
following characteristics:
[Link] steps are precisely stated.
Determinism (Uniqueness) The intermediate results of
each step of execution are uniquely defined and depend
only on the inputs and the results of the preceding steps.
Finitness. The algorithm stops after finitely many
instructions have been executed.
Correctness: The output produced by the algorithm is
correct; that is, the algorithm correctly solves the problem.
Input. The algorithm receives input.
Output. The algorithm produces output.
Generality. The algorithm applies to a set of inputs.
Spring'16 TWHou

Discrete Math 7th


ed.

Trace of an algorithm
pseudocode

Spring'16 TWHou

Discrete Math 7th


ed.

Notation for Algorithms


Algorithm 4.1.1 Finding the maximum of three numbers
Algorithm 4.1.2 Finding the maximum value in a finite
sequence (while loop)

Spring'16 TWHou

Discrete Math 7th


ed.

4.2 Examples of Algorithms


Searching
Algorithm 4.2.1 Text Search
Searches for an occurrence of the pattern p in text t.
It returns the smallest index I such that p occurs in t
starting at index i. If p odes not occurs in t, it returns
0.
Example 4.2.2
Sorting
Algorithm 4.2.3 Insertion Sort
Sorts the sequence s1, s2,,sn in non-decreasing
order.
Spring'16 TWHou

Discrete Math 7th


ed.

Time and Space for Algorithms


Best case time
insertion sort sort sort
(nondecreasing) ,
Worst case time
insertion sort sort sort
(decreasing) ,

Spring'16 TWHou

Discrete Math 7th


ed.

Randomized Algorithm

Algorithm that make random decisions, thereby violating the


requirement of determinism.
Operating systems (a program that never terminates) are rarely
deterministic
Practical problems are difficult to be solved efficiently and
compromises either in generality or correctness are necessary.
A randomized algorithm does not require that the intermediate results
of each step of execution be uniquely defined and depend only on the
inputs and results of the preceding steps.
rand(i,j)
Algorithm 4.2.4 Shuffle
Shuffles the values in the sequence a1, a2, , an.

Spring'16 TWHou

Discrete Math 7th


ed.

You might also like