Questions and Answers
What is the primary characteristic of a dynamic programming algorithm?
It breaks down a complex problem into smaller subproblems and solves each subproblem only once.
What type of algorithm solves a problem by breaking it down into smaller instances of the same problem?
Recursive algorithm
What is the purpose of Big O Notation in algorithm analysis?
To provide an upper bound on the number of steps an algorithm takes
What is the name of the algorithm design technique that breaks down a problem into smaller subproblems and solves each subproblem recursively?
Signup and view all the answers
What is the name of the sorting algorithm that compares adjacent elements and swaps them if they are in the wrong order?
Signup and view all the answers
What is the application of algorithms in which they are used to secure data and ensure confidentiality?
Signup and view all the answers
What type of algorithm makes the locally optimal choice at each step, hoping to find a global optimum?
Signup and view all the answers
What is the type of complexity that measures the amount of memory an algorithm uses?
Signup and view all the answers
Study Notes
Algorithms
Definition
 An algorithm is a welldefined procedure that takes some input and produces a corresponding output
 It is a stepbystep procedure to solve a computational problem
Types of Algorithms
 Recursive Algorithm: solves a problem by breaking it down into smaller instances of the same problem
 Dynamic Programming Algorithm: breaks down a complex problem into smaller subproblems and solves each subproblem only once
 Backtracking Algorithm: finds a solution by recursively exploring all possible solutions
 Greedy Algorithm: makes the locally optimal choice at each step, hoping to find a global optimum
Algorithm Analysis

Time Complexity: measures the amount of time an algorithm takes to complete
 Big O Notation: upper bound on the number of steps an algorithm takes
 Omega Notation: lower bound on the number of steps an algorithm takes
 Theta Notation: exact bound on the number of steps an algorithm takes

Space Complexity: measures the amount of memory an algorithm uses
 Auxiliary Space Complexity: measures the amount of extra memory used by an algorithm
Algorithm Design Techniques
 Divide and Conquer: breaks down a problem into smaller subproblems and solves each subproblem recursively
 Dynamic Programming: breaks down a complex problem into smaller subproblems and solves each subproblem only once
 Greedy Method: makes the locally optimal choice at each step, hoping to find a global optimum
Famous Algorithms

Sorting Algorithms:
 Bubble Sort: compares adjacent elements and swaps them if they are in the wrong order
 Selection Sort: selects the smallest element from the unsorted portion of the array and swaps it with the first element
 Merge Sort: divides the array into smaller subarrays and merges them in sorted order

Searching Algorithms:
 Linear Search: checks each element of the array in sequence until a match is found
 Binary Search: searches for an element in a sorted array by repeatedly dividing the search interval in half
Algorithm Applications
 Cryptography: uses algorithms to secure data and ensure confidentiality
 Data Compression: uses algorithms to reduce the size of data
 Machine Learning: uses algorithms to make predictions and classify data
 Network Flow: uses algorithms to optimize the flow of data through a network
Algorithms
Definition
 An algorithm is a welldefined procedure that takes input and produces a corresponding output.
 It is a stepbystep procedure to solve a computational problem.
Types of Algorithms
 Recursive Algorithm: breaks down a problem into smaller instances of the same problem to solve it.
 Dynamic Programming Algorithm: breaks down a complex problem into smaller subproblems, solves each subproblem only once, and stores the solutions to subproblems to avoid redundant computation.
 Backtracking Algorithm: finds a solution by recursively exploring all possible solutions.
 Greedy Algorithm: makes the locally optimal choice at each step, hoping to find a global optimum.
Algorithm Analysis
Time Complexity
 Measures the amount of time an algorithm takes to complete.
 Big O Notation: represents the upper bound on the number of steps an algorithm takes.
 Omega Notation: represents the lower bound on the number of steps an algorithm takes.
 Theta Notation: represents the exact bound on the number of steps an algorithm takes.
Space Complexity
 Measures the amount of memory an algorithm uses.
 Auxiliary Space Complexity: measures the amount of extra memory used by an algorithm.
Algorithm Design Techniques
 Divide and Conquer: breaks down a problem into smaller subproblems and solves each subproblem recursively.
 Dynamic Programming: breaks down a complex problem into smaller subproblems, solves each subproblem only once, and stores the solutions to subproblems to avoid redundant computation.
 Greedy Method: makes the locally optimal choice at each step, hoping to find a global optimum.
Famous Algorithms
Sorting Algorithms
 Bubble Sort: compares adjacent elements and swaps them if they are in the wrong order.
 Selection Sort: selects the smallest element from the unsorted portion of the array and swaps it with the first element.
 Merge Sort: divides the array into smaller subarrays and merges them in sorted order.
Searching Algorithms
 Linear Search: checks each element of the array in sequence until a match is found.
 Binary Search: searches for an element in a sorted array by repeatedly dividing the search interval in half.
Algorithm Applications
 Cryptography: uses algorithms to secure data and ensure confidentiality.
 Data Compression: uses algorithms to reduce the size of data.
 Machine Learning: uses algorithms to make predictions and classify data.
 Network Flow: uses algorithms to optimize the flow of data through a network.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Learn about the definition of algorithms, and types of algorithms including recursive, dynamic programming, and backtracking algorithms.