… and now for… : … and now for… Sequences
Sequences : Sequences Sequences represent ordered lists of elements.
A sequence is defined as a function from a subset of N to a set S. We use the notation an to denote the image of the integer n. We call an a term of the sequence.
Example:
subset of N: 1 2 3 4 5 …
Sequences : Sequences We use the notation {an} to describe a sequence.
Important: Do not confuse this with the {} used in set notation.
It is convenient to describe a sequence with a formula.
For example, the sequence on the previous slide can be specified as {an}, where an = 2n.
The Formula Game : The Formula Game 1, 3, 5, 7, 9, … an = 2n - 1 -1, 1, -1, 1, -1, … an = (-1)n 2, 5, 10, 17, 26, … an = n2 + 1 0.25, 0.5, 0.75, 1, 1.25 … an = 0.25n 3, 9, 27, 81, 243, … an = 3n What are the formulas that describe the following sequences a1, a2, a3, … ?
Strings : Strings Finite sequences are also called strings, denoted by a1a2a3…an.
The length of a string S is the number of terms that it consists of.
The empty string contains no terms at all. It has length zero.
Summations : Summations It represents the sum am + am+1 + am+2 + … + an.
The variable j is called the index of summation, running from its lower limit m to its upper limit n. We could as well have used any other letter to denote this index.
Summations : Summations It is 1 + 2 + 3 + 4 + 5 + 6 = 21. It is so much work to calculate this… How can we express the sum of the first 1000 terms of the sequence {an} with an=n2 for n = 1, 2, 3, … ?
Summations : Summations It is said that Carl Friedrich Gauss came up with the following formula: When you have such a formula, the result of any summation can be calculated much more easily, for example:
Double Summations : Double Summations Corresponding to nested loops in C or Java, there is also double (or triple etc.) summation:
Example:
Double Summations : Double Summations Table 2 in
4th Edition: Section 1.7
5th Edition: Section 3.2
6th Edition: Section 2.4
contains some very useful formulas for calculating sums.
Exercises 15 and 17 make a nice homework.
Enough Mathematical Appetizers! : Enough Mathematical Appetizers! Let us look at something more interesting:
Algorithms
Algorithms : Algorithms What is an algorithm?
An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.
This is a rather vague definition. You will get to know a more precise and mathematically useful definition when you attend CS420 or CS620.
But this one is good enough for now…
Algorithms : Algorithms Properties of algorithms:
Input from a specified set,
Output from a specified set (solution),
Definiteness of every step in the computation,
Correctness of output for every possible input,
Finiteness of the number of calculation steps,
Effectiveness of each calculation step and
Generality for a class of problems.
Algorithm Examples : Algorithm Examples We will use a pseudocode to specify algorithms, which slightly reminds us of Basic and Pascal.
Example: an algorithm that finds the maximum element in a finite sequence
procedure max(a1, a2, …, an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
{max is the largest element}
Algorithm Examples : Algorithm Examples Another example: a linear search algorithm, that is, an algorithm that linearly searches a sequence for a particular element.
procedure linear_search(x: integer; a1, a2, …, an: integers)
i := 1
while (i n and x ai)
i := i + 1
if i n then location := i
else location := 0
{location is the subscript of the term that equals x, or is zero if x is not found}
Algorithm Examples : Algorithm Examples If the terms in a sequence are ordered, a binary search algorithm is more efficient than linear search.
The binary search algorithm iteratively restricts the relevant search interval until it closes in on the position of the element to be located.
Algorithm Examples : Algorithm Examples a c d f g h j l m o p r s u v x z binary search for the letter ‘j’ search interval
Algorithm Examples : Algorithm Examples a c d f g h j l m o p r s u v x z binary search for the letter ‘j’ search interval
Algorithm Examples : Algorithm Examples a c d f g h j l m o p r s u v x z binary search for the letter ‘j’ search interval
Algorithm Examples : Algorithm Examples a c d f g h j l m o p r s u v x z binary search for the letter ‘j’ search interval
Algorithm Examples : Algorithm Examples a c d f g h j l m o p r s u v x z binary search for the letter ‘j’ search interval found !
Algorithm Examples : Algorithm Examples procedure binary_search(x: integer; a1, a2, …, an: integers)
i := 1 {i is left endpoint of search interval}
j := n {j is right endpoint of search interval}
while (i < j)
begin
m := (i + j)/2
if x > am then i := m + 1
else j := m
end
if x = ai then location := i
else location := 0
{location is the subscript of the term that equals x, or is zero if x is not found}
Algorithm Examples : Algorithm Examples Obviously, on sorted sequences, binary search is more efficient than linear search.
How can we analyze the efficiency of algorithms?
We can measure the
time (number of elementary computations) and
space (number of memory cells) that the algorithm requires.
These measures are called computational complexity and space complexity, respectively.
Complexity : Complexity What is the time complexity of the linear search algorithm?
We will determine the worst-case number of comparisons as a function of the number n of terms in the sequence.
The worst case for the linear algorithm occurs when the element to be located is not included in the sequence.
In that case, every item in the sequence is compared to the element to be located.
Complexity : Complexity For n elements, the loop
while (i n and x ai) i := i + 1
is processed n times, requiring 2n comparisons.
When it is entered for the (n+1)th time, only the comparison i n is executed and terminates the loop.
Finally, the comparison if i n then location := i is executed, so all in all we have a worst-case time complexity of 2n + 2.