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.