Lecture "Brute-force algorithms", exercise 1
essepuntato opened this issue · 11 comments
Write down the execution steps of linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman"), as explained in Listing 7.
def linear_search(input_list, value_to_search):
# defines the function linear_search and the parameters to be used
for position, item in enumerate(input_list):
# the input_list is enumerated (creates a list with each item being assigned a value for its position in the list
# iterates over each item (and its position) on the enumerated list:
if item == value_to_search:
# if the current item is equal to the value to search
return position
# returns the positions of the current item
# algorithm stops
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
# Iteration 1
# position = 0
# item = "Coraline"
# item == value_to_search is False
# Continue to the next iteration
# Iteration 2
# position = 1
# item = "American Gods"
# item == value_to_search is False
# Continue to the next iteration
# Iteration 3
# position = 2
# item = "The Graveyard Book"
# item == value_to_search is False
# Continue to the next iteration
# Iteration 4
# position = 3
# item = "Good Omens"
# item == value_to_search is False
# Continue to the next iteration
# Iteration 5
# position = 4
# item = "Neverwhere"
# item == value_to_search is False
# Continue to the next iteration
# There are no more items in the input_list
# No return statement is executed, so algorithm returns "None"
Write down the execution steps of linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
A linear search finds a value in a list and then return its position.
In this case it doesn't return anything:
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman"):
linear_search(list, "The Sandman")
Iteration 1
position = 0
item = "Coraline"
item == value_to_search is False
**Continue to the next iteration**
Iteration 2
position = 1
item = "American Gods"
item == value_to_search is False
**Continue to the next iteration**
Iteration 3
position = 2
item = "The Graveyard Book"
item == value_to_search is False
**Continue to the next iteration**
Iteration 4
position = 3
item = "Neverwhere"
item == value_to_search is False
**Continue to the next iteration**
Iteration 5
position = 4
item = "Good Omens"
item == value_to_search is False
**Continue to the next iteration**
**Output: None** -> end of the execution of the algorithm
def linear_search(input_list, value_to_search): # define function "linear_search"
for position, item in enumerate(input_list): # iterate all the items in the input list, getting also their position on the list
if item == value_to_search: # check if the current item is equal to the value to search
return position # if so, the position of the current item is returned # and the algorithm stops, if not it doesn't return any position
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
# Iteration 1
# position = 0
# item = "Coraline"
# item == value_to_search is False
# Continue to the next iteration #
# Iteration 2
# position = 1
# item = "American Gods"
# item == value_to_search is False
# Continue to the next iteration #
# Iteration 3
# position = 2
# item = "The Graveyard Book"
# item == value_to_search is False
# Continue to the next iteration #
# Iteration 4
# position = 3
# item = "Good Omens"
# item == value_to_search is False
# Continue to the next iteration #
# Iteration 5
# position = 4
# item = "Neverwhere"
# item == value_to_search is False
# Continue to the next iteration #
# there are no more items to check, so, as the value_to_search is not in the list, the algorithm doesn't report any position.
def linear_search(input_list, value_to_search):
for position, item in enumerate(input_list):
if item == value_to_search:
return position
list_of_books = list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
linear_search(list)["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
#enumerate(list_ of_books) will result in: # enumerate ([(0, "Coraline"), (1, "American Gods"), # (2, "The Graveyard Book"), (3, "Good Omens"), # (4, "Neverwhere")])
#Iteration 1
#position = 0
#item = "Coraline"
#item == value_to_search is False
#continue to the next iteration
#Iteration 2
#position = 1
#item = "American Gods"
#item == value_to_search is False
#continue to the next iteration
#Iteration 3
#position = 2
#item = "The Graveyard Book"
#item == value_to_search is False
#Continue to the next iteration
#Iteration 4
#position = 3
#item = "Good Omens"
#item == value_to_search is False
#Continue to the next iteration
#Iteration 5
#position = 4
#item = "Neverwhere"
#item == value_to_search is False
#Continue to the next iteration
#Returns NONE
Output: None
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
#now we define the Algorithm , we are looking for the book "The Sandman" in a list
for position, item in enumerate("Coraline", "American Gods", "The Graveyard Book", "Good Omens",
"Neverwhere")
#now we have to enumerate the list, so we will have a kind of list with tuples (0, "Coraline", ecc...
#in this case it will be
if item == "The sandman"
return position
#the algorithm will run in the following way:
#Iteration 1
#position = 0
#item = "Coraline"
#item == value_to_search is False
#continue to the next iteration
#Iteration 2
#position = 1
#item = "American Gods"
#item == value_to_search is False
#continue to the next iteration
#Iteration 3
#position = 2
#item = "The Graveyard Book"
#item == value_to_search is False
#Continue to the next iteration
#Iteration 4
#position = 3
#item = "Good Omens"
#item == value_to_search is False
#Continue to the next iteration
#Iteration 5
#position = 4
#item = "Neverwhere"
#item == value_to_search is False
#Continue to the next iteration
#Returns NONE
Output: None
#function to enumerate the list
def linear_search(input_list, value_to_search):
for position, item in enumerate(input_list):
if item == value_to_search:
return position
#creating the list
list_of_books = list (["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
#enumerate ([0, "Coraline", 1 "American Gods", 2 "The Graveyard Book", 3 "Good Omens", 4, "Neverwhere"]))
linear_search(list_of_books, "The Sandman")
#iterate 1
#position = 0
#item = "Caroline"
#item == value_to_search is False
#iterate 2
#position = 1
#item = "American Gods"
#item == value_to_search is False
#iterate 3
#position = 2
#item = "The Graveyard Book"
#item == value_to_search is False
#iterate 4
#position = 3
#item = "Good Omens"
#item == value_to_search is False
#iterate 5
#position = 4
#item = "Nowhere"
#item == value_to_search is False
Return None
End the execution of the algorithm.
def linear_search (input_list, value_to_search):
# iterate all the items in the input list,
# getting also their position on the list
for position, item in enumerate(input_list):
# check if the current item is equal to the value to search
if item == value_to_search:
# if so, the position of the current item is returned
# and the algorithm stops
return position
linear_search(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"] , "The Sandman")
#Iteration 1
#position = 0
#item = "Coraline"
#item == value_to_search is False
#continue to the next iteration
#Iteration 2
#position = 1
#item = "American Gods"
#item == value_to_search is False
#continue to the next iteration
#Iteration 3
#position = 2
#item = "The Graveyard Book"
#item == value_to_search is False
#Continue to the next iteration
#Iteration 4
#position = 3
#item = "Good Omens"
#item == value_to_search is False
#Continue to the next iteration
#Iteration 5
#position = 4
#item = "Neverwhere"
#item == value_to_search is False
#Continue to the next iteration
#Returns NONE
Output: None
list_of_books = list(["Coraline", "American Gods",
"The Graveyard Book", "Good Omens",
"Neverwhere"])
linear_search(list_of_books, "The Sandman")
# FOREACH LOOP EXECUTION
# enumerate(input_list) will result in:
# enumerate([(0, "Coraline"), (1, "American Gods"),
# (2, "The Graveyard Book"), (3, "Good Omens"),
# (4, "Neverwhere")])
#
# Iteration 1
# position = 0
# item = "Coraline"
# item == value_to_search is False
# Continue to the next iteration
#
# Iteration 2
# position = 1
# item = "American Gods"
# item == value_to_search is False
# Continue to the next iteration
#
# Iteration 3
# position = 2
# item = "The Graveyard Book"
# item == value_to_search is False
#
# Iteration 4
# position = 3
# item = “Good Omens"
# item == value_to_search is False
#
# Iteration 5
# position = 4
# item = “Neverwhere"
# item == value_to_search is False
#
# End the execution of the algorithm, return nothing (None)
def linear_search(input_list, value):
for position, item in enumerate(input_list):
if item == "The Sandman":
return position
list_of_books = ["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]
print(linear_search(list_of_books, "The Sandman"))
Iteration 1
# position = 0
# item = "Coraline"
# item == value_to_search is False
# Continue to the next iteration #
# Iteration 2
# position = 1
# item = "American Gods"
# item == value_to_search is False
# Continue to the next iteration
Iteration 3
# position = 2
# item = "The Graveyard Book"
# item == value_to_search is False
# Continue to the next iteration #
# Iteration 4
# position = 3
# item = "Good Omens"
# item == value_to_search is False
# Continue to the next iteration
Iteration 5
# position = 4
# item = "Neverwhere"
# item == value_to_search is False
output is NONE
