Representing set as *sorted* index sequence and cost analysis of BFS

[jeehoonkang]

Dear all,

A student told me that, if there are duplicated elements in F, then calculating N^+_G(F) may be more expensive then I expected. It's indeed true. So I just changed to lecture note in such a way that:

• We represent F as a sorted index sequence without duplications, instead of an index sequence with possible duplications.

• As a result, we need to update the cost analysis of BFS. Now the calculation of N^+_G(F) involves merging the neighbors of each element f \in F (i.e. flatten A = reduce merge empty A), and thus it spends O(|N^+_G(F)| lg |F|) work and O(lg |F| * lg |V|) span. Thus the total work and span are O(|E| lg |V|) and O(d lg^2 |V|), respectively.

As this is corrected just three days before the exam, I promise I will not ask questions related to the cost analysis of BFS in the exam. I am sorry.

[jaeseok-huh]

Hi, @jeehoonkang. Thanks for the clarification.

I'd like to discuss the precise meaning of |N^+_G(F)| here. Before eliminating the duplicative elements after theflatten, the number of elements can go up to E, even though (# of the unique elements) is capped as |N^+_G(F)|. It means that the mergesort, which is needed for elimination(unique & erase operation in C++ STL), takes Elog(E) = Elog(V) of work and log^2(E)=log^2(V) of span.

Hence, I understand that the work and span notation for line 9 is incorrect.

To further analysis on my own, I would reason as below.

For flatten, W(Vlog(|F|)) and S(log(|F|). Each iteration takes W(Elog(V)) and S(log^2(V)), as V dominates F. Therefore, the total work and span are W(Edlog(V)) and S(dlog^2(V)).

It'd be appreciated if anyone can find a misunderstanding or suggest a tighter bound.

Thanks.

[jaeseok-huh]

Similarly, in DFS and Dijkstra's Algorithm, I think, the computation of |N^+_G(f_0)| alone takes O(ElogV) of work unless the method of its computation is provided otherwise. Please see /search-algorithms/main.tex-commit id 686bc7a.

[jeehoonkang]

By a more precise analysis, we can deduce that the work of N^+_G(F) is O((sum_{f \in F} |N^+_G(f)|) log |V|) and its span is O(log |F|). By summing them up for all the iterations, we can deduce that the total work is O(|E| log |V|) and the total span is O(d log |V|). I'll revisit this topic after the midterm exam.

[CauchyComplete]

@jeehoonkang I think flatten spends O(lg^|F| * log^|V|) not O(lg^2 |F|) because the neighborhoods may exceeds F. Why it is O(lg^2 |F|)?

[jeehoonkang]

@CauchyComplete I fixed it. Thanks. (FYI, the total work and span do not change, as lg |F| = O(lg |V|).)