Introduction to Algorithms

Algorithms

• An algorithm is a well-defined computational procedure
• Algorithms take a value or set of values as input
• Algorithms produce a value or set of values as output.
• An algorithm involves getting the smallest value from the input, removing it and outputting it; this is repeated until there are no items left in the input

Properties of an Algorithm

• Correctness is a property
• Algorithms must be unambiguous
• Should give the correct solution for all cases
• Algorithms should be simple
• Algorithms must terminate

Applications of Algorithms

• Data retrieval is one application
• Network routing is another
• Sorting is an application
• Searching is also an application
• Finding the shortest paths in a graph can be done by algorithms

Pseudocode

• It is a method of writing down algorithms
• Pseudocode is easy to read and understand
• It is like other programming languages
• Pseudocode is a more expressive method
• Pseudocode does not concern itself with software engineering techniques

Pseudocode Conventions

• Written in English
• Uses indentation
• Each instruction is on a separate line
• Uses looping and conditional constructs
• "//" indicates a comment line
• "=" indicates assignment
• Array elements are accessed by specifying the array name followed by the index in square brackets
• The notation ".." is used to indicate a range of values within the array
• A[1..i] indicates the subarray A consisting of elements A[1], A[2],.., A[i]

Analysis of Algorithms

• The basic idea is to predict resource usage
• Resources to predict include memory, logic gates, and computational time
• Necessary to compare algorithms and predict run time growth.

Worst, Best, and Average Cases

• Running time depends on chosen instance characteristics
• Best case: minimum number of steps taken on any instance of size n
• Worst case: maximum number of steps taken on any instance of size n
• Average case: an average number of steps taken on any instance of size n

Analysis Methods

• Operation Count Methods exist
• Step Count Method (RAM Model) exists
• Exact Analysis can be used
• Asymptotic Notations are used

Operation Count

• Methods are for time complexity analysis
• Involves selecting one or more operations such as add, multiply, and compare
• The time spent on chosen operations, but not all, is considered

Step Count (RAM Model)

• Assumes a generic one processor
• Instructions execute one after another, without concurrent operations
• +, -, and = take exactly one step
• Each memory access takes exactly one step
• Running Time = Sum of the steps

Calculating Steps Example 1

• Example 1:
• n = 100, number of steps =1
• n = n + 100, number of steps = 2
• print n, number of steps = 1
• total number of steps = 4

Calculating Steps Example 2

• Example 2:
• sum = 0, number of steps = 1 assignment
• for i = 1 to n, number of steps = n+1 assignments, n+1 comparisons, and n additions
• sum = sum + A[i], number of steps = n assignments, n additions, and n memory accesses
• total steps = 6n+3

Question 1 Example

• If using a RAM model, to display the numbers from 1 to 10:
• i = 1 -> 1 step
• While i <= 10 -> 11 steps
• print i -> 10 steps
• i = i + 1 -> (10 + 10) = 20 steps
• Total steps = 42

Question 2 Example

• Using RAM model analysis, find out the number of steps needed to display the numbers from 10 to 20
• i = 10 -> 1 step
• While i <= 20 -> Hint: (20 - 10 + 2) = 12 steps
• print i -> 11 steps
• i = i + 1 -> 11 + 11 = 22 steps
• Total steps = 46

Question 3 Example

• If using RAM model analysis, to display the even numbers from 10 to 20:
• for i = 10 to 20 -> (12 + 12 + 11) steps = 35 steps
• if i % 2 == 0 -> 2 * 11 = 22 steps
• print i -> 6 steps Total steps = 63