Scribd
Upload
6 views

Chapter nine, algorithm and problem solving notes

Chapter 9 discusses algorithms and problem-solving techniques, defining an algorithm as a step-by-step procedure to solve problems. It highlights characteristics of good algorithms, various design techniques, common algorithm types, and the importance of computational thinking in breaking down problems. The chapter also includes practice questions to reinforce understanding of these concepts.

Uploaded by

NotFeris Xd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views

Chapter nine, algorithm and problem solving notes

Chapter 9 discusses algorithms and problem-solving techniques, defining an algorithm as a step-by-step procedure to solve problems. It highlights characteristics of good algorithms, various design techniques, common algorithm types, and the importance of computational thinking in breaking down problems. The chapter also includes practice questions to reinforce understanding of these concepts.

Uploaded by

NotFeris Xd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

📌 Chapter 9: Algorithm and Problem-

Solving
1⃣ Key Concepts & Definitions
🔹 What is an Algorithm?

An algorithm is a step-by-step procedure or set of instructions to solve a problem.

🔹 Characteristics of a Good Algorithm

A good algorithm should be:


✅ Correct – Produces the right output for all inputs
✅ Efficient – Uses minimum time and memory
✅ Readable – Easy to understand and modify
✅ Finite – Has a definite number of steps

🔹 Problem-Solving Techniques

1. Decomposition – Breaking a problem into smaller, manageable parts.


2. Abstraction – Ignoring unnecessary details and focusing on the main idea.
3. Pattern Recognition – Identifying patterns to solve problems efficiently.

2⃣ Additional Notes on Algorithm & Problem-Solving


📌 Algorithm Design Techniques

 Stepwise Refinement – Start with a broad solution and break it down into smaller
steps.
 Divide and Conquer – Break the problem into subproblems, solve them, and
combine results.
 Greedy Algorithm – Always pick the best choice at each step (e.g., shortest path in a
graph).
 Backtracking – Try different solutions and undo steps if needed (e.g., solving a
maze).
 Brute Force – Try all possible solutions (not efficient for large problems).

📌 Common Algorithm Types

1⃣ Searching Algorithms
 Linear Search – Checks each element one by one. (O(n) complexity)
 Binary Search – Works on sorted lists; repeatedly divides in half. (O(log n)
complexity)

2⃣ Sorting Algorithms

 Bubble Sort – Repeatedly swaps adjacent elements if they are in the wrong order.
(O(n²) complexity)
 Insertion Sort – Inserts each element into its correct position. (O(n²) complexity)
 Merge Sort – Splits the array into halves, sorts, and merges. (O(n log n) complexity)
 Quick Sort – Uses a pivot element to partition data. (O(n log n) complexity)

3⃣ Recursion

 A function calls itself to solve a problem in smaller steps.


 Example: Factorial calculation, Fibonacci series.

📌 Writing Algorithms: Pseudocode & Flowcharts

 Pseudocode – Uses simple programming-like statements to describe an algorithm.


 Flowcharts – Graphical representation using symbols:
o Oval – Start/End
o Rectangle – Process (e.g., calculations)
o Diamond – Decision (e.g., if-else conditions)
o Arrow – Flow direction

3⃣ Practice Questions for Chapter 9


📌 Basic Algorithm Questions

1⃣ Write an algorithm to find the largest number in a list of 10 numbers.

2⃣ Write an algorithm to check if a number is even or odd.

3⃣ Write an algorithm that takes a user’s age and prints whether they are a child (0-12),
teenager (13-19), or adult (20+).

📌 Searching & Sorting Questions

4⃣ Given a list of numbers [3, 7, 1, 9, 4], show the steps of Bubble Sort to arrange them in
ascending order.
5⃣ Write pseudocode for Binary Search on a sorted list.

6⃣ What is the time complexity of Merge Sort and why is it better than Bubble Sort?

📌 Recursion & Problem-Solving

7⃣ Write a recursive algorithm to calculate the factorial of a number (n!).

8⃣ Write an algorithm to generate the Fibonacci sequence up to the 10th term.

9⃣ Explain how Divide and Conquer is used in Merge Sort.

📌 Algorithm Optimization & Complexity

🔟 If a program takes O(n²) time, how does increasing input size n affect performance?

1⃣1⃣ Which sorting algorithm is best for small datasets and which one is better for large
datasets? Why?

1⃣2⃣ Write an algorithm to check if a string is a palindrome (reads the same forward and
backward).

📌 Bonus Challenge Question

🎯 A robot is placed in a grid and can only move right or down. Write an algorithm to
find the number of ways the robot can move from (0,0) to (m,n) in the grid.

📌 Computational Thinking (Chapter 9 Extension)

Computational thinking is a problem-solving approach that involves breaking down complex


problems into manageable parts and designing solutions that a computer can execute
efficiently.

1⃣ Key Components of Computational Thinking


🔹 1. Decomposition
✅ Definition:

 Decomposition is breaking a large problem into smaller, manageable parts to


make it easier to understand and solve.

✅ Example:
Problem: Creating a video game
Decomposed into:

1. Game mechanics (movement, controls, scoring)


2. Graphics & design (characters, backgrounds)
3. Sound effects & music
4. User interface (UI) & menus

🔹 Why is it useful?

 Makes problem-solving more organized.


 Allows multiple people to work on different parts.
 Helps in debugging and maintaining code.

🔹 2. Abstraction

✅ Definition:

 Abstraction is removing unnecessary details and focusing on the important parts


of a problem.

✅ Example:
Think of Google Maps:

 A map for drivers highlights roads and traffic but removes details like buildings.
 A map for tourists shows landmarks but hides unnecessary details like small roads.

🔹 Why is it useful?

 Simplifies complex problems.


 Helps focus on what’s important.
 Makes algorithms more efficient.

🔹 3. Pattern Recognition

✅ Definition:
 Pattern recognition is identifying similarities or trends in problems to find efficient
solutions.

✅ Example:

 Spam filters detect patterns in emails (keywords, sender addresses).


 Face recognition identifies patterns in facial features.
 Sorting algorithms use common patterns to organize data efficiently.

🔹 Why is it useful?

 Saves time by applying existing solutions to new problems.


 Improves efficiency in problem-solving.
 Helps in AI and machine learning.

2⃣ Computational Thinking in Algorithms


When designing an algorithm, we use all three concepts together:

1⃣ Decomposition – Break the problem into smaller steps.


2⃣ Abstraction – Remove unnecessary details.
3⃣ Pattern Recognition – Find similarities with known solutions.

3⃣ Practice Questions on Computational Thinking


📌 Decomposition Questions

1⃣ A shopping website needs a search feature. How would you decompose the problem?
2⃣ A banking system requires user authentication (login). Break it down into smaller tasks.

📌 Abstraction Questions

3⃣ What details are important when designing a weather app?


4⃣ Which unnecessary details would you remove in a calculator app?

📌 Pattern Recognition Questions

5⃣ A student grades system is similar to a hospital patient record system. What patterns do
they share?
6⃣ What pattern do you notice in binary search that makes it more efficient than linear
search?

You might also like