Understanding Algorithm Properties and Applications

• Algorithm: a finite sequence of precise instructions for performing a computation or solving a problem.

Applications of Algorithms:

• Used in number theory to make message text.
• Generate pseudorandom numbers.
• Assign memory locations to computer files.
• Internet security.

Example Algorithm: Finding the Maximum Value in a Finite Sequence

• Start by setting a temporary maximum equal to the first integer in the sequence.

• Compare the next integer in the sequence to the temporary maximum. If the next integer is larger, set it as the new temporary maximum.

• Repeat the comparison step for all remaining integers in the sequence.

• Once all integers have been checked, the temporary maximum holds the overall maximum integer in the sequence.

• Pseudocode: Is an intermediate step between an English language description of an algorithm and the implementation of this algorithm in a programming language

Properties of an Algorithm:

• Input: Algorithms must have values from a specified set.
• Output: For each set of input values, an algorithm produces output values from a specified set which are the solution to the problem.
• Definiteness: Each step must be defined precisely.
• Correctness: It should produce the correct output values for each set of input values.
• Finiteness: It should produce the desired output after a finite number of steps for any input in the set.
• Effectiveness: Each step must be performed exactly in a finite amount of time.
• Generality: The procedure should be applicable for all problems of the desired form, not just a particular set of input values.

Searching Algorithms:

• Problem: locate an element x in a list or determine that it is not in the list.

Linear Search:

• A simple search algorithm that sequentially checks each element in the list until a match is found or the entire list has been searched.

Binary Search:

• Requires the list to be sorted in increasing order.
• Works by comparing the target element to the middle element of the list.
• If the middle element is larger, the search continues in first half of the list.
• Otherwise it continues in the second half of the list
• This process repeats until the element is found or the search area is exhausted.

Complexity of Algorithms:

• Time Complexity: Time required to solve a problem of a specified size expressed in terms of the number of operations used by the algorithm.
• Worse case analysis: This refers to the largest number of operations needed to solve the given solution using this algorithm.
• Average case analysis: This refers to the average number of operations used to solve the problem over all inputs.

Time Complexities:

• Finding the Maximum Element in a Finite Sequence: 3n-1

• The linear Search Algorithm: 3n+5

• The Binary Search Algorithm: 4 log₂ n + 4

• When finding x in the list of n elements, the two algorithms use 3n + 5 and 4log₂ n + 4 time (operations) respectively.

• 3n + 5 grows faster than 4log₂ n + 4 when n becomes larger, therefore 3n + 5 is O(n) and 4log₂ n + 4 is O(log₂ n)

Order of Growth:

• How the time of execution depends on the length of the input.
• Using silicon computer, no matter how fast CPU will be you can never solve the problem whose running time is exponential.
• Space complexity: the computer memory required to solve a problem of a specified size

Asymptotic Notations: O-notation

• A function f(n) is said to be O(g(n)) if there exists some constant C₀ > 0 and n₀ ≥ 0 such that f(n) ≤ C₀g(n) for all n > n₀

Definition of Divisibility:

• Given integers a and b (where a ≠ 0), 'a divides b' if there exists an integer c such that b = ac.
• a is a factor of b, and b is a multiple of a. The notation a|b denotes that a divides b.

Basic Properties of Divisibility:

• If a|b and a|c, then a|(b + c).
• If a|b, then a|bc for all integers c.
• If a|b and b|c, then a|c.

Prime and Composite Integers:

• A positive integer p greater than 1 is prime if its only positive factors are 1 and p.
• A positive integer greater than 1 that is not prime is called composite.
• Every positive integer can be written uniquely as the product of primes in increasing size.

Division Algorithm:

• Given an integer a and a positive integer d, there exist unique integers q (quotient) and r (remainder) such that a = dq + r, where 0 ≤ r < d.

Greatest Common Divisor (GCD):

• The largest integer d such that d|a and d|b, denoted by gcd(a, b).

Relatively Prime:

• Integers a and b are relatively prime if gcd(a, b) = 1.

Least Common Multiple (LCM):

• The smallest positive integer that is divisible by both a and b, denoted by lcm(a, b).

Modulo Operator:

• Denoted a mod m, represents the non-negative remainder when a is divided by m.

Congruence Modulo m:

• If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a-b.
• Notation: a ≡ b (mod m).