Quantitative Finance

Computer Science Concepts

Breadth-first Search

     

Use the breadth first strategy to traverse the graph below

List the vertices in the order in which breadth first search traverses them.

  • Start from the node 11.
  • With the choice of two children, visit first the one of higher value.

Given a complete binary tree TT with nn nodes, which of the following best describes the time it takes to find a path using breadth first search from a root VV to another node ss (sTs \in T)?

Consider the above tree. Using breadth first search, we can trace the path PP from any node SS to any other node VV. For example the path from S=1S=1 to V=15V=15 is {1,2,15}\{1,2,15\}.

Let us define a function sP(S,V)sP(S,V) that returns the sum of the nodes in the path PP. So for S=1S=1 and V=15V=15, sP(1,15)=sum({1,2,15})=18sP(1,15)=sum(\{1,2,15\})=18.

Find the value of i=112sP(1,vi)\sum_{i=1}^{12} sP(1,v_i) where viv_i is the iith node in the tree and vi1v_i \neq 1.

×

Problem Loading...

Note Loading...

Set Loading...