Unit 7: Computational Thinking — Long Questions

Computational Thinking (CT) is a problem-solving process that involves a set of skills and techniques to solve complex problems in a way that can be executed by a computer. This approach can be used in various fields beyond computer science, such as biology, mathematics, and even daily life.

Let's break down computational thinking into its key components:

Decomposition
Decomposition is the method of breaking down a complicated problem into smaller, more convenient components. Decomposition is an important step in computational thinking. It involves dividing a complex problem into smaller, manageable tasks. Let's take the example of building a birdhouse. This task might look tough at first, but if we break it down, we can handle each part one at a time. Here's how we can decompose the task of building a birdhouse.

• Design the Birdhouse: Decide on the size, shape, and design. Sketch a plan and gather all necessary measurements.
• Gather Materials: List all the materials needed such as wood, nails, paint, and tools like a hammer and saw.
• Cut the Wood: Measure and cut the wood into the required pieces according to the design.
• Assemble the Pieces: Follow the plan to assemble the pieces of wood together to form the structure of the birdhouse.
• Paint and Decorate: Paint the birdhouse and add any decorations to make it attractive for birds.
• Install the Birdhouse: Find a suitable location and securely install the birdhouse where birds can easily access it.

Pattern recognition involves looking for similarities or patterns among and within problems. For instance, if you notice that you always forget your homework on Mondays, you might recognize a pattern and set a reminder specifically for Sundays.

Pattern recognition is an essential aspect of computational thinking. It involves identifying and understanding regularities or patterns within a set of data or problems. Let's consider the example of recognizing patterns in the areas of squares.

The upper row in Figure represents the side lengths of squares, ranging from 1 to 7. The lower row shows the corresponding areas of these squares. Here, we can observe a pattern in how the areas increase.

• Side Length 1: Area = 1² = 1
• Side Length 2: Area = 2² = 4 (1+3)
• Side Length 3: Area = 3² = 9 (1+3+5)
• Side Length 4: Area = 4² = 16 (1+3+5+7)
• Side Length 5: Area = 5² = 25 (1+3+5+7+9)
• Side Length 6: Area = 6²=36 (1+3+5+7+9+11)
• Side Length 7: Area = 7² =49 (1+3+5+7+9+11+13)

We can see that the area of each square can be calculated by adding consecutive odd numbers. For example, the area of a square with a side length of 3 can be found by adding the first three odd numbers: 1 + 3 + 5 = 9.

Abstraction is a fundamental concept in problem solving, especially in computer science. It involves simplifying complex problems by breaking them down into smaller, more manageable parts, and focusing only on the essential details while ignoring the unnecessary ones. This helps in understanding, designing, and solving problems more efficiently.

Definition
Abstraction is the process of hiding the complex details while exposing only the necessary parts. It helps reduce complexity by allowing us to focus on the high-level overview without getting lost in the details.

Example Making a Cup of Tea:
1. Boil water.
2. Add tea leaves or a tea bag.
3. Steep for a few minutes.
4. Pour into a cup and add milk/sugar if desired.

An algorithm is a step-by-step collection of instructions to solve a problem or complete a task similar to following a recipe to bake a cake. An algorithm is a precise sequence of instructions that can be followed to achieve a specific goal, like a recipe or a set of directions that tells you exactly what to do and in what order:

Example Planting a Tree: Here is a simple algorithm to plant a tree, an activity that can be very meaningful and beneficial:

1. Choose a suitable spot in your garden.
2. Dig a hole that is twice the width of the tree's root ball.
3. Place the tree in the hole, making sure it is upright.
4. Fill the hole with soil, pressing it down gently to remove air pockets.
5. Water the tree generously to help it settle.
6. Add much around the base of the tree to retain moisture
7. Water the tree regularly until it is established.

This algorithm gives clear instructions on how to plant a tree, making it easy to follow for anyone.

Computational thinking involves several key principles that guide the process of problem-solving in a structured manner.

Problem Understanding
Understanding a problem involves identifying the core issue, defining the requirements, and setting the objectives. Understanding the problem is the first and most important step in problem-solving, especially in computational thinking. This involves thoroughly analyzing the problem to identify its key components and requirements before attempting to find a solution.

Importance of Problem Understanding

