Lecture "Brute-force algorithms", exercise 1

[essepuntato]

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.

[delfimpandiani]

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"

[dersuchendee]

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

[ilsamoano]

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.

[lisasiurina]

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

[EleonoraPeruch]

[MattiaSpadoni]

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

[tceron]

#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.

[andreamust]

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

[SeverinJB]

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)

[simayguzel]

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

[DavideApolloni]