Approach for Studying cppreference.com

My approach for reading the cpp reference materials is to start by reading each of the high level topics (ie each page that is directly linked from the main cppreference landing page. Once I have made a sweep of the high level topics, I'll go back to do more in depth reading of the lower level material.

There is a lot of material, so it is easy to feel overwhelmed. Even the basic concepts page has mentioned many things that I need to review/learn (like translation, parameter packs, and odr-used). I'll have to find the right balance of digging in and challenging myself to really know what I say I know, yet also moving on from a topic so that I don't become bored and frustrated and quit before I should.

I took a quick look at each of those unfamiliar topics I just mentioned and after reading just a little, things weren't nearly as initmidating as before. Translation is just a series of steps to go from the code we type into our text editors to a format that computers can run. Parameter packs are a group of parameters for templates. They are a somewhat newer feature of the C++ language so I don't feel so bad that I don't know them well. And odr-used is an awkward spelling/grammatical phrase describing the concept that things must have unique definitions (unlike declarations).

So this is the start of my cppreference reading journey. Let's see how it goes.

Week 3 of Algorithms Part III. Mincut/Maxflow

I finished the third week's work for Algorithms II from Coursera.

I flew through the lectures and exercises over the weekend. The first set of lectures was on Mincut/Maxflow, and the second set was on Radix sort of strings. It looks like we are wrapping up our work with graphs and restarting work on strings.

I think the mincut/maxcut graph search algorithm is tricky. One example of applying this algorithm is calculating when a baseball team is mathematically eliminated from the playoffs. The programming assignment was based on this baseball problem. It was trivial to complete (we just used an existing API that calculated the maxflow), but it was still hard for me to wrap my head around.

I'll have to review the graph data structure and algorithms more, but it's cool to think that I've learned all the basics. I've always found graph structures to be intimidating. It may be an oversimplification, but here's what I'd say about most graph problems:

- maintain a list of neighbors. 
- do depth first or breadth first search.
- for a given problem, maintain some auxillary data, 
  like previous node or current weight

and that's about it. I should review the material to judge whether that's really an oversimplification or not, but that's what I'm feeling now.

After the mincut/maxflow stuff, the lectures moved to sorting again. Oddly, we studied radix sort, which is rather trivial compared to the more complicated merge/quick/heap sorts. I guess we are transitioning to other string algorithms, so this just a step in that direction.

And now, the course has a break for one week. I will take the week to go over material and the given job interview questions. And, rest.

Week 2 of Algorithms Part II. MST and Shortest Path

I finished the second week's work for Algorithms II from Coursera.

I had a three day weekend, so I was able to finish the lectures/exercises/programming assignment before the week even started.

We covered Minimum Spanning Trees and Shortest Path algorithms.

For Minimum Spanning Trees, we used Kruskal's algorithm and Prim's Algorithm. I have a hard time remembering what these algorithms refer to. Naming algorithms after a person is nice for that person, but it's a bit pointless. It's like naming a variable in a program after the original coder. It definitely wouldn't pass a code review.

In any case, Prim's algorithm works by doing the following:

Choose a node to start from.
Find the shortest edge that connects it to some other node.
Now, we have a two node component.

Then, repeat the following two steps.
1. From the component, find the shortest edge that connects it to an
   unconnected node.
2. Add that edge and component.

Kruskal's algorithm is a little bit different.

1. Sort the edges from shortest to longest.
2. Choose the shortest edge.
3. Use it if it is making a new connection.
4. Choose the next shortest edge and repeat from step 2.

I think better names for these might be, "NextBestNode" and "NextBestEdge".

Dijkstra's algorithm is an extension of Prim's algorithm where you consider the directions and weights to get the shortest paths.

A key idea in all of these algorithms is to keep building from basic tools. Use things like sorting, priority queues and depth-first or breadth-first iterations, along with some simple arrays for flagging changes and you can come up with some powerful algorithms.

This is demonstrated in the programming assignment. Using a shortest path algorithm with breadth-first searching we're able to do some rather cool image manipulation called seam carving.

This week was fun and cool, but I'll have to go back and review it all so that it really sticks with me moving forward.