Sample Class Room Exercises

Mathematical Equation:
- Problem: Solve the equation $2x + 3 = 7$
- Why it’s Well-Defined: The problem has a clear goal (find the value of
  $x$ ), a specific method (solve for $x$ using algebraic rules), and a definite solution ( $x = 2$ ).
Crossword Puzzle:
- Problem: Complete a standard crossword puzzle.
- Why it’s Well-Defined: The crossword has a clear objective (fill in all the squares with the correct words), a specific set of rules, and a single correct solution.
Recipe Execution:
- Problem: Bake a chocolate cake using a provided recipe.
- Why it’s Well-Defined: The goal (bake a chocolate cake) is clear, the process is outlined step-by-step in the recipe, and success is measurable by the outcome (a baked cake that meets the description).

Ill-Defined Problems

These problems are ambiguous, lack clear criteria for solutions, and often have multiple possible solutions. Here are three examples:

Designing a Sustainable City:
- Problem: How can we design a sustainable city for the future?
- Why it’s Ill-Defined: The problem is broad, with no single clear solution. Various factors like environmental impact, social equity, and economic viability come into play, and different stakeholders might have different views on what constitutes a "sustainable" city.
Writing a Novel:
- Problem: Write a compelling novel that appeals to a broad audience.
- Why it’s Ill-Defined: The goal is subjective (what is "compelling"?), the process can vary widely, and success is difficult to measure. Different readers may have different interpretations of what makes the novel appealing.
Resolving Workplace Conflict:
- Problem: Resolve a conflict between two team members in the workplace.
- Why it’s Ill-Defined: The problem is complex with no clear solution. It involves interpersonal dynamics, emotions, and communication styles, and what works in one situation might not work in another. Multiple solutions may exist, and the "right" one depends on various factors.

Summary

Well-Defined Problems are structured, with a clear path and solution.
Ill-Defined Problems are open-ended, ambiguous, and often subjective.

Understanding the nature of the problem helps in choosing the right approach to solving it.

2. Identify five use cases for Trial and error, Heuristics, backtracking, and Means-ends analysis.

When tackling complex problems, different problem-solving strategies can be effective depending on the situation. Here’s an overview of four common strategies—Trial and Error, Heuristics, Backtracking, and Means-Ends Analysis—along with five use cases for each.

1. Trial and Error

This method involves trying different solutions until you find one that works. It’s often used when there’s no clear solution or when the problem is relatively simple.

Use Cases:

Puzzle Games: Solving a jigsaw puzzle by trying different pieces until they fit.
Programming Debugging: Testing various code modifications to fix a bug when the exact cause is unclear.
Chemical Experiments: Mixing different chemicals in varying proportions to achieve a desired reaction in a lab setting.
Lock Combinations: Trying different combinations of numbers to unlock a padlock when you’ve forgotten the code.
Home Repairs: Experimenting with different tools or methods to fix a leaky faucet.

2. Heuristics

Heuristics are mental shortcuts or rules of thumb that simplify decision-making and problem-solving. They don’t guarantee a solution but often lead to a quick, satisfactory one.

Use Cases:

Shopping: Choosing a product based on brand reputation rather than comparing every option.
Navigation: Following the general direction toward your destination instead of using a detailed map.
Medical Diagnosis: Doctors using common symptoms to make an initial diagnosis before conducting detailed tests.
Stock Investment: Investors using past trends to make decisions on buying or selling stocks.
Job Interviews: Hiring managers quickly assessing candidates based on first impressions or resumes.

3. Backtracking

Backtracking is a method of solving problems by making a series of decisions, then undoing them if they lead to a dead end, and trying a different approach.

Use Cases:

Maze Solving: Navigating through a maze by choosing paths, and backtracking if a path leads to a dead end.
Sudoku: Filling in numbers, and backtracking when a mistake is realized.
Recursion in Programming: Writing algorithms that solve problems by breaking them into smaller subproblems and backtracking when necessary.
Puzzles like N-Queens: Placing queens on a chessboard such that no two queens attack each other, and backtracking when a conflict is detected.
Travel Planning: Planning a multi-city trip, backtracking to change a route if it’s not feasible or too expensive.

4. Means-Ends Analysis

