Why are Algorithmic Design and Data Structure Techniques Important

Note: Before reading this article please review the concepts for Big O notation at FreeCodeCamp or GeeksforGeeks to better understand why programmers will use one algorithm or data structure over another. It is important to take into account constraints of an algorithm or data structure in terms of time complexity and space complexity so that a program can run smoothly. To further analyze algorithms, asymptotic notation is used. Ultimately, it is crucial to weigh the appropriate amount of space and memory that will be used for a program. 

Algorithmic Design Techniques

Algorithms are typically used to sort data and or to divide problems into smaller problems by storing and using intermediate results. This can be done through several techniques which could include: 

Divide and Conquer Method

"1. Divide the problem into a number of subproblems that are smaller instances of the same problem. 

2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases. 

3. Combine the solutions to the subproblems into the solution for the original problem."

(Cormen, T., & Balkcom, D., n.d.).

Please visit KhanAcademy to view the different time complexities of different divide and conquer methods (selection, insertion, merge, and quicksort).

Greedy Method

The Greedy method is an algorithmic paradigm that builds up a solution piece by piece. It always chooses the next piece that offers the most obvious and immediate benefit. This approach never reconsiders the choices taken previously and is mainly used to solve optimization problems (tutorialspoint, n.d.). An example of this method, would be the fractional knapsack problem. 

Fractional Knapsack Problem using the Greedy Method (GeeksforGeeks, 2021)

Dynamic Programming Method

Dynamic Programming is mainly optimization over plain recursion. If there is a recursive solution that has repeated calls for the same inputs, dynamic programming simply stores the results of the subproblems that way it does not need to be re-computed when needed later (GeeksforGeeks,2021).  This simple optimization reduces time complexities from exponential to polynomial. For instance, the simple recursive solution for Fibonacci Numbers has exponential time complexity, but if optimized by storing solutions of subproblems, the time complexity reduces to linear time complexity (GeeksforGeeks, 2021). 

Fibonacci Numbers: Exponential versus Linear Solutions (GeeksforGeeks, 2021)

Backtracking Method

The Backtracking method consists of building a set of all the solutions incrementally. Any solutions to fail to satisfy constraints will be removed. The Backtracking method is useful for the following kind of problems:

1. Decision Problems: searching for a feasible solution (GeeksforGeeks, 2021).
2. Optimization Problems: searching for the best solution (GeeksforGeeks, 2021).
3. Enumeration Problems: finding all feasible solutions (GeeksforGeeks, 2021).

To see example codes for the Backtracking method please visit Baeldung CS and GeeksforGeeks.

Branch and Bound Method

The Branch and Bound Method is an algorithm design paradigm which is generally used for solving combinatorial optimization problems (GeeksforGeeks, 2021). "These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case (GeeksforGeeks, 2021)".

Branch and Bound Solution to Knapsack Problem (GeeksforGeeks, 2021)

Data Structures

Data structures are a particular way of organizing data in a computer so that it can be used effectively. Please visit GeeksforGeeks to view a comprehensive list of data structures. Data structures inlude: Array, Linked List, Stack, Queue, Binary Tree, Binary Search Tree, Heap, Hashing, Graph, Matrix, and more. 

This article compares the time complexity of arrays and linked lists. 

References

GeeksforGeeks. (2021, December 24). Backtracking: Introduction. GeeksforGeeks. Retrieved March 6, 2022, from https://www.geeksforgeeks.org/backtracking-introduction/

GeeksforGeeks. (2021, November 15). Branch and bound algorithm. GeeksforGeeks. Retrieved March 6, 2022, from https://www.geeksforgeeks.org/branch-and-bound-algorithm/

GeeksforGeeks. (2021, July 31). Dynamic Programming. GeeksforGeeks. Retrieved March 6, 2022, from https://www.geeksforgeeks.org/dynamic-programming/

GeeksforGeeks. (2021, July 31). Greedy algorithms. GeeksforGeeks. Retrieved March 6, 2022, from https://www.geeksforgeeks.org/greedy-algorithms/

Cormen, T., & Balkcom, D. (n.d.). Divide and conquer algorithms . Khan Academy. Retrieved March 5, 2022, from https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms

tutorialspoint. (n.d.). Design and Analysis Greedy Method. tutorialspoint. Retrieved March 5, 2022, from https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_greedy_method.htm#:~:text=Greedy%20algorithms%20build%20a%20solution,used%20to%20solve%20optimization%20problems.