Lecture "Brute-force argorithms", exercise 1
essepuntato opened this issue · 20 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.
I tried to code in python and test my code:
for The Sandman it returns not found.
list_of_books = list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
def find_word(word):
found = False
for count, item in enumerate(list_of_books):
if word == item:
found = True
print("found ", word, " in position ", count, " of list of books")
break
if found == False:
print("Not Found!")
return found
def test_find_word(findIt, expected):
if expected == find_word(findIt):
return True
else:
return False
print(test_find_word("The Sandman", False))
print(test_find_word("Good Omens", True))
Not Found!
True
found Good Omens in position 3 of list of books
True
Iteration 1
Position 0
item = "Coraline"
item == value_to_search? False
Iteration 2
Position 1
item = "American Gods"
item == value_to_search? False
Iteration 3
Position 2
item = "The Graveyard Book"
item == value_to_search? False
Iteration 4
Position 3
item = "Good Omens"
item == value_to_search? False
Iteration 5
Position 4
item = "Neverwhere"
item == value_to_search? False
"The Sandman" is not in the list
Execution
for item, position in enumerate(list):
first the list is enumerated: [(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")]
if item == value_to search:
then each item on the list is checked to see if it is equal to the value_to_search.
Iteration 1
Position = 0
Item = “Coraline”
“Coraline” == “The Sandman” is False
Iteration 2
Position = 0
Item= “American Gods”
“American Gods” == “The Sandman” is False
Iteration 3
Position = 2
Item = “The Graveyard Book"
"The Graveyard Book" == “The Sandman” is False
Iteration 4
Position = 3
Item = “Good omens”
“Good omens” == "The Sandman" is False
Iteration 5
Position = 4
Item = "Neverwhere"
"Neverwhere" == “The Sandman” is False
End of items/iteration
The condition is not met, therefore the result is None.
The algorithm linear_search can be described in Python using this general function:
def linear_search(input_list, value_to_search):
for position,item in enumerate(input_list):
if item == value_to_search:
return position
Our input_list is the list_of_books, while our value_to_search is "The Sandman".
The following are the execution steps:
enumerate(input_list) results in enumerate([(0, "Coraline"), (1, "American Gods"),(2, "The Graveyard Book"), (3, "Good Omens"),(4, "Neverwhere")])
Iteration 1
position = 0
item = "Coraline"
item == "The Sandman" is False
The execution continues to the next iteration
Iteration 2
position = 1
item = "American Gods"
item == "The Sandman" is False
The execution continues to the next iteration
Iteration 3
position = 2
item = "The Graveyard Book"
item == "The Sandman" is False
The execution continues to the next iteration
Iteration 4
position = 3
item = "Good Omens"
item == "The Sandman" is False
The execution continues to the next iteration
Iteration 5
position = 4
item = "Neverwhere"
item == "The Sandman" is False
The execution would continue to the next iteration, but there are no more items in the list. Since there's not an alternative return statement, the function returns nothing at all.
list_of_books = list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
linear_search(list_of_books, "The Sandman")
FOR-EACH 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
Continue to next iteration
Iteration 4
position = 3
item = "Good Omens"
item == value_to_search is False
Continue to next iteration
Iteration 5
position = 4
item = "Neverwhere"
item == value_to_search is False
end of the list
after reaching the end of the list and not having found the value searched, nothing at all or 'none' is returned.
def linear_search(input_list, value_to_search):
for position, item in enumerate(input_list):
if item == value_to_search:
return position
print(linear_search(["Coraline", "American Gods", "The Graveyard Book", "Good Omens","Neverwhere"],"The Sandman"))
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
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
Since the value_to_search was not found in the list return the value None and end the execution of the algorithm
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
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
As the iterations show "The Sandman" is not one of the book from the list of books, so if the value to search is not present, Python will return None that means nothing.
For-each loop execution
... and end the execution of the algorithm
def test_linear_search (input_list, value_to_search, expected):
result = linear_search (input_list, value_to_search)
if expected == result:
return True
else:
return False
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"])
print (test_linear_search(list_of_books, "The Sandman", None))
print (test_linear_search(list_of_books, "American Gods", 1 ))
linear_search (list_of_books, "The Sandman")
print (linear_search (list_of_books, "The Sandman"))
#for-each loop execution
#enumerate (input_list) will result in:
#enumerate ([(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")])
#Iteration1
#position = 0
#item = "Coraline"
#item == "The Sandman" is False
#Go to the next iteration
#Iteration2
#position = 1
#item = "American Gods"
#item == "The Sandman" is False
#Go to the next iteration
#Iteration3
#position = 2
#item = "The Graveyard Book"
#item == "The Sandman" is False
#Go to the next iteration
#Iteration4
#position = 3
#item = "Good Omens"
#item == "The Sandman is False
#Go to the next iteration
#Iteration5
#position = 4
#item = "Neverwhere"
#item == "The Sandman" is False
#The value to search is not present in the list so the algorithm returns "None"
Given the function linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman"), let’s rename the first variable my_list:
my_list = list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
Consequently, enumerate(my_list) will result in enumerate([(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")]).
Defining the function linear_search:
# Code 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
It is possible to study the first iteration
Iteration 1
position = 0
item = "Coraline"
item == value_to_search is False
Continue to the next iteration
Then the second:
Iteration 2
position = 1
item = " American Gods "
item == value_to_search is False
Continue to the next iteration
Then the third:
Iteration 3
position = 2
item = " The Graveyard Book "
item == value_to_search is False
Continue to the next iteration
Then the fourth:
Iteration 4
position = 3
item = "Good Omen"
item == value_to_search is False
Continue to the next iteration
Lastly, the fifth:
Iteration 5
position = 4
item = "Neverwhere"
item == value_to_search is False
Continue to the next iteration
The result is hence None
Linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
FOR_EACH LOOP EXECUTION:
enumerate(input_list) will result in:
enumerate([(0, 'Coraline',), (1, 'American Gods'), (2, 'The Graveyard Book'), (3, 'Good Omens'). (4, 'Neverwhere')])
Iter. 1.
position = 0
item = 'Coraline'
item == value_to_search is False
Continue to next iteration
Iter. 2.
position = 1
item = 'American Gods'
item == value_to_search is False
Continue to next iteration
Iter. 3.
position = 2
item = 'The Graveyard Book'
item == value_to_search is False
Continue to next iteration
Iter. 4.
position = 3
item = 'Good Omens'
item == value_to_search is False
Continue to next iteration
Iter. 5.
position = 4
item = 'Neverwhere'
item == value_to_search is False
Return nothing and end the execution of the algorithm
list_of_books = list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
linear_search (list_of_books, "The Sandman")
#FOR-EACH 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 = O
item = "Coralione"
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
#Since the value_to_search was not found the algorithm will return "None"
Task_1
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
FOR-EACH 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
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
Return nothing (as the items are finished and the value_to_search was not found).
End the execution of the algorithm
list("Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere")
linear_search(list, "The Sandman")
FOR-EACH LOOP EXECUTION
enumerate(list)
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
Iteration 2
position = 1
item = "American Gods"
item == value_to_search is False
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
return None
List_of_books = list([“Coraline”, “American Gods”, “The Graveyard Book”, “Good omens”, “Neverwhere”])
linear_search(list_of_books, “The Sandman”) this means that our value_to_search is “The Sandman”
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
The value_to_search was not found this means that the algorithm will return the value none.
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
enumarate(linear_search) --> it result in (enumarate[(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
Next iteration
Iteration 2
position = 1
item = "American Gods"
item == value_to_search is False
Next iteration
Iteration 3
position = 2
item = "The Graveyard Book"
item == value_to_search is False
Next iteration
Iteration 4
position = 3
item = "Good Omens"
item == value_to_search is False
Next iteration
Iteration 5
position = 4
item = "Neverwhere"
item == value_to_search is False
All the items have been processed, the iteration ends. None of the items is "The Sandman". Python will return "None" by default.
linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")
# execution:
# enumerate([(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")])
#
# Iteration 1
# position = 0
# item = "Coraline"
# item == "The Sandman" is False
# Continue to the next iteration
#
# Iteration 2
# position = 1
# item = "American Gods"
# item == "The Sandman" is False
# Continue to the next iteration
#
# Iteration 3
# position = 2
# item = "The Graveyard Book"
# item == "The Sandman" is False
# Continue to the next iteration
#
# Iteration 4
# position = 3
# item = "Good Omens"
# item == "The Sandman" is False
# Continue to the next iteration
#
# Iteration 5
# position = 4
# item = "Neverwhere"
# item == "The Sandman" is False
# Return none
input_list = ["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]
def linear_search(input_list, value_to_search):
for position, item in enumerate(input_list):
if item == value_to_search:
return position
execution:
enumerate(input_list) will result in:
enumerate([(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")])
Iteration:
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
value_to search = "The Sandman"
return value: none