Algorithms are methods of analyzing problems in mathematics and engineering to determine the most efficient way of solving them.  The concept of algorithm started before Computers, but computers provide a convenient way to do as we can find the time to solve the problems and the space required.  We can also see if a problem has a solution and if it is practical to do so.  For example, a computer cannot be used to determine if a program in an endless loop will halt.  There are 10⁵⁰ possible combinations for moves on a chess board, and it would take several thousand years to analyze all of them at every turn.

We use pseudo code ot write programs.  Although a computer cannot understand this code, it can be easily converted into a programming language.  For this course the preferred language is Java. A knowledge of Java or C++ is not essential but very helpful.

Mathematical information required in Algorithms:
 Back to top
Sets:

Sets are a collection of elements that have something in common.  The four characteristics of sets that we consider are:
1.    Sets are well defined.  There is no ambiguity whether an element is or is not a member of a set.
2.    All elements are of the same type.
3.    There is no duplication.  Duplicate elements are ignored.
4.    There is no order in a set, that is changing the order does not effect a set.

Example:    {1, 2, 3, 1} is exactly the same as {2, 3, 1}
                  {g, o, o, d} is exactly the same as {d, o, g}
A set can have any number of elements.  An empty set shown {} has no elements in it not even 0.  A set can be finite or infinite shown as {1, 2, 3, .......}

If all the elements of one set, say S₁ are in another set, say S₂ then S₁ is said to be a subset of S₂ and S₂ is the superset of S₂.  A proper subset does not have all the elements of a superset.  For example if a set S has elements {1, 2, 3}, the the subsets are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.  All except the last {1, 2. 3} are proper subsets.  So if a set has n elements there are 2ⁿ subsets of which 2ⁿ - 1 are proper.
 Back to top
Sequence:

There can be duplication in a sequence, and the order of occurrence is important.  So here we can have permutations and combinations.  If a sequence consists of elements {1, 2, 3}, the permutations are {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, and {3,2,1}.  So a sequence of n elements will have n! (n factorial) permutations.  If not all elements are selected, we have combinations.  For instance take three elements at a time of a sequence {1, 2, 3. 4} will yield the combinations {1,2,3}, {1,2,4}, {1,3,4}, and {2,3,4}.  Here the formula is              n!
                                                                                                 k! (n-k)!    where n is the number of elements in the sequence (4 in this case), and k is the number of elements selected (3 in this case).  For more information, click below:

 Back to top
Probability:

Sample space is all possible outcomes of an experiment.  For instance, if you throw a die, the possible outcomes are 1, 2, 3, 4, 5, or 6.  Probability is the chance of a particular outcome occurring.  In this case the probability of getting a 1 is 1/6.  Probability is always equal to or greater than zero and also equal to or less than 1.  That is 0 <= Pr(event) <= 1.  The sum of all probability always equals 1.  So the probability of an event not occurring is 1 - Probability of it occurring.    Probability
Conditional probability occurs when one condition has to be satisfied before another one is.
 Back to top
Summation and Series:

Arithmetic Series:    The sum of consecutive integers = n(n + 1)/2.
Polynomial Series:   The sum of squares = (2n³ + 3n² + n)/6  For any other power it is approximately = n^{(k + 1)}/(k + 1) where k is the power.
Powers of 2:            The sum of 2ⁱ = 2^{(k + 1)} - 1
Geometric Series:     The sum of a rⁱ = a [r^{(k + 1)} -1]/(r - 1)
Harmonic Series:      The sum of 1/i is approximately ln(n) + 0.577 where ln is log₂
Arithmetic-Geometric Series:    The sum of  i 2i = (k - 1)2^{(k + 1)} + 2
Fibonacci Numbers:    The Fibonacci sequence is defined recursively as :
                                    F_n = F_{n - 1} + F_{n - 2}     for n >= 2 where F₀ = 0 and F₁ = 1
 Back to the top

Analyzing Algorithms and Problems:

Algorithms are analyzed to improve them.  Seceral criteria are used.  Among them are:

1.    Correctness:    We need a precise statement about the inputs (preconditions) and the expected results for each input (postconditions).  Their relationships shpould be proved, so that if the preconditions are satisfied, the postconditions will be true.  If the program is large, it is broken into smaller modules.  So the algorithms must be writteen such that the individual modules are independent and can be verified separately.

2.    Amount of work done:    The method should be independent of the computers and the programming languages.  Comparing two or more algorithms for the same problem, and count the number of instructions for each.  We do average and worst case analysis.

3.    Space Usage:    A program will reqiure storage space for instructions, constants, and variables, for manupilating data, and for storing information to carry out computations.

4.    Simplicity:    The simplest and most straightforward way may not be the most efficient.  However, simplicity makes verification and modification easier.

5.    Optami;lity:    Establish a lower bound on thre number of operations needed to solve a problem.