Means-Ends Analysis involves breaking down a problem into smaller, more manageable sub-problems, and systematically addressing the differences between the current state and the goal state.

Use Cases:

Project Management: Breaking down a large project into smaller tasks and setting milestones to reach the final goal.
Programming Algorithms: Developing an algorithm by identifying the final output and working backward to define the necessary steps.
Medical Treatment Plans: Doctors setting treatment milestones (e.g., reducing pain, improving mobility) to achieve the final goal of full recovery.
Chess Strategy: Players determining the end goal (checkmate) and working backward to create a sequence of moves to reach it.
Educational Goals: Students setting long-term goals (e.g., graduating) and breaking them down into semester-wise targets and daily study plans.

Summary

Trial and Error is useful when the solution isn’t clear and experimentation is feasible.
Heuristics provide quick, though sometimes imperfect, solutions by using mental shortcuts.
Backtracking is effective in problems where you can undo steps to correct mistakes.
Means-Ends Analysis helps in systematically breaking down complex problems into manageable parts.

Each of these strategies has its place in problem-solving, and the choice of strategy depends on the nature of the problem at hand.

When evaluating problem-solving strategies like Trial and Error, Heuristics, Backtracking, and Means-Ends Analysis, their efficiency can be compared by considering the number of steps required to reach a solution. Here's a comparative evaluation of these algorithms:

1. Trial and Error

Efficiency Evaluation:

Steps Involved: Potentially very high.
Reasoning: This method can be inefficient, as it might involve randomly testing numerous possibilities before finding the correct solution. The number of steps depends on the complexity of the problem and the number of possible solutions.

Example:

Puzzle Game: If a puzzle has 100 pieces, you might need to try many different placements before finding the right one, leading to a large number of steps.

2. Heuristics

Efficiency Evaluation:

Steps Involved: Typically low to moderate.
Reasoning: Heuristics reduce the number of steps by using experience-based techniques to make educated guesses. While not always perfect, this method can lead to quicker solutions than brute force (like Trial and Error).

Example:

Shopping: Instead of comparing all products, choosing a product based on a brand name might take only a few steps.

3. Backtracking

Efficiency Evaluation:

Steps Involved: Moderate to high.
Reasoning: Backtracking involves exploring solutions and undoing steps when a dead end is reached. The number of steps depends on how quickly the correct path is found and how often backtracking occurs.

Example:

Sudoku Puzzle: If you fill in numbers and frequently realize a mistake later, you’ll need to backtrack and try a different approach, potentially involving many steps.

4. Means-Ends Analysis

Efficiency Evaluation:

Steps Involved: Typically moderate.
Reasoning: This method efficiently breaks down the problem into smaller, more manageable sub-problems. The number of steps is reduced by systematically solving each sub-problem toward the final goal.

Example:

Project Management: By dividing a large project into milestones, you can focus on smaller tasks that are easier to manage, reducing the overall number of steps.

Comparative Summary

Trial and Error:
- Efficiency: Often inefficient due to the potentially large number of steps.
- Best for: Simple problems or when no clear solution path is available.
Heuristics:
- Efficiency: More efficient than Trial and Error but less reliable.
- Best for: Quick decisions where perfect accuracy is not essential.
Backtracking:
- Efficiency: Moderately efficient, especially in structured problems.
- Best for: Problems where multiple paths can be explored and retracted, like puzzles or algorithmic challenges.
Means-Ends Analysis:
- Efficiency: Generally efficient due to systematic problem breakdown.
- Best for: Complex problems that can be decomposed into smaller sub-problems with a clear path to the goal.

Conclusion

The efficiency of these problem-solving strategies varies based on the nature of the problem:

Trial and Error can be the least efficient, with a potentially high number of steps.
Heuristics are faster but may not always lead to the optimal solution.
Backtracking is efficient in structured environments where wrong paths can be retraced.
Means-Ends Analysis is often the most efficient for complex, multi-step problems.

Understanding the problem type and applying the appropriate strategy will lead to better problem-solving efficiency.

visualization

3. Use a diagram to solve the Tower of Hanoi for three pegs with the minimum number of moves.

Tower of Hanoi Problem with 3 Pegs

