Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 1

Computational thinking:

It is a way of solving problems by breaking them into smaller parts and using logical steps. It helps us think like a computer to
find the best and fastest solution.

Algorithm:

An algorithm is a step-by-step set of instructions to solve a problem or complete a task. It works like a recipe that tells you
exactly what to do, in what order.

Computational Problem:

A computational problem is a problem that can be solved by giving input to a computer, processing it using steps (an
algorithm), and getting the correct output.

1. Sorting numbers: Arranging a list of numbers from smallest to largest.

2. Searching a name: Finding a specific name in a list of students.

3. Calculating average: Finding the average marks of a student from given scores.

Some of the computing problems are as follows:

Decision Problem:
A decision problem is a type of problem that can be answered with a simple "Yes" or "No" based on given input.

Examples:

1. Is the number even?

2. Is the student passed the exam?

3. Is the file found in the computer?

Search Problem:
A search problem is a type of problem where the goal is to find specific information or data from a collection.

Examples:

1. Finding a name in a contact list.

2. Locating a book in a library database.

3. Searching for a file in a computer folder.

Counting Problem:
A counting problem is a problem where we need to count how many items, ways, or solutions meet certain conditions.

Examples:

1. Counting how many students scored above 80 marks.

2. Counting the number of files in a folder.

3. Counting how many times a word appears in a paragraph.

Basics of Counting Problems:

Counting problems help us find the number of ways something can happen. We use simple math rules to count without listing
all possibilities.
Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 2

1. Addition Rule:

Used when choosing one option from different groups. You add the number of choices.
Example: If you can choose 3 fruits or 2 drinks, total choices = 3 + 2 = 5 ways.

2. Multiplication Rule:

Used when making a series of choices (step by step). You multiply the number of choices.
Example: If you have 3 shirts and 2 pairs of pants, total outfits = 3 × 2 = 6 combinations.

3. Permutations:

Used when order is important in selection or arrangement. The same items in different orders are counted separately.
Example: AB and BA are different permutations.

4. Combinations:

Used when order doesn’t matter in selection. The same items in any order are counted once.
Example: AB and BA are the same combination.

Pigeonhole Principle:
If you have more items than containers, at least one container must hold more than one item.
Example: If 5 apples are placed in 4 baskets, one basket will have at least 2 apples.

Inclusion Principle:

When counting items that belong to at least one of two groups, add the number in each group.
Example: If 10 students like football and 8 like cricket, total liking football or cricket = 10 + 8 = 18 (if no overlap).

Exclusion Principle:

If some items belong to both groups, subtract the overlap to avoid counting twice.
Example: If 10 students like football, 8 like cricket, and 4 like both, total = 10 + 8 – 4 = 14 students.

Algorithms and their characteristics:

What is algorithm?
An algorithm is a step-by-step plan to solve a problem. It gives clear instructions to get the desired result.

Properties of algorithms:

1. Input: The data given to the algorithm to start with.

2. Output: The result produced after following the algorithm steps.
3. Definiteness: Each step in the algorithm is clear and unambiguous.
4. Finiteness: The algorithm must finish after a limited number of steps.
5. Effectiveness: Each step can be done easily and correctly.
6. Generality: The algorithm works for all valid input of the problem.

Role of algorithms in computational problem solving:

Algorithms provide clear step-by-step instructions to solve computational problems efficiently. They help turn complex tasks
into simple, easy-to-follow processes.

1. Algorithms make computational problem solving systematic and reliable.

2. They help break complex problems into smaller, manageable tasks.
3. Algorithms provide a clear method to get from input to the desired output.
4. They ensure the solution is correct and repeatable every time.
Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 3

5. Algorithms help computers perform tasks efficiently and quickly.

6. They allow programmers to write clear and organized code.

Applications of algorithms:

1. Sorting and Searching: Organizing data (like names or numbers) and quickly finding items.
2. Graph Algorithms: Solving problems involving networks, like finding the shortest route or connections.
3. Cryptography: Protecting information by encoding it so only authorized people can read it.
4. Machine Learning: Teaching computers to learn from data and make predictions or decisions.
5. Image Processing: Enhancing or analyzing images, like in photo editing or facial recognition.

Logical reasoning:

Logical reasoning is thinking clearly and carefully to solve problems or make decisions. It helps us understand how things
connect and find the right answer step by step.

1. Problem Decomposition: Breaking a big problem into smaller, easier parts to solve one by one.
2. Pattern Recognition: Finding similarities or repeated ideas to help understand and solve problems faster.
3. Abstraction: Focusing on important details only and ignoring unnecessary information.
4. Algorithm Design: Creating a clear step-by-step plan (algorithm) to solve a problem efficiently.

Boolean Logic:

It is a way of using true or false values to make decisions. It uses simple operations like AND, OR, and NOT to combine or
change these true/false statements.

