Algorithms Fundamentals

10 Questions

What is the primary characteristic of a recursive algorithm?

Breaking down a problem into smaller sub-problems, solving each recursively until the solution is found.

What is the main goal of a greedy algorithm?

To make the optimal choice at each step, hoping to find a global optimum solution.

What is the primary advantage of dynamic programming algorithms?

Solving each sub-problem only once and storing the solutions to avoid redundant computation.

What is the purpose of time complexity analysis in algorithm design?

To measure the amount of time an algorithm takes to complete, usually in terms of the number of operations performed.

What is the main difference between the divide and conquer algorithm design technique and the divide and conquer algorithm type?

The divide and conquer algorithm design technique is a general approach to solving problems, while the divide and conquer algorithm type is a specific type of algorithm that breaks down a problem into smaller sub-problems and solves each recursively.

What is the purpose of backtracking in algorithm design?

To try a solution and if it fails, backtrack and try another solution.

What is the significance of Big O notation in algorithm analysis?

It provides a way of expressing the time or space complexity of an algorithm, usually in terms of the number of operations performed or the amount of memory used.

What is the primary difference between a brute force algorithm and a dynamic programming algorithm?

A brute force algorithm tries all possible solutions and chooses the best one, while a dynamic programming algorithm breaks down a problem into smaller sub-problems, solving each only once and storing the solutions to avoid redundant computation.

What is the main application of graph algorithms?

Solving problems related to graph data structures, such as finding shortest paths or traversing graphs.

What is the primary purpose of cryptography algorithms?

To provide secure data transmission and protection by encrypting and decrypting data.

Study Notes

Algorithms

Definition

A set of instructions to solve a specific problem or perform a particular task
A well-defined procedure that takes some input and produces a corresponding output

Types of Algorithms

Recursive Algorithms: break down a problem into smaller sub-problems, solving each recursively until the solution is found
Dynamic Programming Algorithms: break down a problem into smaller sub-problems, solving each only once and storing the solutions to sub-problems to avoid redundant computation
Greedy Algorithms: make the optimal choice at each step, hoping to find a global optimum solution
Divide and Conquer Algorithms: break down a problem into smaller sub-problems, solving each recursively and combining the solutions to solve the original problem

Algorithm Design Techniques

Brute Force: try all possible solutions and choose the best one
Divide and Conquer: break down a problem into smaller sub-problems and solve each recursively
Dynamic Programming: break down a problem into smaller sub-problems, solving each only once and storing the solutions to sub-problems
Backtracking: try a solution and if it fails, backtrack and try another solution

Algorithm Analysis

Time Complexity: the amount of time an algorithm takes to complete, usually measured in terms of the number of operations performed
Space Complexity: the amount of memory an algorithm uses, usually measured in terms of the number of bytes required
Big O Notation: a way of expressing the time or space complexity of an algorithm, usually in terms of the number of operations performed or the amount of memory used

Famous Algorithms

Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort
Searching Algorithms: Linear Search, Binary Search
Graph Algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's Algorithm
Cryptography Algorithms: RSA, AES