• Clarity and Focus: By fully understanding the problem, you gain clarity on what needs to be solved. This helps you focus on the right aspects without getting distracted by irrelevant details.

• Defining Goals: Proper understanding of the problem allows you to define clear and achievable goals. You can determine what the final outcome should look like and set specific objectives to reach that outcome.

• Efficient Solutions: When you understand the problem well, you can devise more efficient and effective solutions. You can choose the best methods and tools to address the problem, saving time and resources.

• Avoiding Mistakes: By thoroughly understanding the problem, you can avoid common pitfalls and mistakes. Misunderstanding the problem can lead to incorrect solutions and wasted effort.

Example Building a School Website:
Imagine you are asked to build a website for your school. Before jumping into coding, you need to understand the problem:

1. Identify Requirements: What features does the website need? For example, pages for news, events, class schedules, and contact information.
2. User Needs: Who will use the website? Students, teachers, parents? Understanding your audience helps in designing user-friendly interfaces.
3. Technical Constraints: What resources and tools are available? Do you have access to a web server and the necessary software?

By understanding these aspects, you can plan and build a website that meets the needs of your school community.

Problem Simplification
Simplifying a problem involves breaking it down into smaller, more manageable sub-problems.

Example To design a website, break down the tasks into designing the layout, creating content, and coding the functionality.

Solution Selection and Design
Choosing the best solution involves evaluating different approaches and selecting the most efficient one. Designing the solution requires creating a detailed plan or algorithm.

Algorithm design methods provide a range of tools and techniques to tackle various computational problems effectively. Each method has its strengths and weaknesses, making it suitable for different types of problems. Understanding different methods allows one to choose the most appropriate approach for a given problem, leading to more efficient and elegant solutions. Let's discuss two of these methods.

Flowcharts
Flowcharts are visual representations of the steps in a process or system. Flowcharts depicted using different symbols connected by arrows. They are widely used in various fields, including computer science, engineering, and business, to model processes, design systems, and communicate complex workflows clearly and effectively.

Importance of Flowcharts

• Clarity: Flowcharts provide a clear and concise way to represent processes, making them easier to understand at a glance.

• Communication: These are excellent tools for communicating complex processes to a wide audience, ensuring everyone has a common understanding.

• Problem Solving: Flowcharts help identify bottlenecks and inefficiencies in a process, aiding in problem-solving and optimization.

• Documentation: They serve as essential documentation for systems and processes, which is useful for training and reference purpose.

[Flowchart showing: START -> Input a, b, c -> Decision diamonds for b > c, a > b, a > c -> Output b, Output a, Output c -> END]

[Flowchart showing: Start -> Get order -> Item available? (No/Yes) -> Pick, Pack and Ship -> Customer pays? (No/Yes) -> Notify customer/Bring Item back -> Decrease rating/Deliver Item -> Increase rating -> End]

[Flowchart showing: Start -> Has 5 Attempts? (Yes/No) -> Lock account/Login -> Authorized? (No/Yes) -> Alert user/Grant success -> End]

Pseudocode is a method of representing an algorithm using simple and informal language that is easy to understand. It combines the structure of programming clarity with the readability of plain English, making it a useful tool for planning and explaining algorithms. Pseudocode is not actual code that can be run on a computer, but rather a way to describe the steps of an algorithm in a manner that is easy to follow.

Example-1
Determining whether a number is even or odd is a fundamental task in programming and computer science. An even number is divisible by 2 without any remainder, whereas an odd number has a remainder of 1 when divided by 2. Below is the pseudocode for this process, followed by an explanation.

Algorithm 1
Pseudocode for determining if a number is even or odd.

1. Procedure Check Even Odd(number)
2. Input: number (The number to be checked)
3. Output: "Even" if number is even, "Odd" if number is odd
4. Begin
5. if (number % 2 == 0) then
6. print "Even"
7. else
8. print "Odd"
9. End if
10. End

Explanation

1. Procedure Declaration: The pseudocode begins with the declaration of the procedure 'Check Even Odd' which takes a single input, 'number'.

2. Input: The procedure accepts a variable 'number' which is the integer to be checked.

3. Output: The procedure outputs "Even" if the number is even, and "Odd" if the number is odd.

4. Begin: Mark the start of the procedure.