Logical Reasoning Types:

1. Verbal Logical Reasoning: This is when the clues are given to you in words, like a story or a paragraph. To solve it, you
read carefully, understand what's being said, and then pick the best answer from the choices.
2. Non-Verbal Logical Reasoning: This is when the clues are given to you as pictures, shapes, or diagrams. You look at
the images to find the pattern or answer.

Example: Favorite Colors

Imagine three people: Aiza, Uzair, and Luqman. Their favorite colors are red, blue, and green, but we don't know who likes
which one yet. Here are the clues:

1. Aiza doesn't like green.

2. Uzair's favorite color is blue.

3. Luqman doesn't like red.

Let's Solve It:

• Clue 2 tells us for sure: Uzair's favorite is BLUE.

Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 4

• Now we know blue is taken. So, for Aiza, who doesn't like green, the only remaining color is RED. (Because blue is
taken by Uzair, and Aiza doesn't like green, red is the only option left for her).

• Since blue and red are taken, the last color left is GREEN. This must be Luqman's favorite. Does this contradict
"Luqman doesn't like red"? No, because he likes green, not red.

So, the answer is:

• Aiza: RED

• Uzair: BLUE

• Luqman: GREEN

Non-Verbal Logical Reasoning Example:

Example: What Shape Comes Next?

Look at this row of shapes:

[Square] [Triangle] [Circle] [Square] [Triangle] [Circle] [Square] [Triangle] [ ? ]

To Solve This:

Just look for a pattern in the shapes.

• The shapes repeat: Square, Triangle, Circle.

• Then it starts again: Square, Triangle, Circle.

• And again: Square, Triangle...

What's missing? After the Triangle (8th shape), the pattern tells us the next shape (9th) should be a Circle.

So, the answer is: Circle

Standard Algorithms:

Standard algorithms are common methods used to solve basic problems like sorting, searching, and counting. They follow
clear, step-by-step instructions that computers can easily understand. These algorithms are widely used in programming and
form the foundation of computer science.

1. Sorting Algorithms

Used to arrange data in a particular order (ascending or descending).

• Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.

• Selection Sort: Finds the smallest element and places it in the correct position.

• Merge Sort: Divides the list into halves, sorts them, and then merges them.

2. Searching Algorithms

Used to find a specific item in a list.

• Linear Search: Checks each element one by one.

• Binary Search: Repeatedly divides a sorted list in half to find the target.
Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 5

Steps in an Algorithm to Solve a Problem Using Computational Thinking:

Core concepts of computational thinking:

Computational thinking involves solving problems logically and effectively. To design an algorithm using this approach, follow
these key steps:

1. Understand the Problem (Decomposition):

Break the main problem into smaller, manageable parts.

Example: If you want to sort student marks, first understand what "sorting" and "marks" mean.

2. Identify Patterns (Pattern Recognition):

Look for similarities or repeated actions in the problem.

Example: All marks are numbers, and sorting can be done by comparing them.

3. Focus on Key Details (Abstraction):

Ignore unnecessary information and focus only on what's important.

Example: Ignore student names if only marks need to be sorted.

4. Design a Step-by-Step Plan (Algorithm Design):

Create clear and ordered steps to solve the problem.

Example:

1. Start

2. Take input of marks

3. Compare and sort marks

4. Display sorted marks

5. End

Abstraction:

Abstraction means hiding unnecessary details and showing only the important parts of something to make it easier to
understand or use.

1. Maps

• A map hides real-world complexity (trees, people, buildings) and only shows roads, cities, and directions.
Only useful info is shown.

2. Symbols

• Symbols like “@”, “$”, or road signs represent ideas or actions without showing everything.
Simple signs = big meanings.

3. Models

• A model (like a globe or 3D house model) represents something complex in a simple form.
Focuses on key structure, not tiny details.
Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 6

4. Programming Variables

• A variable like age = 20 hides how and where the data is stored in memory.
You just use the variable, not worry about memory.

5. Functions (in Programming)

• A function like add(a, b) hides the steps inside it. You just call it to get the result.
Only input and output matter to the user.

6. Object-Oriented Programming (OOP)

• In OOP, a class like Car hides complex parts like engine details and just lets you call car.start().
You don’t need to know how the engine works.

Example: Steps to Make a Cup of Tea:

1. Boil water

2. Add tea leaves or tea bag to a cup or pot

3. Pour hot water over the tea

4. Let it steep for 2–5 minutes (depending on how strong you like it)

5. Add sugar or honey (optional)

6. Add milk or lemon (optional, depending on the type of tea)

7. Stir well

8. Serve and enjoy

Creating Generalized Solutions:

Creating a generalized solution means designing a method or process that can solve many similar problems, not just one.
It focuses on finding what is common in different cases and creating a single reusable solution.