The Tower of Hanoi is a classic mathematical puzzle that involves moving disks between pegs according to specific rules. It's a well-known problem used in both computer science and mathematics to illustrate concepts like recursion, algorithm design, and problem-solving strategies.

Let’s break down the problem and how to solve it when using 3 pegs.

Problem Setup

You are given 3 pegs (A, B, C).
There are n disks of different sizes, initially stacked on one peg (say, Peg A), with the largest disk on the bottom and the smallest on top.
The objective is to move all the disks from Peg A to Peg C following a set of rules.

Rules of the Tower of Hanoi:

You can only move one disk at a time.
A disk can only be placed on top of another disk if it is smaller than the disk beneath it.
You can use Peg B as an intermediate peg to help with the moves.

How to Solve the Tower of Hanoi: Recursive Approach

The Tower of Hanoi puzzle can be solved using a recursive algorithm. The idea is to break the problem down into smaller sub-problems until the solution becomes obvious for the smallest case (moving just 1 disk).

Steps for Recursive Solution:

Base Case (n = 1):
If there is only one disk, move it directly from Peg A to Peg C.
- Move disk 1 from Peg A to Peg C.
Recursive Case (n > 1):
For n disks, the solution can be broken down into the following steps:

Move the top n-1 disks from Peg A to Peg B (using Peg C as the auxiliary peg).
Move the largest disk (disk n) from Peg A to Peg C.
Move the n-1 disks from Peg B to Peg C (using Peg A as the auxiliary peg).

Example: Tower of Hanoi with 3 Disks

Let’s walk through an example where there are 3 disks, labeled from 1 (smallest) to 3 (largest):

Initial Setup:
- Disks are stacked on Peg A: (3, 2, 1) (disk 3 on the bottom, disk 1 on top).
- Target: Move all disks to Peg C.

Step-by-Step Solution:

Move 1: Move disk 1 from Peg A to Peg C.
- Peg A: (3, 2)
- Peg B: ()
- Peg C: (1)
Move 2: Move disk 2 from Peg A to Peg B.
- Peg A: (3)
- Peg B: (2)
- Peg C: (1)
Move 3: Move disk 1 from Peg C to Peg B.
- Peg A: (3)
- Peg B: (2, 1)
- Peg C: ()
Move 4: Move disk 3 from Peg A to Peg C.
- Peg A: ()
- Peg B: (2, 1)
- Peg C: (3)
Move 5: Move disk 1 from Peg B to Peg A.
- Peg A: (1)
- Peg B: (2)
- Peg C: (3)
Move 6: Move disk 2 from Peg B to Peg C.
- Peg A: (1)
- Peg B: ()
- Peg C: (3, 2)
Move 7: Move disk 1 from Peg A to Peg C.
- Peg A: ()
- Peg B: ()
- Peg C: (3, 2, 1)

The puzzle is solved, with all disks now on Peg C, in the correct order!

Recursive Formula for Number of Moves

The number of moves required to solve the Tower of Hanoi problem with n disks can be represented by the recursive relation:

T(n) = 2T(n-1) + 1

Where:

T(n) is the number of moves required for n disks.
T(n-1) is the number of moves for n-1 disks.
The "+1" represents the move of the largest disk.

For n disks, the number of moves is:

T(n) = 2^n - 1

For example:

For 1 disk, the number of moves is: $T(1) = 2^1 - 1 = 1$
For 3 disks, the number of moves is: $T(3) = 2^3 - 1 = 7$ This matches our earlier example, where 7 moves were needed.

5. A recursive function that takes a number and returns the sum of all the numbers from zero to that number.

def sum_recursive(n):

# Base case: if n is 0, the sum is 0

if n == 0:

return 0

# Recursive case: sum of numbers from 0 to n is n + sum of numbers from 0 to n-1

else:

return n + sum_recursive(n - 1)

# Example usage:

number = 5

result = sum_recursive(number)

print(f"The sum of all numbers from 0 to {number} is: {result}")

6. A recursive function that takes a number as an input and returns the factorial of that number.

def factorial_recursive(n):

# Base case: if n is 0 or 1, the factorial is 1

if n == 0 :

return 1

# Recursive case: factorial of n is n multiplied by the factorial of n-1

else:

return n * factorial_recursive(n - 1)

# Example usage:

number = 5