5. Condition Check: The condition 'if (number % 2 == 0)' checks if the remainder of the number when divided by 2 is zero. The modulus operator '%' is used for this purpose.

6. Even Case: If the condition is true, the procedure prints "Even".

7. Odd Case: If the condition is false, the procedure prints "Odd".

8. End: Marks the end of the procedure.

Flowcharts and pseudocode are both tools used to describe algorithms, but they do so in different ways. Understanding their differences can help you decide which method is more suitable to use for your scenario.

Comparison Table

Pseudocode • Pseudocode uses plain language and structured format to describe the steps of an algorithm.
• It is read like a story, with each step is written out sequentially.
• Pseudocode communicates the steps in a detailed, narrative-like format.
• It is particularly useful for documenting algorithms in a way that can be easily converted into actual code in any programming language.

Flowcharts • Flowcharts use graphical symbols and arrows to represent the flow of an algorithm.
• It is like watching a movie, where each symbol (such as rectangles, diamonds, and ovals) represents a different type of action or decision, and arrows indicate the connection and direction of the flow.
• Flowchart communicates the process in a visual format, which can be more easy for understanding the overall flow and structure.
• They are useful for identifying the steps and decisions in an algorithm at a glance.

Example Algorithm: Presents the pseudocode for checking a valid username and password.

1. Procedure Check Credentials (username, password)
2. Input: username, password
3. Output: Validity message
4. Begin
5. validUsername = "user123" (Replace with the actual valid username)
6. validPassword = "pass123" (Replace with the actual valid password)
7. if (username == validUsername) then
8. if (password == valid Password) then
9. print "Login successful"
10. else
11. print "Invalid password"
12. end if
13. else
14. print "Invalid username"
15. end if.
16. End

Techniques to essential algorithms are essential to understand how efficiently they solve problems. In this section, we will explore different techniques for evaluating algorithms, focusing on their time and space complexities.

1. Time Complexity

Time Complexity measures how fast or slow an algorithm performs. It shows how the running time of an algorithm changes as the size of the input increases.

Here's an easy way to understand it:

Imagine you have a list of names, and you want to find a specific name. If you have 10 names, it might only take a few seconds to look through the list. But what if you have 100 names? Or 1,000 names? The time it takes to find the name increases as the list gets longer. Time complexity helps us understand this increase.

2. Space Complexity

Space complexity measures the amount of memory an algorithm uses relative to input size. It is essential to consider both the memory required for the input and any extra memory used by the algorithm.

Dry Run

A dry run involves manually going through the algorithm with sample data to identify any errors.

Dry Run of a Flowchart

A dry run of a flowchart involves manually walk ing through the flowchart step-by-step to understand how the algorithm works without using a computer. This helps identify any logical errors and understand the flow of control.

Example Calculating the Sum of Two Numbers: Consider the flowchart given in figure for adding two numbers:

Steps to dry run this flowchart:
1. Start
2. Input the first number (e.g., 3)
3. Input the second number (e.g., 5)
4. Add the two numbers (3 + 5 = 8)
5. Output the result (8)
6. Stop

Dry Run of Pseudocode

A dry run of pseudocode involves manually simulating the execution of the pseudocode line-by-line.
This helps in verifying the logic and correctness of the algorithm.

Example Finding the Maximum of Two Numbers

Consider the pseudocode for finding the maximum of two numbers:

Algorithm Find Maximum
1. Input: num1, num2
2. if num1 > num2 then
3. max = num1
4. else
5. max = num2
6. end if
7. Output: max

Step to dry run this pseudocode:
1. input num1 and num2 (e.g., 10 and 15)
2. Check if num1 > num2 (10>15: False)
3. Since the condition is False, max = num2 (max = 15)
4. Output max (15)

Simulation is use of computer programs to create a model of a real-world process or system. This helps us understand how things work by testing different ideas or algorithms without needing to try them out in real life.

Use of Simulation

1. Testing Algorithms: We can use simulation to see how well an algorithm works with different types of data. For example, if we want to test a new way to sort numbers, we can simulate it with different sets of numbers to see how fast it is.
2. Exploring Scenarios: Simulation allows us to create many different situations to see what happens. For example, in a science experiment about plant growth, we can simulate different amounts of water or sunlight to find out which conditions help plants grow best.