Steps to Create a Generalized Solution:

1. Identify the Core Problem

• Understand what needs to be solved.

• Focus on the main task, not the extra details.

Example: You need to calculate the total of a list of numbers.

2. Extract the Common Pattern

• Look at different examples and find what stays the same.

• Find the steps or logic that repeats.

Example: Whether it’s 5 numbers or 100, the process is the same: input → add → output.

3. Develop a Generic Solution

• Create a method (algorithm, function, or program) that works for any input of the same type.
Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 7

• Use variables and loops to handle different sizes or inputs.

"Test with Different Scenarios": This just means you should try out your calculator or game in many different ways. Don't just
try the easy stuff! Try putting in weird numbers, or pressing buttons in a strange order, to make sure it works correctly no matter
what. If you find a problem, fix it.

Example: Sorting Algorithms

What is "Sorting"? Sorting means putting things in order, like arranging numbers from smallest to largest, or words
alphabetically.

• Specific Case: Bubble Sort

o Imagine you have a deck of cards all mixed up.

o Bubble Sort is like going through the deck, two cards at a time. If the first card is bigger than the second, you
swap them. You keep doing this, repeatedly, until all the cards are in the right order. It's a specific way to sort.

• Generalized Solution: Many Ways to Sort!

o While Bubble Sort is one way, there are many other ways to sort those cards!

o Think of Quick Sort, Merge Sort, or Heap Sort. These are all different "recipes" or methods to sort the cards.
They all aim to get the same result (a sorted deck), but they use different steps to get there.

o A "generalized solution" means having a way to pick the best sorting method for whatever you're trying to sort.

Example: Calculating Area of Shapes

What is "Area"? Area is the amount of space inside a flat shape, like the space covered by a rug on a floor.

• Specific Case: Area of a Rectangle

o If you want to find the area of only a rectangle, you use a very specific formula: Length x Width. That's it. This
formula only works for rectangles.

• Generalized Solution: Area of Any Shape!

o What if you also need to find the area of a circle, a triangle, or other shapes?

o Instead of having a separate calculator for each type of shape, a "generalized solution" would be like building
one super calculator.

o You could tell this super calculator: "I have a rectangle, its length is X and width is Y, give me the area."

o Or: "I have a circle, its radius is Z, give me the area."

o This one super calculator knows all the different formulas for different shapes and can give you the right
answer for any shape you give it.

Modular Design:

Modular design is a fundamental concept in software engineering and computational thinking, focused on breaking down a
system into smaller, manageable, and interchangeable parts, known as modules.

Example: In programming, functions or methods are modules that perform specific tasks. In Python, a function to calculate
the area of a rectangle.

Example: OOP uses classes and objects to implement modular design.

Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 8

Example: In web development, modular design can be applied through components and services.

1. Define Modules:
Break the complex problem into smaller sub-problems. Create a separate module to solve each core sub-problem.
2. Design Interfaces:
Plan how modules will connect and share data. Define clear input and output for each module.
3. Implement Modules:
Write code for each module based on its design. Follow the steps and interfaces defined earlier.
4. Integrate Modules:
Combine all modules to form the full program. Ensure they work together using proper connections.
5. Test Modules:
Test each module on its own. Then test the complete system to find errors.

Algorithm Dry Run:

Dry run means checking the algorithm step-by-step using sample input. We manually trace the values of variables to see how
the algorithm works.

Example Dry Run Steps (for better understanding):

Let’s say we have this simple algorithm:

Algorithm: Find Sum of First 3 Numbers

1. Start

2. Set sum = 0

3. Read number1, number2, number3

4. sum = number1 + number2 + number3

5. Print sum

6. End

Trace Table

Step number1 number2 number3 sum Output

2 — — — 0 —

3 2 4 6 0 —

4 2 4 6 12 —

5 2 4 6 12 12

Errors :

There are two types of errors that we should understand to improve our problem-solving:

1. Syntax Errors

• These are mistakes in the structure of a sentence or command.

• It's like making a grammar mistake in a sentence.

• Example: Forgetting to write "PKR" before 500.

Instructor: Sartaj Aziz Khan Unit# 2 COMPUTATIONAL THINKING & ALGORITHMS 9

2. Logical Errors

• These are mistakes in thinking or planning.

• The sentence may be correct, but the meaning is wrong.

• Example: Asking for phones under 500, but the results include phones above 500 because you didn’t clearly ask for
new ones only.

Example: Search Engine Query

Query: "Best smartphones for college students under 500"

• Logical Error: The search engine may show used phones or phones above 500 because the request is not clear.

o Better query: "Best new smartphones for college students under 500"

• Syntax Error: The number "500" doesn’t mention the currency (PKR).

o Correct query: "Best new smartphones for college students under PKR 500"