End of Algorithms 2

After falling a bit behind schedule, I am almost finished with Algorithms II from Coursera. I have finished all of the prgramming assignments and all of the lectures. All that remain is the final round of exercises.

Like many worthwhile pursuits, I am glad that I went through the classes (both Algorithms I and II), and also happy that it is over.

There were a lot of things I think I gained from the experience. It gave me a good survey of lots of data structures and algorithms. I wanted to fill-in holes in my knowledge of algorithms, and I think that these courses have done just that. For all of the more advanced subjects, I need to take deeper dives, but I am happy that I have a good breadth of knowledge at least.

Additionally, since Algorithms is taught with Java examples, I got to work with a foreign language and its specific coding style and tool-set. While frustrating at times, it's fun to try new things.

And opposite the 'new', the lecturer shared many interesting historical anecdotes throughout the course. I'm not really big on history, but I think these little tidbits made the material a bit more colorful, which also makes it easier to recall things.

A bit of advice

Now that I am about to finish my second massive online course, I wanted to offer you (and future me) some advice about taking online courses:

• If you start it, finish it. If you say to yourself, "I'll see how it goes", you will undoubtably quit.
• Do everything. Watch the lectures, do the exercises, do the projects, participate in forums.
• Set a time(s) in your day/week to do the work. Schedule it like an appointment that you can't miss.
• Keep up with the new material and the deadlines (even if they're not really enforced).

What I am saying is, be hard on yourself. Don't let yourself have an excuse for not finishing the course. It's so easy to start and quit.

What's next?

I don't have any plans to take any other Coursera courses in the immediate future. I'll check in again later, but I don't see anything that I'd really want to invest time into for now. So, I don't expect to commit anything else this year.

Luckily, I have a nice backlog of study items that I want to work on. More on that later ...

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.

Week 1 of Algorithms Part II. Graphs

I finished Algorithms 1 from Coursera a couple of weeks ago, and this week, I just finished the first weeek's work for Algorithms II from Coursera.

I tried to make the most of my time off between the two classes. I worked on an open source project, did some reading about building web applications and tried to study some other things. During this time off, I realized that I prefer structured classes. They help me to stay focused on the subject of study. With that said, I have to continue to push myself to focus on the material and my deep understanding of it, instead of allowing myself to be satisfied with simply getting the correct answers for the course.

I think some ways to improve my understanding will be to review and participate in the Coursera discussion forums. This gives me a chance to see how others (different from the course instructors) are thinking about the material. In the discussion forum, I can have the chance to approach things as a teacher, which will also help me to understand the material better.

So, onto my thoughts on week 1 of Algorithms 2.

This week, we went over undirected and directed graphs. Using breadth first and depth first searches, we were able to solve some possibly tricky problems like topological sort and finding strong components in directed graphs. The takeaway for me is to get very comfortable with depth and breadth first searches and to have a good mental image of what we get from each. With these two tools you can have a good chance of answering a question. Interestingly, it's a bit difficult to know at first glance how fast you might be able to solve a given problem. It's a lot less intuitive than guessing calculation times of sorting algorithms.

The lectures did an OK job of presenting the material. There were a few demos that you should watch (not just read through). The exercises were rather pain free. They asked you to trace through the steps of things like breadth first and depth first search.

The programming assignment, similar to ones in Algorithm I, asked us to work with existing implementations (this week, a directed graph) instead of writing an implementation on our own. I guess re-writing an implementation on my own can be part of my own self studying. The most time consuming part of this project was understanding the requirements (can there be multiple terms in a synset, is a word unique across synsets, etc ...) After I figured out what the requirements were, it was pretty straightforward to use the provided directed graph class to finish. I'm not sure if it really improved my understanding of Graphs, but at least it didn't take too much time.

Week 6 of algorithms part 1. Hash table and final exam

The sixth and final week of my coursera algorithms course is done.

This week, we had lectures on hash tables, a set of exercises and a final exam. This was a little different from previous weeks where we would have a little bit more lecture material, two sets of exercises and a programming assignment.

The final exam had a lot of tricky questions, where the major obstacle was just reading the question correctly. I started it a few days ago, and didn't submit until today. Every day, after work, I read over the questions and answers to see if I might have been confused about anything.

I ended up getting an OK score, 9.13 out of 10. I can attempt it a couple of more times, but I don't think there's much point in trying to improve the score. It doesn't really mean anything, and I probably wouldn't learn much by doing it again.

It feels good to be done with this. It's great to finish anything, and this is something I wanted to try and finish years ago.

I signed up for part 2 of this course. After which, I hope to be well versed in all the basic data structures and algorithms that every software developer should know.

The next course starts in 2 weeks, so I'll have a little bit of a break, which is nice. Maybe I'll plan what I want to work on after part 2 of this is done - take another course? study some other way? reallocate time to something else?

Week 5 of algorithms part 1. Red Black Trees

The fifth week of my coursera algorithms course is done.

This was the most interesting week of study for me. We studied balanced binary search trees. I have read about red black trees trees before, but it never really clicked for me. However, the lecture did a great job explaining red black trees by first presenting the related 2-3 tree. This made understanding the red black tree much easier. I am very happy to know this material now.

The exercises were again helpful in pushing me to really understand red black trees. Can you identify if a node should be red or black? Can you make insertions into such a tree? It was a bit painful to write these trees out on paper and trace through the changes, but it's the best way to really show you know it. The exercises had some true/false questions as always, and I got tricked up on them as always. I feel like they are there just to trip you up a few times and make you repeat the exercises a few times before moving on.

This week's programming assignment was my favorite one so far. We actually implemented a KdTree. In some previous assignments we used existing data structures that were presented in class to do something. In this lecture, we were asked to implement the KdTree, which I thought was more interesting and instructive.

I just realized that this is the last programming assignment we will have. This upcoming week, we will have lectures on Hash tables, exercises and then the Final Exam. Hopefully, the exam pushes me to re-think all of the past material and review it so that it really gets engrained in my mind. I have to fight the instinct of trying to just get a good grade, and instead make my goal be getting a good working knowledge of these data structures and algorithms.

Hopefully, I meet that goal.

Week 4 of algorithms part 1

The fourth week of my coursera algorithms course is done.

We learned about heap sort, binary search trees and priority queues. This is the first week when I feel like I am learning something that I am unfamiliar with. In previous weeks, I had a lot of experience studying and using all of the concepts already.

When I hear a problem, my mind visualizes the data using a few common data structures (maybe a stack/queue/sorted array or list/or a tree). For some reason, I don't immediately think about priority queues. This week's lectures reminded me of the importance and power of them. I think I should go back and review the material one more time to further engrain the concepts.

Because I had a day off this week, I was able to finish all of the material this week with a lot of time to spare.

I look forward to the upcoming week's lessons. In it, we will learn about red/black trees and other balanced search trees. This is one of the holes in my computer science knowledge that I'd really like to eliminate.

Week 3 of algorithms part 1

The third week of my coursera algorithms course has just gone by, but I didn't have enough time to finish all of the work.

I started the week OK by completing the lectures and exercises during the weekend. But during the week, I had to go into work early a few times, and I fell behind. I finally submitted the programming assignment this morning. I got a 98.something, with some deductions on performance in one of the test cases. I'd like to get all 100s, but oh well.

This week, we learned about merge sort and quick sort. Even though I was familiar with both of these sorting algorithms before, I think the lectures and exercises really helped me solidify my understanding of both of them.

For me, the most challenging part of the programming assignment was figuring out how to use a "Comparator". That's due to me not being a Java developer. Once again, the programming assignment had very little to do with the lectures or helping me understand sorting algorithms. I don't understand the point of these programming assignments.

This upcoming week, I have an extra day off (President's day) so hopefully, I can go over the previous week's job interview questions and still finish the week's assignments on time.

Week 2 of algorithms part 1

I have finished the second week of my coursera algorithms course.

Last week, I felt a little bit short on time, so I shifted things around a bit. On the weekend, I completed all lectures and exercises. During the week, I was able to finish the programming assignment in a couple of days and then comfortably go through the job interview questions. Getting the lectures and exercises done on the weekend is the key to me doing the work carefully instead of rushing to the end.

The exercises can be a bit annoying. I often had to do them multiple times because I kept getting one of the true or false questions wrong. On the plus side, it forces you to go through the algorithms carefully a bunch of times.

This week, we learned about stacks, queues and some elementary sorts. As a real programmer, we use these so often without thinking about how they are implemented. It's good to dig into the details every once in a while. Hopefully more complex topics are on the way.

The programming assignment was a little bit more interesting this week. We built data structures that were modified versions of the stacks and queues that we learned about in class. This was better than the previous week where we just used API's that used the data structures discussed in class.

The other thought I had while working through things this week was how nice Java + the eclipse IDE is compared to my normal C++ + vim working environment. On the IDE side of things, the autocomplete is so nice. On the language side, a feature like "Implements" seems much cleaner than in C++. In C++, we'd have to inherit a pure virtual interface class. While logically equivalent, it seems a little bit cleaner in Java. However, that might be a biased opinion, as I am a C++ programmer who is learning Java.

Week 1 of algorithms

I have just finished the first week of the coursera course Algorithms, Part I.

We learned about the union find algorithm and how to do some basic analysis of algorithms. I enjoyed the presentation of the union find algorithm (from an initailly naive implementation to a more robust final solution). The material on analyzing an algorithm is of course important, but a little drier and less fun for me.

The quizzes were helpful in forcing me to work through the gritty details of the lectures again. It often took me about 3 tries for each quiz before I got a perfect score. I think each failed attempt forced me to really think about the material.

I didn't really enjoy the programming assignment this week. Setting up the IDE was a chore. The assignment wasn't really about algorithms. It was more about using an API than understanding algorithms.

One of my worries before starting the course was whether I'd have enough time to do all the work. After one week, I'm still worried. I finished all of the work for this week before the next lecutre comes out tomorrow, but it was close. I didn't have much time to review the optional job interview questions. If the material gets more challenging, I may run out of time. To give myself some more leeway, I think I'll have to cover more material on the weekend.

Quick Sort in C++

In my ongoing attempts to improve my programming skills, I've just read about quick sort.  Here is my quick/vague/one line/summary description of quick sort.  The quicksort algorithm works by recursively putting smaller elements to the left of a pivot and larger elements to the right of a pivot until your array is sorted.

Below is my attempt at coding up a working algorithm in C++.  The basic framework of the algorithm is as follows.

void quick_sort( vector & v, int start, int end ) {
    // partition the vector 
    int pivot = partition( v, start, end-1 );

    // recursive calls for each half.
    if ( start < pivot -1 ) 
        quick_sort( v, start, pivot-1 );
    if ( pivot < end ) 
        quick_sort( v, pivot, end );

    return;
}

The meat of the algorithm is in the partition() function. In this function, we do a few things.

1. Pick a pivot value.
2. Move all elements that are less than the pivot to the left of the pivot value.
3. Move all elements that are greater than the pivot value to the right of the pivot value.
4. Return the position of the pivot.  

Here's my code for a pivot function.

int partition( vector & v, int start, int end ) {
    int pivot =  v[ (start + end) / 2 ];

    while( start <= end ) {
       while( v[ start ] < pivot ) start++;
       while( v[ end ] > pivot ) end--;

       // swap values
       if ( start <= end ) {
           int tmp = v[start];
           v[start] = v[end];
           v[end] = tmp;

           start++;
           end--;
       }
    }
    return start;
}

Notes on quick sort.

• I think there are several other ways to write this algorithm.  Different implementations can affect things like how much memory is used, whether it is stable sort, and the overall performance.  
• One example where the implementation can affect performance is the choice of pivot.  I set the pivot as the mid point of the array, but it can be any value. If the input was already sorted, reverse sorted, or random, the pivot position can affect the performance of the algorithm (for better or worse).
• It took me a while to get the algorithm working because it was pretty easy to to have an off by one error in many places.  

Heap Sort with C++

In my attempt to improve my programming skills, I just read about the heap sort algorithm.
Here are my notes and code where I try to understand and implement the heapsort algorithm in C++.

Step one of the heapsort is to build a valid heap.  When someone says heap sort, we are looking at a binary heap.  A binary heap is a binary tree where all levels of a heap are filled (except possibly the last level) and where every parent is greater than either of its children.

For example, if you have an array or vector with these values:
[ 6,  8, 1 , 5, 7, 3,  2... ]
A binary heap would have this shape:

          6
      8        1
    5   7    3   2
...

and we would say 6 is the parent of 8 and 1, 8 is the parent of 5 and 7, etc ...  However, while this binary heap has the right shape, it fails to meet the criteria where every parent is greater than or equal to either of its children.

In order to transform an invalid heap to a valid one, I wrote the functions heapify() and shiftDown():

void heapify( vector & v, int start, int end )  {
    int midPos = ( end - start ) / 2;
    for ( int pos = midPos; pos >= 0; pos-- ) {
        shiftDown( v, pos, end );
    }
}
void shiftDown( vector & v, int parent_pos, int end_pos ) {

    // Sift the parent down the right child?
    int right_child_pos = ( parent_pos * 2 ) + 2;
    if ( right_child_pos < end_pos &&
         v[ parent_pos ] < v[ right_child_pos ] ) {
         int tmp = v[ parent_pos ];
         v[ parent_pos ] = v[ right_child_pos ];
         v[ right_child_pos ] = tmp;
         shiftDown( v, right_child_pos, end_pos );
     }

    // Sift the parent down the left child?
    int left_child_pos = ( parent_pos * 2 ) + 1;
    if ( left_child_pos < end_pos &&
         v[ parent_pos ] < v[ left_child_pos ] ) {
         int tmp = v[ parent_pos ];
         v[ parent_pos ] = v[ left_child_pos ];
         v[ left_child_pos ] = tmp;
         shiftDown( v, left_child_pos, end_pos );
     }

}

The heapify()  function walks from the parent that is on the lowest level of the heap (sits at n/2) to the parent at the top of the heap (position = 0).
For each parent, we use shiftDown() to shift values down the tree until the rule where any parent is greater than or equal to any child is fulfilled.

Given the above functions, we have a partially sorted list where the larger values are at the top of the heap, which is the start of the array.  To get a sorted array where the values go from smallest to largest, we cherry pick the top of the heap to get the max value then rebuild the heap, as follows:

void heapSort( vector & v )  {
    int numItems = v.size();
    heapify( v, 0, numItems - 1);

    for ( int end_pos = numItems - 1; end_pos >= 0; end_pos-- ) {
        int tmp = v[ 0 ]; 
        v[ 0 ] = v[ end_pos ];
        v[ end_pos ] = tmp;

        heapify( v, 0, end_pos);
    }
}

For the sake of testing I also wrote this function to print the array to look like a heap.

void print_as_heap( const vector & v ) {
    int max_row_size = 1;
    int row_size = 0;
    vector::const_iterator it ;
    for ( it = v.begin(); it != v.end(); it ++ ) {
        std::cout << " " << *it;
        row_size++;

        if ( row_size == max_row_size ) {
            std::cout << std::endl;
            row_size = 0;
            max_row_size *= 2;
        }
    }
    std::cout << std::endl;
}

The end.

Insertion Sort with a C++ vector and iterators

In order to practice my programming skills, I thought I'd write some basic sorting algorithms from scratch. Below is my code to do an insertion sort of a vector with iterators in C++.
This took me longer to write than I am willing to admit, indicating that I should continue practicing and writing these algorithms.

void insertion_sort( std::vector & v ) 
{
    // leave if there is nothing to sort
    if ( v.empty() )
    {
        return;
    }

    // go left to right along the vector
    std::vector::iterator l2r_it;
    l2r_it = v.begin();
    l2r_it++;
    for ( ; l2r_it != v.end(); l2r_it++ ) 
    {
        //  go right to left along the vector
        std::vector::iterator r2l_it = l2r_it ;
        while ( r2l_it != v.begin() &&
                *r2l_it < *(r2l_it - 1) )
        {
            int tmp = *r2l_it;
            *r2l_it = *(r2l_it - 1);
            *(r2l_it - 1 ) = tmp;

            r2l_it--;
        }
    }
}