Benefit of Simulation

• Cost-Effective: It is often cheaper and faster to run simulations than to conduct real experiments.
• Safe: We can test dangerous situations, like a fire in a building, without putting anyone at risk.
• Repeatable: We can run the same simulation multiple times with different settings to observe how things change.

Example of Simulation

1. Weather Forecasting: Meteorologists use simulations to predict the weather. They input data about temperature, humidity, and wind speed into a computer model to see how the weather might change over the next few days.
2. Traffic Flow: City planners can simulate traffic to see how changes to roads or traffic lights might affect the flow of cars. This helps them design better roads and reduce traffic jams.

LARP stands for Logic of Algorithms for Resolution of Problems. It is a fun and interactive way to learn how algorithms work by actually running them and seeing the results. Think of it as a playground where you can experiment with different algorithms and understand how they process data.

Why is LARP Important?

LARP helps you

• Understand how algorithms work. For instance, which illustrates an algorithm designed to determine the applicability of tax on the annual salary of a person.
• See the effect of different inputs on the output.
• Practice writing and improving your own algorithms.

Writing Algorithms

Writing algorithms using LARP involves a structured and simplified approach to developing logical solutions for computational problems. LARP employs a clear syntax that begins with a START command and ends with an END command, ensuring that each step of the algorithm is easy to follow. Within this framework, instructions are provided in a straightforward manner, such as using WRITE to display messages, READ to input values, and conditional statements like IF...THEN...ELSE to handle decision-making processes. Here's an example of a simple algorithm to check if a number is even or odd.

START
WRITE "Enter a number"
READ number
IF number % 2 == 0 THEN
WRITE "The number is even"
ELSE
WRITE "The number is odd"
ENDIF
END

Drawing Flowcharts in LARP

Drawing flowcharts in LARP involves visually representing the algorithm's steps using standard flowchart symbols such as rectangles for process, diamonds for decisions, and parallelogram for input/output operations.

When we write algorithms or create flowcharts in LARP, we sometimes make mistakes called errors or bugs. These mistakes can prevent our algorithms from functioning correctly. Error handling and debugging are processes that help us find and fix these errors.

Types of Errors

There are three main types of errors you might encounter:

• Syntax Errors: These occur when we write something incorrectly in our algorithm or flowchart. For example, missing a step or using the wrong symbol.
• Runtime Errors: These happen when the algorithm or flowchart is being executed. For example, trying to perform an impossible operation, such as dividing a number by zero.
• Logical Errors: These are mistakes in the logic of the algorithm that cause it to behave incorrectly. For example, using the wrong condition in a decision step.

Debugging Techniques

Debugging is the process of finding and fixing errors in an algorithm or flowchart. Here are some common debugging techniques:

• Trace the Steps: Go through each step of your algorithm or flowchart to see identify where it goes wrong.
• Use Comments: Write comments or notes in your algorithm to explain what each part is supposed to do. This can help you spot mistakes.
• Check Conditions: Ensure that all conditions in decision steps are correct.
• Simplify the Problem: Break down the algorithm into smaller parts and test each part separately.

Common Error Message in LARP

Here are some common error messages you might see in LARP and what they mean:

• Missing Step: You probably forgot to i ic an important step in your algorithm.
• Undefined Variable: You are using a variable that hasn't been defined yet.
• Invalid Operation: You are trying to perform an operation that is not allowed, like dividing by zero.

LARP (Logic of Algorithms for Problem Resolution) improves knowledge and implementation of computational thinking principles by taking an immersive, interactive, and collaborative approach to problem solving. Participants gain hands-on experience composing complicated issues, identifying patterns, abstracting pertinent information, and designing successful algorithms through role-playing situations that replicate real-world challenges. LARP makes abstract topics tangible by requiring participants to actively create and test solutions while receiving quick feedback, which encourages incremental improvements. This strategy focuses on collaboration and adaptation, reflecting the dynamic nature of computational problem solving.

Consider a case in which LARP is used to develop a sorting algorithm for organizing volumes in a library based on height. Participants assume roles such as "librarian," "books," and "observers." The librarian employs an initial algorithm, such as bubble sort, to arrange participants (books) according to their displayed height.