Preview

08 -Searching Algorithms

 1. What searching algorithm is being demonstrated below?
def Sequential_Search(dlist, item):

    pos = 0
    found = False
    
    while pos < len(dlist) and not found:
        if dlist[pos] == item:
            found = True
        else:
            pos = pos + 1
    
    return found, pos

print(Sequential_Search([11,23,58,31,56,77,43,12,65,19],31))

  A binary search

  A karnaugh sequence search

  A merge search

  A linear search

 2. One of the advantages of a linear search is:

  Good performance over small to medium lists

  It is not affected by insertions and deletions.

  The list does not need to be in any order.

  all of these options are valid advantages

 3. In a very large sorted list, the best searching algorithm from the below options would be:

  Not bothering to search at all

  A linear/serial search

  A binary search

  A sorting algorithm

 4. Why would a Binary search NOT be suitable when searching for '31' in the following list?
#searching for 31
mylist=[11,23,58,31,56,77,43,12,65,19]

  Because 31 is not in the middle

  Because the list is too small i.e <100

  Because the list is not sorted

  Because the list is too large i.e >5

 5. Which Algorithm is known for finding the shortest paths between nodes in a graph, which may represent, for example, road networks

  Heuristic algorithm

  Binary Graph Algorithm

  Dijkstra's algorithm

  Binary Search path algorithm

 6. __________ algorithm finds the shortest path between a and b. It picks the unvisited vertex with the ________ distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if _________

  Dijkstra's / lowest / bigger

  Dijkstra's / highest / smaller

  Dijkstra's / highest / bigger

  Dijkstra's / lowest / smaller

 7. The ________ algorithm is a best-first search algorithm meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these

  A*

  Binary

  Linear

  Dijkstra’s

 8. Can you predict the output of this code? (Dijkstra's shortest path Algorithm)
nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G')
distances = {
    'B': {'A': 5, 'D': 1, 'G': 2},
    'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5},
    'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3},
    'G': {'B': 2, 'D': 1, 'C': 2},
    'C': {'G': 2, 'E': 1, 'F': 16},
    'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2},
    'F': {'A': 5, 'E': 2, 'C': 16}}

unvisited = {node: None for node in nodes} #using None as +inf
visited = {}
current = 'B'
currentDistance = 0
unvisited[current] = currentDistance

while True:
    for neighbour, distance in distances[current].items():
        if neighbour not in unvisited: continue
        newDistance = currentDistance + distance
        if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
            unvisited[neighbour] = newDistance
    visited[current] = currentDistance
    del unvisited[current]
    if not unvisited: break
    candidates = [node for node in unvisited.items() if node[1]]
    current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]

print(visited)

  {'C': 4, 'D': 1, 'G': 2, 'B': 0, 'E': 2, 'F': 4, 'A': 3}

  {'A': 1, '4': 1, 'G': 2, 'B': 0, 'E': 2, 'F': 4, 'C': 3}

  {'A': 1, 'B': 1, 'C': 2, 'D': 0, 'E': 2, 'F': 4, 'G': 3}

  {'A': 4, 'D': 1, 'G': 2, 'B': 0, 'E': 2, 'F': 4, 'C': 3}

 9. What do you need to change in the linear search algorithm below to enable it to return. TRUE, 3 (when searching for '31')?
def Sequential_Search(dlist, item):

    pos = 0
    found = False
    
    while pos < len(dlist) and not found:
        if dlist[pos] == item:
            found = True
        else:
            pos = pos + 2
    
    return found, pos

print(Sequential_Search([11,23,58,31,56,77,43,12,65,19],31))

  Change line 3 to: pos = 31

  Change line 10 to: pos = pos - 1

  Change line 3 to: pos = 1

  Change line 10 to: pos = pos + 1

 10. What searching algorithm is the below pseudocode demonstrating?
OUTPUT "Which customer do you want to find?"
INPUT user inputs John Smith
STORE the user's input in the customer_name variable
customer_found = False
(we need to create a flag that identifies if the customer is found)
WHILE customer_found = False:
	Find midpoint of list
	IF customer_name = record at midpoint of list THEN
		customer_found = True
	ELSE IF customer comes before the midpoint THEN
		throw away the second half of the list
	ELSE 
		throw away the first part of the list
OUTPUT customer details

  Binary Sort

  Binary Search

  Linear Sort

  Linear Search