Algorithm design (planning solutions) in Intro to Computing - Real World Applications

Real World Mode - Algorithm design (planning solutions)

Algorithm Design as Planning a Road Trip

Imagine you want to take a road trip to visit several cities. Before you start driving, you need a plan. You decide which cities to visit, the order to visit them, the best roads to take, and where to stop for breaks. This plan helps you reach your destination efficiently without getting lost or wasting time. Algorithm design is like making this road trip plan for solving a problem step-by-step.

Mapping Algorithm Design to Road Trip Planning

Computing Concept	Real-World Equivalent	Explanation
Algorithm	Road trip plan	A clear set of steps to reach a goal (problem solution).
Steps/Instructions	Directions and stops on the route	Each action you take to move closer to your destination.
Input	Starting point and cities to visit	Information you have before starting the trip.
Output	Arriving at all cities in order	The final result of following the plan.
Efficiency	Shortest or fastest route	Choosing the best plan to save time and fuel.
Testing the plan	Checking the map or GPS before driving	Ensuring the plan works before starting.

A Day in the Life: Planning a Road Trip

Sarah wants to visit three friends in different cities. She first lists the cities (input). Then, she looks at a map to decide the order to visit them so she drives the least distance (algorithm design). She writes down the directions and estimated times (steps). Before leaving, she checks the weather and traffic (testing the plan). During the trip, she follows her plan and arrives at each friend's house without getting lost (output). If she finds a road closed, she adjusts her plan (algorithm improvement).

Where the Road Trip Analogy Breaks Down

• Algorithms can be abstract and work on data, not physical places.
• Some algorithms run automatically inside computers without human planning.
• Road trip plans are often flexible, but some algorithms require exact steps.
• Computers can test many plans quickly; humans take longer to plan trips.

Self-Check Question

In our road trip analogy, what would the "testing the plan" step be equivalent to?

Answer: Checking the map or GPS before starting the trip to make sure the route works.

Key Result

Algorithm design is like planning a road trip--deciding the best route and steps to reach your destination efficiently.

Practice

1. What is the main purpose of designing an algorithm before coding?

easy

A. To plan clear steps to solve a problem

B. To write the final program code

C. To test the program output

D. To choose the programming language

Solution

1. Step 1: Understand the role of an algorithm

   An algorithm is a step-by-step plan to solve a problem before coding.

2. Step 2: Differentiate algorithm from coding and testing

   Coding is writing the program, testing checks output, but algorithm is planning steps.

3. Final Answer:

   To plan clear steps to solve a problem -> Option A

4. Quick Check:

   Algorithm = plan steps [OK]

Hint: Algorithms are plans, not code or tests [OK]

Common Mistakes:

• Confusing algorithm with coding
• Thinking algorithm is testing output
• Believing algorithm chooses language

2. Which of the following is the correct way to start an algorithm for finding the largest number in a list?

easy

A. Set largest to 0

B. Set largest to the first number in the list

C. Print the list

D. Sort the list alphabetically

Solution

1. Step 1: Understand initialization in algorithms

   To find the largest number, start by assuming the first number is the largest.

2. Step 2: Evaluate other options

   Setting largest to 0 may fail if all numbers are negative; printing or sorting alphabetically is unrelated.

3. Final Answer:

   Set largest to the first number in the list -> Option B

4. Quick Check:

   Initialize largest with first list item [OK]

Hint: Initialize with first list item, not zero [OK]

Common Mistakes:

• Starting largest at 0 without checking list values
• Sorting list alphabetically instead of numerically
• Printing list instead of initializing variable

3. Consider this algorithm to sum numbers from 1 to 4:

sum = 0
for i in range(1, 5):
  sum = sum + i
print(sum)

What will be the output?

medium

A. 10

B. 15

C. 0

D. Error

Solution

1. Step 1: Understand the loop range

   The loop runs with i = 1, 2, 3, 4 (range(1,5) excludes 5).

2. Step 2: Calculate sum step-by-step

   sum = 0+1=1, 1+2=3, 3+3=6, 6+4=10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   1+2+3+4 = 10 [OK]

Hint: Sum numbers 1 to 4 = 10 quickly [OK]

Common Mistakes:

• Including 5 in the sum
• Confusing range end as inclusive
• Forgetting to add all numbers

4. This algorithm is meant to find the smallest number in a list:

numbers = [3, 1, 4]
smallest = 0
for num in numbers:
  if num < smallest:
    smallest = num
print(smallest)

What is the error in this algorithm?

medium

A. The print statement is missing parentheses

B. The loop should use 'while' instead of 'for'

C. The comparison should be 'num > smallest'

D. smallest should start as the first list number, not 0

Solution

1. Step 1: Check initialization of smallest

   Starting smallest at 0 fails if all numbers are positive and greater than 0.

2. Step 2: Correct initialization

   Set smallest to the first number in the list (3) to compare properly.

3. Final Answer:

   smallest should start as the first list number, not 0 -> Option D

4. Quick Check:

   Initialize smallest with first list item [OK]

Hint: Initialize smallest with first list item, not zero [OK]

Common Mistakes:

• Using wrong comparison operator
• Confusing for and while loops
• Ignoring initialization importance

5. You want to design an algorithm to count how many words in a sentence start with the letter 'a'. Which step should you include in your algorithm?

hard

A. Sort the words alphabetically before counting

B. Count all letters 'a' in the sentence regardless of position

C. Split the sentence into words and check each word's first letter

D. Replace all 'a's with 'b's before counting

Solution

1. Step 1: Break sentence into words

   Splitting the sentence into words allows checking each word individually.

2. Step 2: Check first letter of each word

   Count only words whose first letter is 'a' to meet the problem requirement.

3. Final Answer:

   Split the sentence into words and check each word's first letter -> Option C

4. Quick Check:

   Check first letter of each word [OK]

Hint: Split sentence, check first letter of each word [OK]

Common Mistakes:

• Counting all 'a's, not just word starts
• Sorting words unnecessarily
• Replacing letters before counting