Tag Archives: In-place algorithm

Computer Algorithms: Graph Depth-First Search

Introduction

Along with breadth-first search, depth-first search is one of the two main methods to walk through a graph. This approach though is different. Breadth-first search (BFS) looks pretty much like starting from a vertex and expanding the searching process level by level. This means that first we get some information of all the successors of the given node and then we go further with the next level. In other words BFS is like a wave. Depth-first search is based on a different approach, which can be very useful in some specific algorithms.

DFS vs. BFS
Depth-first and breadth-first search are the two main ways to explore a graph!

Both methods can be useful in solving different tasks. Continue reading Computer Algorithms: Graph Depth-First Search

Friday Algorithms: Input Data and Complexity

Size of ..

As we all know most of the cases a program execution time depends most from the input data. As I wrote in my post the degree of the input data estimates the algorithm complexity.

Of course 3*n² is a bit faster than 5*n², but in general both functions are similar and have the same complexity. In this case we tend to say that the size of the input data is n.

Size of the input data
The size of the input data affects the complexity of the algorithm

It is easy to bind this to arrays or other simple data structures. For example when sorting an array with n elements, the size of the input data is n, but sometimes there is not such an obvious relation between an algorithm and the size of the input data.

For instance when we’ve to search a path into a graph, than maybe the best way to describe the input data is by summing both the number of vertices and the number of edges.

Conclusion

Think, think, think
Think, think, think

However this is important when dealing with algorithms, because a mistake in the estimation of the input data size will result in wrong algorithm estimation at all