Lecture "Brute-force argorithms", 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.

[ghasempouri1984]

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

[RebeccaJillianBeattie]

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

[chloeppd]

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.

[OrsolaMBorrini]

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.

[angstigone]

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.

[federicabonifazi]

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

[CarmenSantaniello]

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.

[olgagolgan]

[MaddaGh]

For-each loop execution ... and end the execution of the algorithm

[martasoricetti]

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"

[ManueleVeggi]

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

[11051620]

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

[NoraPs]

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"

[katya-avem]

[AnastasiyaSopyryaeva]

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

[giorgimariachiara]

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

[elizastuglik]

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.

[Bianca-LM]

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.

[AmeliaLamargese]

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

[sanyuezoe]

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