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.

[ChiaraCati]

# define a linear_search function that takes as input a list of books and the title of a book 
def linear_search( list_of_books, title):    

    for position, item in enumerate(list_of_books): 
    # at the beginning of every iteration the list is enumerated as follows: [(0, "Coraline"), 
    # (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")]

        # start comparing the input title, with the item lists
        if item == title:
            return position

print(linear_search(list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman"))

Output None

# since in every iteration item == title False is returned, the function stops at the end of the list and returns 
# None as output
#This means that the input title is not contained in input list`

[giorgiasampo]

'''

we define the list of books to search within

list_of_books = ("Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere")

we then define the instruction to look for a specific title

linear_search (list_of_books, "The Sandman")

for every step of the FOR EACH loop it will confront the item in the list with the given input and return it if they are the same

the first execution should return the tuple generated by the enumeration of the list in input

so in the first iteration we should have enumerate = [(0, "Coraline"), (1"American Gods"), (", "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

End of the possible iterations

No matching items found in the given list

return "None" and end the execution of the algorithm

'''

[edoardodalborgo]

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 = ["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]
print(linear_search(list_of_books, "The Sandman"))

When the function is called it runs a for/each loop that iterates on every tuple created
with enumerate function called with the argument list_of_books.
Every tuple contains 2 values: an item of the argument and its specific position in the list.
For every tuple(position, item) the function checks if the item interested in the iteration
is equal to the value_to_search, and if they are equal return the position of the item
in the list that we are looking for and the function stops. If the item of the iteration isn't
the same as the value searched, the function proceeds with another iteration of the for loop
and checks for another item in another tuple created by enumerate on the list.

In our case, we are searching for the item "The Sandman" in our list, but we don't have this item
in our list_of_books. In this case, the function iterate on every item of our list but don't catch
the item we were searching for and return the value None.

[diegochillo]

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 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
# END OF THE LIST
# Return None and end the execution of the algorithm

[dbrembilla]

def linear_search(input_list, value_to_search):

    for position, item in enumerate(input_list):

        if item == value_to_search:

        return position
linear_search(list(["Coraline",
"American Gods", "The Graveyard Book", "Good Omens",
"Neverwhere"]), "The Sandman")

# Loop execution:
# Iteration 1:
# position = 0
# item == value_to_search is False

# Iteration 2:
# position = 1
# item == value_to_search is False

# Iteration 3:
# position = 2
# item == value_to_search is False

# Iteration 4:
# position = 3
# item == value_to_search is False

# Iteration 5
# position = 4
# item == value_to_search is False
# no output

[AleRosae]

The linear search function is defined as follows:

def linear_search (input_list, value_to_search):
    for position, item in enumerate(input_list):
        if item == value_to_search:
            return position

the list of books in which we want to search for the value is the following: books_list = list["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"] the value we want to search for is: "The Sandman" linear_search(books_list, "The Sandman")

Function will iterate throughout the list considering each item one by one, in order to check whether the value is present.

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

Since "The Sandman" is not present in the list, item == value_to_search always returns False, thus Noneis returned as output

[fcagnola]

# 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

input_list = list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"])
print(linear_search(input_list, "The Sandman"))

# The function defined as linear_search will take in input two parameters, 
# a list and a value to search. The execution will then iterate through a 
# for-each loop. Enumerate will return a list like the following
# [(0,"Coraline"), (1,"American Gods"), (2,"The Graveyard Book"), (3,"Good Omens"), (4,"Neverwhere")]
# The algorithm will then iterate through said list in this way:

# 1st iteration:
# position = 0, item = "Coraline"
# value_to_search == item returns False
# proceed to next iteration

# 2nd iteration:
# position = 1, item = "American Gods"
# value_to_search == item returns False
# proceed to next iteration

# 3rd iteration:
# position = 2, item = "The Graveyard Book"
# value_to_search == item returns False
# proceed to next iteration

# 4th iteration:
# position = 3, item = "Good Omens"
# value_to_search == item returns False
# proceed to next iteration

# 5th iteration:
# position = 4, item = "Neverwhere"
# value_to_search == item returns False
# end iteration and return None because the value was not in the list

[yunglong28]

#  Linear Search algorithm

def linear_search(input_list, value_to_search):
    for position, item in enumerate(input_list):
        if item == value_to_search:
            return position

#  List to search is:
list = ["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]

#  Execution:
print(linear_search(list, "The Sandman")
#  enumerate(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
#  the output is None and the for loop is stopped

[gabrielefiorenza]

list_of_books = list(["Coraline", "American Gods","The Graveyard Book", "Good Omens","Neverwhere"]) linear_search(list_of_books, "The Graveyard Book")

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

[AlessandraFa]

# linear search algorithm:
def linear_search(input_list, value_to_search):
    for position, item in enumerate(input_list):
        if item == value_to_search:
            return position

# list to search:
list_of_books = ["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]
value_to_search = "The Sandman"

print(list(enumerate(list_of_books)))
# Output: [(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), 
# (3, "Good Omens"), (4, "Neverwhere")]
# Each tuple has the form (<position>, <item>); for-each algorithm compares each item with 
# the searched value. In this case, the items in list_of_books are compared to "The Sandman".

# Execution:

# Iteration 1:
# for position = 0, item = "Coraline":
# "Coraline" == "The Sandman" is False --> condition not met: execute Iteration 2

# Iteration 2:
# for position = 1, item = "American Gods":
# "American Gods" == "The Sandman is False --> condition not met: execute Iteration 3

# Iteration 3:
# for position = 2, item = "The Graveyard Book":
# "The Graveyard Book" == "The Sandman" is False --> condition not met: execute iteration 4

# Iteration 4:
# for position = 3, item = "Good Omens":
# "Good Omens" == "The Sandman" is False --> condition not met: execute iteration 5

# Iteration 5:
# for position = 4, item = "Neverwhere":
# "Neverwhere" == "The Sandman" is False --> condition not met; end of the list.

# Since value "The Sandman" was not found in the list, the algorithm returns None and ends 
# the execution.

[vanessabonanno]

For-each loop execution

enumerate(list) will return:
-> enumerate([(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")])

1st iteration:
position = 0
item = "Coraline"
item == value_to_search FALSE 
go to next iteration

2nd iteration:
position = 1
item = "American Gods"
item == value_to_search FALSE 
go to next iteration

3rd iteration:
position = 2
item = "The Graveyard Book"
item == value_to_search FALSE 
go to next iteration

4th iteration:
position = 3
item = "Good Omens"
item == value_to_search FALSE 
go to next iteration

5th iteration:
position = 4
item = "Neverwhere"
item == value_to_search FALSE 
No others items in list

Python will end iterations of the for-each loop and will return "None"

[IlaRoss]

Being the function linear_search:

       for position, item in enumerate (input_list):
           if item == value_to_search:
               return position

We execute it for input_list = (["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]) and value_to_search = "The Sandman"

linear_search (list(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"]), "The Sandman")

#FOR-EACH Loop execution
#1st iteration
#position = 0
#item = "Coraline"
#item == value_to_search is False
#Go back and continue with next iteration
#
#2nd iteration
#position = 1
#item = "American Gods"
#item == value_to_search is False
#Go back and continue with next iteration
#
#3rd iteration
#position = 2
#item = "The Graveyard Book"
#item == value_to_search is False
#Go back and continue with next iteration
#
#4th iteration
#position = 3
#item = "Good Omens"
#item == value_to_search is False 
#Go back and continue with next iteration
#
#5th iteration
#position = 4
#item = "Neverwhere"
#item == value_to_search is False
#No more items in the list. Iteration ends.
#
#As no match was found for "The Sandman", the function returns None and the execution ends.

[SusannaPinotti]

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
#next iteration is executed
#
#Iteration 2 
#position = 1 
#item = "American Gods"
#item == value_to_search is False 
#next iteration is executed 
#
#Iteration 3
#position= 2
#item = "The Graveyard Book"
#item == value_to_search is False 
#next iteration is executed
#
#Iteration 4 
#position = 3
#item = "Good Omens"
#item == value_to_search is False 
#next iteration is executed 
#
#Iteration 5
#position = 4
#item = "Neverwhere"
#item == value to search is False 
#the iteration stops 
#
#no value is returned since there is no match 

[LuisAmmi]

The first thing to do is to enumerate the values in the list. So, the algorithm gives us a new list with items associated with their own position. Then, the algorithm will check, one by one, all the item up to find the value specified in the definition of the function.

def linear_search(list_of_book, value_to_search):
    for position, item in enumerate(list_of_book):
        if item == value_to_search:
            return position

print(linear_search(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"],"The Sandman"))

The algorithm runs in this way:
# For-each loop execution
# enumerate(list_of_book) will return `enumerate[(0, "Coraline"), (1, "American Gods"), (2, "The Graveyard Book"), (3, "Good Omens"), (4, "Neverwhere")` 
# it starts with the first iteration:
# 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

# So the value_to_search is not in the list. The algorithm returns None.

[SarahTew]

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 the next iteration Iteration 4 position = 3 item = "Good Omens" item == value_to_search is False Continue to the next iteration Iteration 5 position = 3 item = "Neverwhere" item == value_to_search is False No more iterations Return "None"

[GiuliaMenna]

def linear_search(input_list, value_to_search):
        for position,item in enumerate(input_list):
            if item == value_to_search:
                return position

input_list = ["Coraline","American Gods","The Graveyard Book","Good Omens","Neverwhere"]
value_to_search = "The Sandman"
print(linear_search(input_list, "The Sandman"))

#For-each Loop execution
#Position = 0
#Item = "Coraline"
#Item == value_to_search is false
#Move to the next position

#Position = 1
#Item= "American Gods"
#Item == value_to_search is false
#Move to the next position

#Position = 2
#Item = "The Graveyard Book"
#Item == value_to_search is false
#Move to the next position

#Position =3
#Item ="Good Omens"
#Item == value_to_search is false
#Move to the next position

#Position = e
#Item = "Neverwhere"
#Item == value_to_search is false
#for-each loop execution stops
#Output = None