Algorithms - Traversals

Traversals

What is a traversal? It's when you visit every node of a tree or graph using the edges.

Tree traversal

Let's talk about 3 methods of traversing trees (Note: Always start at the root)

• Depth-First-Search: Visit all the descendants of a node before visiting the sibling nodes. You have to visit some nodes more than once in a DFS, this is called backtracking


• Breadth-First-Search: Visit all children of a node before visiting sibling nodes


• Priority Search: Nodes are given priorities, and the children of the node that haven't been visited yet with the highest priority are visited first

So let's try these on a tree. Here's one I made earlier:

Algorithms - More graphs

More Graphs (yay)

Note: This is a direct follow on (or a sequel if you want) to this post, so you might want to read that first!

Representing graphs

So you've seen what graphs are and how they can be classified. But how do you represent them in code? For example, do we put them in an array, a vector or a linked list? There isn't one definite answer, so let's go through some of the methods of representing them.

Algorithms - Intro to Graphs

Intro to Graphs

What are graphs?

So while you might think that graphs are things like these:



..you're right! That is a graph. But when computer scientists talk about graphs, they actually mean these:

Algorithms - Analysis of Algorithms

Analysis of Algorithms

There are 2 ways of doing this:

• Inspecting pseudo code.  This is the analytical approach


• Implement the algorithm and time it. This is the experimental approach

The analytical approach is usually preferred because:

Algorithms - Complexity

Complexity

Note: You really need to read the algorithms text book chapters 1 to 3 as well as reading these notes!

Second note: This will probably be quite short as I'm cutting out all the exposition from the notes and just including the important information.

Algorithms – Trees

So what exactly is a Tree in programming?

Well, it is not a tree that you see every day when you walk through a park :P

Algorithms – Complexity and the Big-Oh

A friend once told me that you can only truly grasp the idea of complexity if you make friends with the Big-Oh; And that's exactly what i intend to help you all with here today! :)