result = factorial_recursive(number)

print(f"The factorial of {number} is: {result}")

7. A recursive function that takes a number ‘n’ and returns the nth Fibonacci number.

def fibonacci_recursive(n):

# Base cases: if n is 0, return 0; if n is 1, return 1

if n == 0:

return 0

elif n == 1:

return 1

# Recursive case: nth Fibonacci number is the sum of (n-1)th and (n-2)th Fibonacci numbers

else:

return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Example usage:

number = 6

result = fibonacci_recursive(number)

print(f"The {number}th Fibonacci number is: {result}")

8. A recursive function that takes an array of numbers as input and returns the product of all the numbers in the array.

def product_recursive(arr):

# Base case: if the array is empty, return 1 (multiplicative identity)

if len(arr) == 0:

return 1

# Base case: if the array has one element, return that element

elif len(arr) == 1:

return arr[0]

# Recursive case: multiply the first element by the product of the rest of the array

else:

return arr[0] * product_recursive(arr[1:])

# Example usage:

numbers = [2, 3, 4, 5]

result = product_recursive(numbers)

print(f"The product of the numbers in the array is: {result}")

9. A program to reverse the contents of an 1D array without using a second array.

def reverse_array(arr):

# Initialize pointers for the start and end of the array

start = 0

end = len(arr) - 1

# Swap elements from start to end until the pointers meet in the middle

while start < end:

# Swap the elements

arr[start], arr[end] = arr[end], arr[start]

# Move the pointers

start += 1

end -= 1

# Example usage:

numbers = [1, 2, 3, 4, 5]

print("Original array:", numbers)

reverse_array(numbers)

print("Reversed array:", numbers)

10. To register for the end-semester examination, you need to log into the University portal with your credentials. Write a program to validate the credentials. Assume that the usernames are stored in an array of strings called USERNAME and the corresponding passwords are stored in another array of strings called PASSWORD such that password[i] is the password for the user username[I].

# Sample data: list of usernames and passwords

USERNAME = ["user1", "user2", "user3"]

PASSWORD = ["pass1", "pass2", "pass3"]

# Input username and password

input_username = input("Enter your username: ")

input_password = input("Enter your password: ")

# Initialize a flag to track if the credentials are valid

is_valid = False

# Iterate through the stored usernames and passwords

for i in range(len(USERNAME)):

if input_username == USERNAME[i] and input_password == PASSWORD[i]:

is_valid = True

break

# Output the result

if is_valid:

print("Login successful!")

else:

print("Invalid username or password. Please try again.")

11. You are given a list and your task is to divide it to make two smaller lists. The sublists should be made from alternate elements in the original list. So if the original list is [5,1,4,12,6], then one sublist should be [5,4,6] and the other should be [1,12].

# Original list

original_list = [5, 1, 4, 12, 6]

# Initializing two sublists

sublist1 = []

sublist2 = []

# Splitting the list into two sublists

for i in range(len(original_list)):

if i % 2 == 0:

sublist1.append(original_list[i])

else:

sublist2.append(original_list[i])

# Output the sublists

print("Sublist 1:", sublist1)

print("Sublist 2:", sublist2)

12. A program that takes three points in a 2D plane and determines whether they are collinear. Two pairs of points are collinear if they have the same slope.# Function to calculate the slope between two points

def slope(x1, y1, x2, y2):

if x2 - x1 == 0: # Check for vertical line to avoid division by zero

return float('inf')

return (y2 - y1) / (x2 - x1)

# Input points

x1, y1 = map(int, input("Enter coordinates of the first point (x1, y1): ").split())

x2, y2 = map(int, input("Enter coordinates of the second point (x2, y2): ").split())

x3, y3 = map(int, input("Enter coordinates of the third point (x3, y3): ").split())

# Calculate slopes between pairs of points

slope1 = slope(x1, y1, x2, y2)

slope2 = slope(x2, y2, x3, y3)

slope3 = slope(x1, y1, x3, y3)

# Check if the slopes are equal

if slope1 == slope2 == slope3:

print("The points are collinear.")

else:

print("The points are not collinear.")

Search This Blog

Algorithmic Thinking with Python KTU BTech S1 UCEST 105 2024 scheme - Dr Binu V P