Chapter 10. Datatypes and Structures Flashcards
What is an algorithm?
- A step-by-step procedure or formula for solving a problem.
- Consists of a finite set of instructions that produce a desired outcome.
What are the characteristics of a good algorithm?
- Clear and unambiguous.
- Finite: Has a clear end point.
- Effective: Produces the correct result.
- Efficient: Uses minimal resources.
What are flowcharts used for in algorithm design?
- Visual representations of the steps in an algorithm.
- Use symbols like ovals for start/end, rectangles for processes, and diamonds for decision points.
What are pseudocode and its purpose?
- A high-level description of an algorithm using structured, natural language.
- Bridges the gap between human language and programming code.
What are the basic control structures in algorithms?
- Sequence: A set of instructions executed in order.
- Selection: Decision-making (if-else statements).
- Iteration: Repeating a set of instructions (loops).
What is the difference between linear search and binary search?
- Linear search: Checks each element one by one.
- Binary search: Divides the search interval in half, requires a sorted list.
What is a recursive algorithm?
- An algorithm that calls itself to solve smaller instances of the same problem.
- Example: Factorial calculation, Fibonacci series.
What are the advantages of recursive algorithms?
- Simplifies the code for problems that have a recursive nature.
- Reduces the need for complex loops and conditionals.
What are the disadvantages of recursive algorithms?
- Can lead to high memory usage (stack overflow) if not properly managed.
- Often less efficient than iterative solutions.
What is the purpose of sorting algorithms?
- To arrange data in a specific order (ascending or descending).
- Examples: Bubble sort, quicksort, merge sort.
What is the difference between bubble sort and quicksort?
- Bubble sort: Simple but inefficient, compares adjacent elements.
- Quicksort: More efficient, uses a divide-and-conquer approach.
What is a greedy algorithm?
- An algorithm that makes the best choice at each step with the hope of finding the global optimum.
- Example: Dijkstra’s algorithm for shortest path.
What is dynamic programming?
- A method for solving complex problems by breaking them down into simpler subproblems.
- Stores the results of subproblems to avoid redundant computations.
What is the difference between breadth-first search (BFS) and depth-first search (DFS)?
- BFS: Explores all neighbors at the current depth before moving to the next level.
- DFS: Explores as far as possible along each branch before backtracking.
What is a heuristic in problem-solving?
- An approach to finding a satisfactory solution where finding an optimal solution is impractical.
- Often used in artificial intelligence and optimization problems.
What is a backtracking algorithm?
- An algorithm that tries to build a solution incrementally, removing solutions that fail to satisfy the problem constraints.
- Example: Solving a maze or Sudoku puzzle.
What is the role of a decision table in problem-solving?
- A tabular method for representing and analyzing decision rules.
- Helps in systematic identification of different possible actions.
What is the difference between a deterministic and a non-deterministic algorithm?
- Deterministic: Produces the same output for a given input every time.
- Non-deterministic: May produce different outputs for the same input on different runs.
What is a divide-and-conquer algorithm?
- An algorithm that divides the problem into smaller subproblems, solves them independently, and combines their solutions.
- Example: Merge sort, quicksort.
What are the typical steps in algorithm design?
- Understand the problem.
- Plan the algorithm (pseudocode or flowchart).
- Implement the algorithm.
- Test and debug the algorithm.
