$($c$)$ Show how Dijkstra's algorithm would find the shortest path

$[7$ marks$]$

between the start and finish for the weighted undirected graph represented by the adjacency matrix below. What is the shortest path and what is its length?

$\backslash$table$[[,$Start,B$,*$ C$,$D$,$E$,$Finish$],[$Start$,0,4,5,2,0,10],[$B$,4,0,0,0,7,0],[$C$,5,0,0,0,0,6],[$D$,2,0,0,0,0,8],[$E$,0,7,3,0,0,1],[$Finish$,10,0,6,8,1,0]]$

$($d$)$ Show how the Knuth$-$Morris$-$Pratt string searching algorithm

$[7$ marks$]$

would find the pattern $1110101$ in the string $111010011101110101.$ How many character comparisons are required before the pattern is found?$3($a$)$ The following hash table uses quadratic probing.

What is the load factor of this hash table?

How many collisions would take place when searching for the

following numbers:

i$)626$

ii$),381$

iii$),426$

$($b$)$ In a worse$-$case scenario, how many steps would it take for a

$[6$ marks$]$

depth$-$first search to get from the start state to the finish state of

the graph represented by the adjacency matrix below? Show

how the contents of the stack would change during this search.