Verified first problem in HW2

Learned one thing: it is always better to trace this kind of problem on paper before you decide or say the answer out loud.

Let's move on.

Questions related to sorting

Nice. Finished the first question about sorting.  As expected, some questions trip me.   There are two reasons, 1 is that the implementation of the lecture could be different from mine.  So I need to study the algorithm a bit before I can decide.  Second is that some algorithm is intrinsically tricky to think through.  For example, quicksort and mergesort are two sorts which take some serious time to consider.

But oh well, this is nice because it gives me some insight to some existing sorts which I thought I know (such as selection, insertion, bubble) and some new sort (such as quicksort and radixsort).

Sorting algorithms from the basic Data Structure course

I spent around 30 minutes to take a look.  It is quite cursory.  Also the goal is to mainly bring up the students on the knowledge of the big O notation.  Of course, you also won't expect there is anything difficult other than just mentioned the basic definition of Oh and Theta.

Bubblesort is using power of 2 which is a bad practice.  Whereas quicksort is not using Sedgewick's implementation.   So one can expect the learning is rather amateurish.

Of course, that is my goal for now. I just hope to finish the class.

Chapter 2 (Read 1)

Finished Read 1 of Chapter 2's "Getting Started".  Hadn't done all the exercises except 2.1-1 and 2.1-2.  I greatly enjoyed the style.   The more important part is that I have immersed myself to think the algorithm through.   Now simple algorithm's pseudocode starts to float in my head automatically.

That feeling shouldn't be fuzzy in any parts. If you feel hesitant on some small detail, then the learning is bad. 

By itself Chapter 2 is also a good introduction to sorting as well because most of the analysis and exercises focus on sorting.  If all the exercises are done (including the sectionals and chapter-ends), then one would get a good feel of insertion, selection, merge and bubble sort.   Pretty good value for a chapter.

Feeling an algorithm is one thing, understanding an algorithm means you grok it - my definition of groking:

• You can write it in pseudo.
• You can write it in compilable and workable C, Java, Perl, Python, Assembly and Lisp without using a compiler.
• You understand the worst, the average and the best case analysis of the code. 
• You know all the standard variations, in the case of insertion, I need to know Shell. 
• You know the latest development, in the case of insertion, I need to know Library.
• You know the relationship of the algorithm with other algorithms.  To understand this relationship, it should be defined as the first 5 points above as well.
• You can propose a better algorithm than what are published.

With this definition, I got to admit I am a complete noob on sorting.

It's ok, it could be tough to be an expert on every algorithm.  I will use my usual approach : First read of the book can be shallow but always requires myself to finish all exercise before my read counts as real.

33_P