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]