Introduction to Algorithms

Revise S1 for algorithms.

Defines how input is mapped to output, where input and output are both representation of data. Has a well-defined procedure. A step-by-step method of solving a computational task. Algorithms are studied to easily understand and solve problems in the best way.

Computational task

A group of tasks with varying inputs.

Algorithm specification

Algorithms are specified in either:

• Flowcharts
  A diagram that shows a flow of control.
  • Terminals - rounded rectangles, represents start or end of the algorithm
  • Input/Output - parallelogram
  • Process/Stored data - rectangles
  • Decision - diamond
• Pseudocode
• Program listing

Algorithm types

Brute Force algorithm

An algorithm that tries all possible solutions and selects the optimal solution. Solution is optimal. Time of execution can be huge.

Greedy algorithm

An algorithm that makes the locally optimal choice at each stage with the hope of finding a global optimum.