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 karnaugh sequence search

  A linear search

  A binary search

  A merge search

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

  It is not affected by insertions and deletions.

  all of these options are valid advantages

  The list does not need to be in any order.

  Good performance over small to medium lists

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

  A linear/serial search

  Not bothering to search at all

  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 the list is too large i.e >5

  Because 31 is not in the middle

  Because the list is not sorted

  Because the list is too small i.e <100

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

  Binary Graph Algorithm

  Dijkstra's algorithm

  Binary Search path algorithm

  Heuristic 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 / smaller

  Dijkstra's / highest / smaller

  Dijkstra's / lowest / bigger

  Dijkstra's / highest / bigger

 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

  Binary

  Linear

  Dijkstra’s

  A*

 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] &gt; 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': 4, 'D': 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': 1, '4': 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 &lt; 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 10 to: pos = pos - 1

  Change line 3 to: pos = 1

 10. What searching algorithm is the below pseudocode demonstrating? 
OUTPUT &quot;Which customer do you want to find?&quot;
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

  Linear Search

  Linear Sort

  Binary Search

  Binary Sort


Report an error