Algorithms and Data Structures
Tutorial
Algorithmic Thinking: Searching for a Value
In this exercise, we will explore different strategies for searching for a value and how it can be
applied in real-life situations such as building websites and apps.
Introduction
When faced with a problem, there is no one-size-fits-all solution. The goal is to identify the
solution that works best for the given problem. In the game we played, both John and
Brittany took turns to guess a number. When the number was easy, they both took the same
number of turns. However, when the number was larger, Brittany's strategy performed better.
Comparing Strategies
We played the game twice, and the results varied based on the number they were searching
for. When the number was three, both John and Brittany took the same number of turns.
However, when the number was ten, Brittany's strategy was better. It is essential to note that
the specific value they are searching for may not matter as much as where that value lies in
the range given.
Real-Life Application
When building websites and apps, searching for a value is a common task. For instance, when
searching for a friend on Facebook, the app has to search through over 2 billion records to
find the person you are looking for. The speed at which the app finds the person matters as it
affects the user experience. Therefore, companies like Facebook work on making search as
fast as possible using different strategies.
Search Algorithms
John's strategy, where he started at the beginning of the range and counted one number after
the other, is a type of search called linear search. It is a search algorithm that follows a
specific set of guidelines:
Start at the beginning of the list or range of values.
Compare the current value to the target value.
If the current value is the target value, you are done.
If the current value is not the target value, move on to the next value in the list and
repeat step 2.
If you reach the end of the list, the target value is not in the list.
, Brittany's strategy performed better as it followed a different algorithm. The point is that
there is no one algorithm that works for all problems. The algorithm should be specific to the
given problem. An algorithm must have a clear problem statement, and the goal is to follow
the same set of guidelines each time you face the problem.
What Makes an Algorithm?
An algorithm is a set of steps that solves a specific problem. To define an algorithm, we need
to have a clear idea of the problem we are trying to solve, how the input is defined, and what
the output looks like when the algorithm has done its job. Here are some guidelines to follow:
The problem statement must be clearly defined.
The steps in the algorithm must be in a specific order and be distinct.
The algorithm must produce a result and complete in a finite amount of time.
These guidelines help us define what an algorithm is and help us verify that the algorithm is
correct. Consistent results for the same set of values is how we know that the algorithm is
correct. Before rushing in and thinking about solutions, we want to work through the
guidelines first and break down the problem into smaller, clearly defined problems.
What Makes a Good Algorithm?
There is no one single way to measure whether an algorithm is the right solution because it is
all about context. However, there are two measures of efficiency when it comes to algorithms:
time and space complexity. Time complexity is a measure of how long it takes the algorithm to
run, while space complexity deals with the amount of memory taken up on the computer.
Good algorithms need to balance between these two measures to be useful.
Measuring Algorithm Performance
When evaluating an algorithm, one important metric to consider is its running time, which
refers to how long the algorithm takes to run for a given set of values. This allows us to define
time complexity. To illustrate this, let's look at John's performance playing a game in which he
guesses a target value from a set of values. We will focus on his performance in four rounds:
In round one, John had 10 values to choose from, and the target was 3. He took 3 turns to
guess the answer.
In round two, John had 10 values again, but the target was 10. He took 10 turns to guess
the answer.
In round three, John had 100 values to choose from, and the target was 5. He took 5 turns
to guess the answer.
In round four, John had 100 values, and the target was 100. He took 100 turns to guess
the answer.
To measure John's performance, we can plot the number of tries it took him to guess the
answer (the running time of the algorithm) against the number of values in the range. By
Tutorial
Algorithmic Thinking: Searching for a Value
In this exercise, we will explore different strategies for searching for a value and how it can be
applied in real-life situations such as building websites and apps.
Introduction
When faced with a problem, there is no one-size-fits-all solution. The goal is to identify the
solution that works best for the given problem. In the game we played, both John and
Brittany took turns to guess a number. When the number was easy, they both took the same
number of turns. However, when the number was larger, Brittany's strategy performed better.
Comparing Strategies
We played the game twice, and the results varied based on the number they were searching
for. When the number was three, both John and Brittany took the same number of turns.
However, when the number was ten, Brittany's strategy was better. It is essential to note that
the specific value they are searching for may not matter as much as where that value lies in
the range given.
Real-Life Application
When building websites and apps, searching for a value is a common task. For instance, when
searching for a friend on Facebook, the app has to search through over 2 billion records to
find the person you are looking for. The speed at which the app finds the person matters as it
affects the user experience. Therefore, companies like Facebook work on making search as
fast as possible using different strategies.
Search Algorithms
John's strategy, where he started at the beginning of the range and counted one number after
the other, is a type of search called linear search. It is a search algorithm that follows a
specific set of guidelines:
Start at the beginning of the list or range of values.
Compare the current value to the target value.
If the current value is the target value, you are done.
If the current value is not the target value, move on to the next value in the list and
repeat step 2.
If you reach the end of the list, the target value is not in the list.
, Brittany's strategy performed better as it followed a different algorithm. The point is that
there is no one algorithm that works for all problems. The algorithm should be specific to the
given problem. An algorithm must have a clear problem statement, and the goal is to follow
the same set of guidelines each time you face the problem.
What Makes an Algorithm?
An algorithm is a set of steps that solves a specific problem. To define an algorithm, we need
to have a clear idea of the problem we are trying to solve, how the input is defined, and what
the output looks like when the algorithm has done its job. Here are some guidelines to follow:
The problem statement must be clearly defined.
The steps in the algorithm must be in a specific order and be distinct.
The algorithm must produce a result and complete in a finite amount of time.
These guidelines help us define what an algorithm is and help us verify that the algorithm is
correct. Consistent results for the same set of values is how we know that the algorithm is
correct. Before rushing in and thinking about solutions, we want to work through the
guidelines first and break down the problem into smaller, clearly defined problems.
What Makes a Good Algorithm?
There is no one single way to measure whether an algorithm is the right solution because it is
all about context. However, there are two measures of efficiency when it comes to algorithms:
time and space complexity. Time complexity is a measure of how long it takes the algorithm to
run, while space complexity deals with the amount of memory taken up on the computer.
Good algorithms need to balance between these two measures to be useful.
Measuring Algorithm Performance
When evaluating an algorithm, one important metric to consider is its running time, which
refers to how long the algorithm takes to run for a given set of values. This allows us to define
time complexity. To illustrate this, let's look at John's performance playing a game in which he
guesses a target value from a set of values. We will focus on his performance in four rounds:
In round one, John had 10 values to choose from, and the target was 3. He took 3 turns to
guess the answer.
In round two, John had 10 values again, but the target was 10. He took 10 turns to guess
the answer.
In round three, John had 100 values to choose from, and the target was 5. He took 5 turns
to guess the answer.
In round four, John had 100 values, and the target was 100. He took 100 turns to guess
the answer.
To measure John's performance, we can plot the number of tries it took him to guess the
answer (the running time of the algorithm) against the number of values in the range. By
