Algorithms and Programs
Algorithms and Programs
Basic Concepts
-
An algorithm is a set of step-by-step procedures, or a set of rules to follow, for completing a specific task or solving a particular problem.
-
A program is a detailed plan of action, or sequence of instructions, for a computer. Programs implement the logic of one or multiple algorithms to function.
-
Algorithms can be expressed in many forms, including flowcharts, pseudo code and programming languages.
Types of Algorithms
-
Sequential Algorithm: This follow a linear step-by-step approach. Each step has to be completed before moving onto the next.
-
Recursive Algorithm: This algorithm calls itself with a smaller input every time to solve a larger problem incrementally.
-
Divide and Conquer Algorithm: These break a single problem into smaller sub-problems, solve each one individually, and combine their solutions to solve the original problem.
-
Greedy algorithm: These make the optimal choice at each decision point with the hope that these local choices will lead to a global optimum.
-
Dynamic Programming Algorithm: Strategy of solving complex problems by breaking it down into simpler sub-problems in a recursive manner.
Complexity of Algorithms
-
The time complexity of an algorithm quantifies the amount of time the algorithm takes to run as a function of the size of the input to the program.
-
The space complexity of an algorithm quantifies the amount of space or memory the algorithm takes to run as a function of the size of the input.
-
Commonly used notations to define Time complexity are:
- Big O Notation: It provides an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large.
- Omega Notation: It provides a lower bound of the complexity in the best case.
- Theta Notation: It provides both upper and lower bounds of the complexity.
Testing Programs
-
Syntax Errors: These errors occur when the rules of the programming language are not followed.
-
Logic Errors: Also called semantic errors, these occur when an algorithm doesn’t do what the programmer intended.
-
Runtime Errors: These errors occur while the program is being executed.
-
Test Data: Used to check whether a program works correctly and can handle different types of input.
- Normal Data: Data that is within the parameters of what the program is expecting.
- Boundary Data: Data at the extreme ends of what the program should be able to handle.
- Erroneous Data: Data that the program should not accept.
Writing Efficient Programs
-
Maintainability: Programs should be written in a way that allows them to be updated easily.
-
Readability: The code should be written in a clean, organized and understandable manner.
-
Robustness: The program should handle incorrect inputs or unexpected user actions gracefully.
-
Portability: The program should run on different types of computers or operating systems with minimal modifications.
-
Efficiency: The program should use computer resources sparingly to accomplish its tasks. This means it should have minimal time and space complexity.