2018-2019
2018-2019 copied to clipboard
comp-think
Lecture "Brute-force algorithms", exercise 1
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
