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 merge search
A karnaugh sequence search
A linear search
A binary search
2. One of the advantages of a linear search is:
3. In a very large sorted list, the best searching algorithm from the below options would be:
4. Why would a Binary search NOT be suitable when searching for '31' in the following list?
5. Which Algorithm is known for finding the shortest paths between nodes in a graph, which may represent, for example, road networks
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 _________
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
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)
{'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}
{'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}
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 = 1
Change line 10 to: pos = pos + 1
Change line 10 to: pos = pos - 1
Change line 3 to: pos = 31
10. What searching algorithm is the below pseudocode demonstrating?