Why is DFS O(m+n)

The basic algorithm for BFS:

set start vertex to visited

load it into queue

    while queue not empty

        for each edge incident to vertex

             if its not visited

                 load into queue

                 mark vertex

So I would think the time complexity would be:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

where v is vertex 1 to n




Then the sum

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

can be rewritten as

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

and the first group is O(N) while the other is O(E).

Increasing Stack Size in Visual Studio for Stack Overflow

For one of the questions in the Data Structures Program, Strongly Connected Components, there is a problem. The solution overflow:



It took me quite some time to find a solution to the stack overflow problem. I'm writing this to help everyone else facing the same problem. I saw a couple topics about this problem, but none of them offered a solution. My apologies in case I have missed it and this is a duplicate topic.

I've successfully solved the assignment using C++ with Visual Studio. To adjust the stack size you need to open Project -> "Your project's name" Properties. A dialog box opens. Find "Linker" on the left side. Now click "System". You need to change "Stack Reserve Size" and "Stack Commit Size". I put both to 400 million (it will probably work with a much lower number) and got my program to work.

Linux Question:

-Wl,-stack_size,0x10000000,-stack_addr,0xc0000000

Benchmark Code time

using this for C++ now:

#include <time.h>

double start = clock();

//Code Here

double time = (clock() - start)/ double(CLOCKS_PER_SEC)*1000; //Time in ms

std::cout << "Execution Time is: \t" << time << "ms" << std::endl;

Good Papers from Data Structures Class

1. Locality of Reference (Lists Vs Vectors)
http://en.wikipedia.org/wiki/Locality_of_reference

2. Least Recently Used Cache Algorithm

3. 

When to use Map Data Structure Over Vector

1) When an element is deleted from vector, all the elements below it have to be moved up.
When and element is inserted to vector, all the elements below it have to be moved down.

If you ave many add's and deleted in a program in a sequential list. It might be advantageous to cobnsider map. Map finds the element in logN time

2) When you ave sorted but you might not have all the elemnets in sequence.

e.g., you have edges of vertices 1,2,5,10 etc., it is better to store them in map.

Storing them in vector, you have store edges of 3,4,67,8,9 as empty.

Kosaraju Algorithm of DFS

Computing Strongly Connected Components:

http://scienceblogs.com/goodmath/2007/10/30/computing-strongly-connected-c/

Sorting

Sorting has always been daunting for me to comprehend.

I am taking Coursera course: Algorithms:

I am getting an intuition of why Merge is a better algorithm for sorting?
Ans: Divide and Conquer

Divide is conquer is very powerful, used in sorting, FFT and in many applications. I am now enthusiastic to know more about applications of divide and conquer.


1. Learning about Merge Sort

In merge sort, the input array is split exactly into half and work is done on both halves.

According to Master Method:
Therefore a=2, b= 2, d= 1 (O(n)

b= 2 (since we make two recursive calls)...one for left half and one for right half
d= O(n) since merge is running on length k at each level (Hint: Temp array for loop runs for 2*K times)

a = b ^d. Therefore, O(Mergesort) = O(n^d logn) = O(nlogn)

Note that the master method is useful for calculating Order of Recursive algorithms when a,b,d are clearly defined


2. Quick Sort

In merge sort, a, b,d varies depending on the choice of pivot. Therefore probablity theorems are used to get O(quicksort algorithm)


3. Another example for master method
Finding power of a number (a^b)
Naive way is to multiply a by itself b times. A better way is done using the approach below

    FastPower(a,b) : 

              if b = 1 

                   return a 

              otherwise 

                   c := a*a 

                   ans := FastPower(c,[b/2]) 

               if b is odd 

                   return a*ans 

               otherwise return ans 

end

a=??, b=???, d=???


note in this case,
a = 1 (number of recursive calls each level)
b = 2 (problem is divided into 1/2 length at each level)
d= 0 (the work is independent of length)

a = 1, b^d =1
a= b^d => O(algo) = O(n^0 logn) = 0(logn). This tallies up as there logn level and O(1) work done at each level.