The toughest issues for human to learn are two : 1, their memory is faulty and fading. 2, their memory is too good and never goes away.
33_P
Saturday, April 30, 2011
Friday, April 29, 2011
Insertion sort challenge - the shortest insertion sort program (from Stackoveflow)
That just makes me want to learn Golfscript
http://stackoverflow.com/questions/1712606/insertion-sort-code-challenge
http://stackoverflow.com/questions/1712606/insertion-sort-code-challenge
i++ and ++i
Nice discussion about the difference between i++ and ++i. K&R style prefer ++i. I might also adopt that at some point.
http://stackoverflow.com/questions/24853/c-what-is-the-difference-between-i-and-i
http://stackoverflow.com/questions/24853/c-what-is-the-difference-between-i-and-i
Insertion sort 56-57 (C)
They are all good. My intention is test out characteristic of C. Listing 1 was the original algorithm. Whereas Listing 2 and 3 are for insertion sort 56 and 57. I still find even when the for implementation is shortest, it is not as readable as the while implementation. You can simply compare the C code with the pseudocode and realize that.
I found listing 2 to be the best compromise. It still keep the while-loop but shorten the program for 2 lines. I will adopt it in my code from now on.
Listing 1:
for(j=1;j<N;j++){
k=A[j];
i=j-1;
while(i>=0&&A[i]>k){
A[i+1]=A[i];
i--;
}
A[i+1]=k;
i=j-1;
while(i>=0&&A[i]>k){
A[i+1]=A[i];
i--;
}
A[i+1]=k;
}
Listing 2: Insertion Sort 56
for(j=1;j<N;j++){
k=A[j];
i=j-1;
while(i>=0&&A[i]>k)
i=j-1;
while(i>=0&&A[i]>k)
A[i+1]=A[i--];
A[i+1]=k;
A[i+1]=k;
}
Listing 3: Insertion Sort 57
for(j=1;j<N;j++){
for(k=A[j],i=j-1;i>=0&&A[i]>k;A[i+1]=A[i--]);
A[i+1]=k;
}
for(k=A[j],i=j-1;i>=0&&A[i]>k;A[i+1]=A[i--]);
A[i+1]=k;
}
Thursday, April 28, 2011
To be a mildly good programmer: long journey
Just check out in Amazon a bunch of programming books which could be useful in job interviews. Of course, there are 4 essential sets of book I think everyone should read - I will say DEK, CLRS, Segewick and Bentley are the most essential. Then there are the more advanced version of books which are mostly used for preparing interview. PIE, Cracking Interview, Algorithm for Interviews. Of course this doesn't count books about languages.
I believe a sane way is to follow one single book first and then get it through till the end. During the time, it's alright to reference with other books. Once you finish 1 book, then move on to finish another one. In this way, genuine improvement will come to you.
I believe a sane way is to follow one single book first and then get it through till the end. During the time, it's alright to reference with other books. Once you finish 1 book, then move on to finish another one. In this way, genuine improvement will come to you.
Status at 20110428(b)
Just got out of my sorting routine a bit. It turns out is not that difficult to solve some of the problems such as 10-1.6 and 10-1.7. Of course, there are tons of this kind of trick question about elementary structure.
Finished the reading on median. The algorithm is very smart! In fact, I should spend more time on thinking using similar technique to solve problems.
Also started the basic data structure chapter. This is also where all the classical data structures are presented in the style of CLRS pseudocode. It certainly makes much more sense to me now.
Browse Read: 236/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3, 6.2-4, 10.1-6 and 10.1-7.
Finished the reading on median. The algorithm is very smart! In fact, I should spend more time on thinking using similar technique to solve problems.
Also started the basic data structure chapter. This is also where all the classical data structures are presented in the style of CLRS pseudocode. It certainly makes much more sense to me now.
Browse Read: 236/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3, 6.2-4, 10.1-6 and 10.1-7.
Why I fail so easily in my perl one-liner insertion sort?
I guess part of it is that the program is complicated and takes simplification.
For instance, one can reduce the two assignments in the outer loop to
Also the while loop should be gone because it is always the loop require more inspection adn error checking.
This should shorten the loop and reduce the chance of error.
In the case of perl, it also seems to be a good idea to have less $ in the program. Got to think about it.
For instance, one can reduce the two assignments in the outer loop to
$k=$A[$j];
$i=$j-1;
to ($k,$i)=($A[$j],$j-1);
and$A[$i+1]=$A[$i];
$i--;
to ($A[$i+1],$i)=($A[$i],$i-1);
Also the while loop should be gone because it is always the loop require more inspection adn error checking.
This should shorten the loop and reduce the chance of error.
In the case of perl, it also seems to be a good idea to have less $ in the program. Got to think about it.
Status at 20110428
Finished the reading on median. The algorithm is very smart! In fact, I should spend more time on thinking using similar technique to solve problems.
Also started the basic data structure chapter. This is also where all the classical data structures are presented in the style of CLRS pseudocode. It certainly makes much more sense to me now.
Browse Read: 236/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.
Also started the basic data structure chapter. This is also where all the classical data structures are presented in the style of CLRS pseudocode. It certainly makes much more sense to me now.
Browse Read: 236/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.
Merge sort 1 (CLRS pseudocode)
Wrote the first CLRS pseudo. After some thought, it is clear to me my first real implementation in merge sort should be in perl or python first. Because writing in C will require me to get the memory allocation correct. Technique exists to just use one working memory to solve the problem. But they are certainly not the same as the style from CLRS.
Also read through 5.2.4 by DEK, I don't thoroughly understand it.
Also read through 5.2.4 by DEK, I don't thoroughly understand it.
53rd and 54th writing of insertion sort (CLRS pseudocode, C pseudocode) : insertion sort with sentinel
To deepen my understanding of insertion sort. I start to think through different variants of insertion sort. The most trivial one is to use sentinel in the sort.
In CLRS version, it looks like
1, A[0] = -infinity
2, for j = 1 to N
3, key = A[j]
4, i = j -1
5, while A[i] > k
6, A[i+1] = A[i]
7, i = i - 1
8, A[i+1] = k
I also wrote a C program on paper. So far looks good to me. Of course, the compiler is still the final judge.
Wednesday, April 27, 2011
Merge sort
I decided to start thinking of how to write a respectable merge sort. Compare to insertion and selection. Basic merge sort requires significantly more skill. Obviously to practice it like what I have been doing with insertion and selection. (In case, you hadn't figured out yet - I always try to write a program mistake free in one-shot.)
The key part is merge. The standard algorithm requires used of auxillary memory as well as sentinel. Also, as one might know by reading, insertion sort is usually being used when the size of array is less than 10. This is important to know. If you were like me, you would probably doubt that it is necessary. Of course, both of them are not necessary component of sorting. You can write an in-place algorithm without a sentinel as well.
The key part is merge. The standard algorithm requires used of auxillary memory as well as sentinel. Also, as one might know by reading, insertion sort is usually being used when the size of array is less than 10. This is important to know. If you were like me, you would probably doubt that it is necessary. Of course, both of them are not necessary component of sorting. You can write an in-place algorithm without a sentinel as well.
Daily Practice 20110427(b)
Insertion sort 48 - 51 (python) : only 51 is good. 48: I don't even know the syntax. 49: syntax error, there is no i-- in python. 50, I don't realize the python use 0-based array!
Selection sort 17-19 (python) : only 19 is good. 17: don't realize python has zero-based array. 18: can't remember the cause.
It's good to exercise in unfamiliar language. Python's code is significantly shorter than perl and C even in simple programs such as insertion and selection sorts.
Selection sort 17-19 (python) : only 19 is good. 17: don't realize python has zero-based array. 18: can't remember the cause.
It's good to exercise in unfamiliar language. Python's code is significantly shorter than perl and C even in simple programs such as insertion and selection sorts.
Debugged Insertion sort 47
What happened? Turns out I used
"> =" instead of ">=".
The whole thing dies.
The perfect one-liner game is not for everyone......
"> =" instead of ">=".
The whole thing dies.
The perfect one-liner game is not for everyone......
Insertion sort 45 -47 (perl one-liner)
Ah, it got me. 45 and 46 both failed first time. Debugging one-liner needs to make sure bracket matches mentally. (It's difficult.) I even found that I can't debug insertion sort 47. Since the machine is suddenly halt.
Bummer for the day, I guess this is skill. You got to fail sometime to refine it.
Bummer for the day, I guess this is skill. You got to fail sometime to refine it.
Daily Practice 20110427(a)
Insertion sort 44 (C): Good
Selection sort 16 (C): Good
First time I got it right the first time. Good. For another couple of days, I will start to add merge sort to my routine.
33_P
Selection sort 16 (C): Good
First time I got it right the first time. Good. For another couple of days, I will start to add merge sort to my routine.
33_P
ANSI Common Lisp Chapter 2
I just picked this up from the library - I never learnt lisp and probably would never learn it well. Though I am always fascinated by the alternative thinking offered by the language.
May be this is my 4th language to fill in ...... It's actually not that difficult to learn though. Learn well - that probably takes a life time.
May be this is my 4th language to fill in ...... It's actually not that difficult to learn though. Learn well - that probably takes a life time.
Tuesday, April 26, 2011
Insertion sort 43 (perl one-liner)
:) Quite epic.
perl -lane '{push @A,$_}END{for($j=1;$j<$#A+1;$j++){$k=$A[$j];$i=$j-1;while($i>=0&&$A[$i]>$k){$A[$i+1]=$A[$i];$i--}$A[$i+1]=$k;} printf("%s\n",join(" ",@A))}'
33_P
perl -lane '{push @A,$_}END{for($j=1;$j<$#A+1;$j++){$k=$A[$j];$i=$j-1;while($i>=0&&$A[$i]>$k){$A[$i+1]=$A[$i];$i--}$A[$i+1]=$k;} printf("%s\n",join(" ",@A))}'
33_P
Daily Practice 20110426c
Insertion sort 42 (Perl): GoodSelection sort 15 (Perl): Good
My first selection sort in perl. Feels good.
33_P
My first selection sort in perl. Feels good.
33_P
Expanded Further readings for insertion sort and selection sort
Further readings for insertion sort and selection sort
-sentinel version of straight insertion sort
-binary search
-binary insertion sort
-recursive version of insertion sort
-shell sort
-library sort
-tree sort(?)
-TAOCP Exercise in 5.2.1
Selection sort:
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
-tournament sort
-smoothsort.
-TAOCP Exercise in 5.23
Selection sort 14 (CLRS Pseudocode)
This is just a write up of selection sort with using one index in the code. In fact. I figured, you can also remove the varible t in the code because one can just use i to be the temporary variable as well. I have been using it since selection sort 13. Probably I should write it up in the next selection sort write up.
33_P
33_P
insertion sort with sentinels
Found two papers (wow.) on insertion sort with sentinels.
Using Sentinels In Insert Sort (1989) by Harold Thimbleby
Also An improved insert sort algorithm
Also Jon Bentley's method of insertion sort actually reduce one subtraction in the outside loop of straight insertion sort without sentinels. Ah ,where is my "Programming Pearl"? Who doesn't want to exhaust the topic as simple as insertion sort?
33_P
Using Sentinels In Insert Sort (1989) by Harold Thimbleby
Also An improved insert sort algorithm
Also Jon Bentley's method of insertion sort actually reduce one subtraction in the outside loop of straight insertion sort without sentinels. Ah ,where is my "Programming Pearl"? Who doesn't want to exhaust the topic as simple as insertion sort?
33_P
TAOCP Vol 3 (5.2.1 and 5.2.3)
I reread the two sections about insertion sort and selection sort in TAOCP. Those are two very good sections on this seeminly simple subject. In fact, I should regard I understand these broad types of sorting technique *after* I finished the exercises in TAOCP first.
One thing I learn is that insertion sort's performance is actually related the average number of inversion in a sequence. This gives a better insight than the standard probablistic arguments.
Very interesting. There are just so many things I don't know even in "simple" matters.
33_P
One thing I learn is that insertion sort's performance is actually related the average number of inversion in a sequence. This gives a better insight than the standard probablistic arguments.
Very interesting. There are just so many things I don't know even in "simple" matters.
33_P
Daily Practice 20110426
Insertion sort 40 (C): Good
Selection sort 10,11,12 (C): 10 Bad, 11 Bad, 12 Good. Why?
10 used tmp rather than A in swapping - it's a good thing to always mind the variable you used.
11 used the assign A[j] to min instead of j. The caused the whole program looks like it is working. This is a subtle bug if the value of A is closed to sort.
My problem of selection sort is that I hadn't gone through the what if analysis of the whole algorithm. I should try it some time.
33_P
Selection sort 10,11,12 (C): 10 Bad, 11 Bad, 12 Good. Why?
10 used tmp rather than A in swapping - it's a good thing to always mind the variable you used.
11 used the assign A[j] to min instead of j. The caused the whole program looks like it is working. This is a subtle bug if the value of A is closed to sort.
My problem of selection sort is that I hadn't gone through the what if analysis of the whole algorithm. I should try it some time.
33_P
Monday, April 25, 2011
The Art of Computer Programming by Knuth
Trying to restock all books in my house. I finally get back my 3 volumes of "The Art of Computer Programming". How I am fascinated by it! Even simple as insertion, there is a lot of things I don't know!
And how much I want to know about random generator! How much I want to know about selection!
At this point I just treat it as a reference. But one day I will read it like a book.
33_P
And how much I want to know about random generator! How much I want to know about selection!
At this point I just treat it as a reference. But one day I will read it like a book.
33_P
Status at 20110425(b)
Finished browse reading of Chapter 8. As it turns out the concepts are not that difficult to grasp. It's the analysis which is difficult to get it right.
When you talked with experienced programmer, they usually don't feel content if they only know the algorithm by heart. They also want to know the complete analysis of the algorithm.
That makes me think: I should probably go back to work out the insertion sort (and selection sort) in the manner of Section 2.2.
33_P
Browse Read: 214/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.
When you talked with experienced programmer, they usually don't feel content if they only know the algorithm by heart. They also want to know the complete analysis of the algorithm.
That makes me think: I should probably go back to work out the insertion sort (and selection sort) in the manner of Section 2.2.
33_P
Browse Read: 214/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.
Reminder to myself.
Got to master Java or C++ soon. I hope to fill in my programming requirement for insertion sort.
Further readings for insertion sort and selection sort
Insertion sort:
-sentinel version of straight insertion sort
-binary search
-binary insertion sort
-shell sort
-library sort
-tree sort(?)
Selection sort:
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-cycle sort
-heap sort variants
-tournament sort
-smoothsort.
-sentinel version of straight insertion sort
-binary search
-binary insertion sort
-shell sort
-library sort
-tree sort(?)
Selection sort:
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-cycle sort
-heap sort variants
-tournament sort
-smoothsort.
Status at 20110425
* Finished 2.3-1. It's trivial.
* Also thought through 2.3-7, it's a cute question. It teaches a pattern. Whenever you got stuck at a problem, try to sort some of the data.
* Exercises 2.3-2 - 2.3-6 are all cute exercises which guide the reader through slightly advanced concept such as binary search as well as binary insertion tree. This makes one able to learn 5 sorting algorithms in this chapter. Pretty neat indeed.
* It's also time to make merge sort to be one of my move. Pretty neat idea as well.
Browse Read: 200/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.
* Also thought through 2.3-7, it's a cute question. It teaches a pattern. Whenever you got stuck at a problem, try to sort some of the data.
* Exercises 2.3-2 - 2.3-6 are all cute exercises which guide the reader through slightly advanced concept such as binary search as well as binary insertion tree. This makes one able to learn 5 sorting algorithms in this chapter. Pretty neat indeed.
* It's also time to make merge sort to be one of my move. Pretty neat idea as well.
Browse Read: 200/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.
Daily Practice 20110425
Insertion sort: 38th and 39th writings (C) : 38th - disaster, got syntax wrong for initializing an array and assigned a wrong variable to k. Make it your habit to think the index order. 39th - get it right.
Selection sort: 8th writing and 9th writings (C) : 8th - wrong, change the sign of comparison. So it sorts the other way. 9th is good.
Found myself not very focused today.
33_P
Selection sort: 8th writing and 9th writings (C) : 8th - wrong, change the sign of comparison. So it sorts the other way. 9th is good.
Found myself not very focused today.
33_P
Quicksort
Every programmer knows that quicksort is the most prominent method in sorting. Saving funny sorting scheme such as bubble or shell, quicksort is also very difficult to be analyzed. So I decided to read through Chapter 7 of CLRS. Quicksort would probably take me at least 100-200 practices to fully master because there are just too many possible variations. Just the original Sedgewick's paper and survey paper would make at least 10 variations possible.
33_P
33_P
Sunday, April 24, 2011
Daily Practice 20110424b
insertion sort: 38th and 39th writings in C :38th missed a ;, 39th is good. At 11:35 p.m., I was feeling tired and certainly lost focus. But this is good time to practice making myself focused.
selection sort: 7th writing in C: Good.
Each take around 3 mins.
33_P
selection sort: 7th writing in C: Good.
Each take around 3 mins.
33_P
Daily Practice 20110424
insertion sort: 37th writing in C : Good ~3mins.
selection sort : 5th and 6th writing in C : 5th is bad but 6th is good. 5th has issue because of swapping was slightly wrong. Now I know a non-insertion sort error pattern in my head. ~5 mins.
I am taking approximately 3 mins in insertion sort and 5 mins in selection sort. It is certainly something I can improve. My first speed goal is to write them under 60 seconds.
33_P
selection sort : 5th and 6th writing in C : 5th is bad but 6th is good. 5th has issue because of swapping was slightly wrong. Now I know a non-insertion sort error pattern in my head. ~5 mins.
I am taking approximately 3 mins in insertion sort and 5 mins in selection sort. It is certainly something I can improve. My first speed goal is to write them under 60 seconds.
33_P
2nd - 4th writing of selection sort (C)
#include <stdio.h>
#define N 10
int main(int c,char* v[])
{
int A[N] = {3, 5, 7, 1, 2, 6, 8, 9, 10, 0};
int i,j,imin,t;
for(j=0;j<N-1;j++){
imin = j;
for(i=j+1;i<N;i++)
if(A[i]<A[imin])
imin=i;
if(j!=imin){
t=A[j];
A[j]=A[imin];
A[imin]=t;
}
}
for(i=0;i<N;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}
#define N 10
int main(int c,char* v[])
{
int A[N] = {3, 5, 7, 1, 2, 6, 8, 9, 10, 0};
int i,j,imin,t;
for(j=0;j<N-1;j++){
imin = j;
for(i=j+1;i<N;i++)
if(A[i]<A[imin])
imin=i;
if(j!=imin){
t=A[j];
A[j]=A[imin];
A[imin]=t;
}
}
for(i=0;i<N;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}
This is the version I decided to use at the end. My 2nd write blews. Why? I failed to apply my mental checking *before* the code is compiled. I am still too impatient. My 3rd and 4th are good.
Lesson: if you already have an algorithm in your head which is refined, when learning a new algorithm, try to apply things you learn from these algorithms. e.g. I know insertion sort. Why didn't I use my technique in insertion sort to check my selection sort?
33_P
Saturday, April 23, 2011
Friday, April 22, 2011
Status at 20110422 (c)
Solved 2.2-3 and 2.2-4. Both are not difficult. This reminds me though. I need to analyze the worst case and average case analysis of insertion sort and selection sort.
My exercise read will move on once I do that.
Browse read: 200/1144
Exercise up to 2.3-1
33_P
My exercise read will move on once I do that.
Browse read: 200/1144
Exercise up to 2.3-1
33_P
Status at 20110422 (b)
I was able to break my reading block on heap sort. Then I cruised through chapter 7 on quick sort and come to chapter 8. I believe 6, 7, 8 are advanced topics which require good background in theory. So reread is necessary. There are topics which I feel blurry - that include priority queue and the analysis of quick sort. Those are very important but not easy to fully understand.
I also reread the material about merge sort and Chapter 3 again. Now I get them. My mind just wasn't ready for them. In fact, this is a very good book to own because once you finished Chapter 2 and drill it seriously. You already know 4 basic comparison sorting algorithm by heart, one even has performance in theta(nlogn).
Browse Read: 200/1144
Exercises up to 2.2-3
33_P
(Correction: there are only 1144 pages in the 3rd edition.)
I also reread the material about merge sort and Chapter 3 again. Now I get them. My mind just wasn't ready for them. In fact, this is a very good book to own because once you finished Chapter 2 and drill it seriously. You already know 4 basic comparison sorting algorithm by heart, one even has performance in theta(nlogn).
Browse Read: 200/1144
Exercises up to 2.2-3
33_P
(Correction: there are only 1144 pages in the 3rd edition.)
Status at 20110422
Finished 2.2-2 on paper. My selection sort pseudocode took 10 lines. That is 2 lines and 1 variable more than necessary. I am going to improve it before I start practice writing it.
So far,
Browse Read: 159/1155
Exercises up to : 2.2-3
33_P
So far,
Browse Read: 159/1155
Exercises up to : 2.2-3
33_P
Practice in insertion sort
After some drilling and practice (33 times so far) of the basic insertion sort on pseudocode, c, perl and python. I start to feel mildly comfortable with the algorithm. This kind of exercises are very useful. In fact, looking back, a deep understanding of one single algorithm, even if it is very simple, seems to sharpen my mind more than browsing thousands of algorithms. It tends to expose holes in your mind.
It is some progress, I will follow my own goal on each algorithm. To grok the algorithm : That is to think through it, to write the correct program without the need of compiler/interpreter, to understand it fully theoretically and to know all known extensions of it.
Of course, at the end of the day, if I can propose a better one, I will be ultimately satisfied.
For insertion sort, I am still far far away. The next thing I plan to do are
1, Learn the basic variations of insertion sort.
2, Do the same practice on selection sort.
3, Do the same practice of linear search.
1 is trivial. In C, there are around 3 possible code variations floating around on the web just for straight insertion sort. Each of them has their merit. One important variation is the sentinel version. It is known to be faster. (Why?)
It's also important to understand the some more advanced version of insertion sort, such as binary insertion sort, shell sort and the new kid, library sort. Those..... by themselves should be treated with respect and need to be practiced separately. More on those later. But part of the reason I will do 3 is because it will be the bridge of doing binary search. It will be two foundations before I start to do a binary insertion sort.
33_P
It is some progress, I will follow my own goal on each algorithm. To grok the algorithm : That is to think through it, to write the correct program without the need of compiler/interpreter, to understand it fully theoretically and to know all known extensions of it.
Of course, at the end of the day, if I can propose a better one, I will be ultimately satisfied.
For insertion sort, I am still far far away. The next thing I plan to do are
1, Learn the basic variations of insertion sort.
2, Do the same practice on selection sort.
3, Do the same practice of linear search.
1 is trivial. In C, there are around 3 possible code variations floating around on the web just for straight insertion sort. Each of them has their merit. One important variation is the sentinel version. It is known to be faster. (Why?)
It's also important to understand the some more advanced version of insertion sort, such as binary insertion sort, shell sort and the new kid, library sort. Those..... by themselves should be treated with respect and need to be practiced separately. More on those later. But part of the reason I will do 3 is because it will be the bridge of doing binary search. It will be two foundations before I start to do a binary insertion sort.
33_P
33rd writing of insertion sort (C)
Nailed it. Feel more natural. It's better to time myself from now on.
33_P
33_P
Thursday, April 21, 2011
31,32 writing of insertion sort (python)
Ah. Got the and syntax is incorrect. But finally get back to the game of python.
Ah. Training yourself on one move can be frustrating.
Ah. Training yourself on one move can be frustrating.
29th writing of insertion sort (perl)
Still got it wrong. Changed > to = in the second condition. Should spot-check every condition before interpretation.
26th writing of insertion sort (C)
Bad. When I initialize the array, the elements mismatch. This is perhaps the first time I hit this problem.
33_P
33_P
Wednesday, April 20, 2011
25th writing of insertion sort (C, with for-while transformation)
instead of
for(j=1;j<N;j++){
k = A[j];
i = j-1;
while(i>=0&&A[i]>k){
A[i+1]=A[i];
i--;
}
A[i+1]=k;
}
one can do while-for transformation.
for(j=1;j<N;j++){
for(i=j-1,k=A[j];i>=0 && A[i]>k;A[i+1]=A[i],i--);
A[i+1]=k;
}
It is shorter but it's less clear.
for(j=1;j<N;j++){
k = A[j];
i = j-1;
while(i>=0&&A[i]>k){
A[i+1]=A[i];
i--;
}
A[i+1]=k;
}
one can do while-for transformation.
for(j=1;j<N;j++){
for(i=j-1,k=A[j];i>=0 && A[i]>k;A[i+1]=A[i],i--);
A[i+1]=k;
}
It is shorter but it's less clear.
23rd writing of insertion sort (perl)
Bad: The print was written within the loop. Not my intention. The sorting is correct though.
33_P
33_P
First writing of Selection sort (TCRC Pseudocode)
I started to feel mildy confident about insertion sort. So I move on to write my first version of selection sort. (i.e. Also solved 2.2.2, need to put in on paper).
My answer is two-line longer compare to solution I can found on-line. Too bad, let's refine it later.
33_P
My answer is two-line longer compare to solution I can found on-line. Too bad, let's refine it later.
33_P
More about insertion sort
From Wikipedia, learned couple of more things about insertion sort.
1, It is stable. That is the key with the same value will not change its order. (Consider line 4 second comparison, what if two values are the same?)
2, It is adaptive. You just need to understand the best case scenario to get a feeling of it. I don't want to get into the math though. (Since I don't know.)
3, Other than the form I saw in TCRC, there is also a sentinel form of the algorithm. Always look for a different form of the algorithm. Some people will call that form as "straight insertion sort".
33_P
1, It is stable. That is the key with the same value will not change its order. (Consider line 4 second comparison, what if two values are the same?)
2, It is adaptive. You just need to understand the best case scenario to get a feeling of it. I don't want to get into the math though. (Since I don't know.)
3, Other than the form I saw in TCRC, there is also a sentinel form of the algorithm. Always look for a different form of the algorithm. Some people will call that form as "straight insertion sort".
33_P
21st time of insertion sort writing(C)
Get it right.
This makes you compare program writing as playing an Arcade shooting game. Equally difficult but equally understated.
33_P
This makes you compare program writing as playing an Arcade shooting game. Equally difficult but equally understated.
33_P
20th writing of insertion sort (C)
Get it right. Learned something:
-Check the number of lines if it is what you expect.
-Of course, ultimately you want to write one which is formatted but that can be pre-calculated as well.
33_P
-Check the number of lines if it is what you expect.
-Of course, ultimately you want to write one which is formatted but that can be pre-calculated as well.
33_P
17-19th writings of insertion sort (C)
Had lunch, try again.
17th: missed i=j-1;
18th: when print, print i instead of A[i]. Wow 3rd time.
19th: get it right.
That's why not many people can treat programming as arcade. Even a simple game like insertion sort is not easy to play.
33_P
17th: missed i=j-1;
18th: when print, print i instead of A[i]. Wow 3rd time.
19th: get it right.
That's why not many people can treat programming as arcade. Even a simple game like insertion sort is not easy to play.
33_P
My many writings of insertion sort (so far 17)
Several things I learnt:
- It is very important to write code on paper.
- It is very important to try to get the program right first time. Try not using the compilation warnings to guide you. It gives you a lot of mileage in future.
- In the later writing, not only you should see the algorithm, you should see all the potential trap when you write the algorithm.
- Most importantly, if you spend time on it, the time you spent is actually little.
17th writing of insertion sort (C)
Get it right the first time.
Of course, all these writings are all start from scratch. It's like you retype a command.
Another discovery: these kinds of practice doesn't take time at all. Why not?
Of course, all these writings are all start from scratch. It's like you retype a command.
Another discovery: these kinds of practice doesn't take time at all. Why not?
13-16th writings (C) of insertion sort
From the pseudocode to one particular language, it always takes some time to get things right in your head. What were my mistakes?
13th: when I try to print the array, I printed the index.
14th: include <stdio>, rather than <stdio.h>
15th: when I try to print the array, I printed the index.
16th: get it right.
How alarming it is to make the same mistake twice?
33_P
13th: when I try to print the array, I printed the index.
14th: include <stdio>, rather than <stdio.h>
15th: when I try to print the array, I printed the index.
16th: get it right.
How alarming it is to make the same mistake twice?
33_P
Tuesday, April 19, 2011
Insertion sort: thinking
1 for j = 2 to N
2 key = A[j]
3 i = j-1
4 while i > 0 and A[i] > key
5 A[i+1] = A[i]
6 i = i -1
7 A[i+1] = key
Now ask yourself this.
1, Line 1, why not j =1 to N?
2, Line 4, why not A[i+1]? What would happen if you do that?
3, Line 7, what would happen if you do A[i] = key?
2 key = A[j]
3 i = j-1
4 while i > 0 and A[i] > key
5 A[i+1] = A[i]
6 i = i -1
7 A[i+1] = key
Now ask yourself this.
1, Line 1, why not j =1 to N?
2, Line 4, why not A[i+1]? What would happen if you do that?
3, Line 7, what would happen if you do A[i] = key?
12th writing of insertion sort in perl
Bad. Mostly language specific problem:
1, $i -> i
2, you can't do my $i,$j,$key, you can only do something like my ($i,$j,$key)
33_P
1, $i -> i
2, you can't do my $i,$j,$key, you can only do something like my ($i,$j,$key)
33_P
9th, 10th (C), 11th (C) writing of insertion sort
I thought I was right. In fact. I made a fatal mistake in line 6.
I wrote A[i] = key.
instead of A[i+1] = key.
Just think what happens when the while loop exits?
33_P
I wrote A[i] = key.
instead of A[i+1] = key.
Just think what happens when the while loop exits?
33_P
8th Writing of insertion sort
Failure: Though the detail up to the algorithm is correct. But I didn't anticipate how much space it will take.
Of course if the pseudocode only takes 7 lines, you just need to count how many lines you need for double curly bracket.
Got to be good at it!
33_P
Of course if the pseudocode only takes 7 lines, you just need to count how many lines you need for double curly bracket.
Got to be good at it!
33_P
7th Writing in insertion sort (C)
Not perfect. The algorithm is ok. But to be good, you can't write code with any mistakes on paper.
-What was my mistake?
33_P
-What was my mistake?
- Mistaken stdlib as stdio for the library of print.
- #define -> #defined
- printf -> print
- In C-array, you naive-initialize it like A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
- Contrast this to perl
33_P
6th writing of insertion sort
Good again.
What did I get though by such repetition? Now it starts to be the tidbits. Every statement has a meaning, has a why. You also want to think about the variations of the algorithm.
What if it is zero-based index? What if one makes a mistake in a certain symbol? What if one change the order of the code?
How to improve it? How to improve in a certain language?
33_P
What did I get though by such repetition? Now it starts to be the tidbits. Every statement has a meaning, has a why. You also want to think about the variations of the algorithm.
What if it is zero-based index? What if one makes a mistake in a certain symbol? What if one change the order of the code?
How to improve it? How to improve in a certain language?
33_P
Reminder
Just want to remind myself this,
what are the interesting review questions for insertion sort? Of course, I want to collect a bunch of these questions for every algorithm.
what are the interesting review questions for insertion sort? Of course, I want to collect a bunch of these questions for every algorithm.
Status at 20110419
Finished Section 6.2 and 6.3. When you think through it, these stuffs is actually not that tough. The math in Section 6.3 worths some time to review. I will count myself went up to p. 159.
Also finished some trivial exercises in my head. That includes 6.1-7, 6-2.3 and 6-2.4. Needs to put in on paper of course.
Browse Read: 159/1155
Exercises up to Section 2.2-2
Exercises which are finished but not on paper: 2.2-4, 6.1-7, 6.2-3 and 6.2-4.
Also finished some trivial exercises in my head. That includes 6.1-7, 6-2.3 and 6-2.4. Needs to put in on paper of course.
Browse Read: 159/1155
Exercises up to Section 2.2-2
Exercises which are finished but not on paper: 2.2-4, 6.1-7, 6.2-3 and 6.2-4.
Monday, April 18, 2011
Correctness of programming
Sometimes you can have powerful conviction when you are doing fundamental training for yourself. What I did today was to read he first few chapters of Gries' "Science of Programming".
For good and bad reasons, I have voluntarily/unvoluntarily programming for many years. Unlike many wiz kids, I wasn't natural in terms of computers. My understanding of programming largely comes from "intuition".
That's bad.
In fact, that could result in the worst type of programming technique - debugging by print. It is the worst because you want to dump the guts of the program and you think that means you know what's going on. Your feeling, instead of logic, are playing a role.
What's the problem? Well sometimes you can't print everything. If the bad logic occurs in the inner loop, then you can potentially have display messages which cannot be analyzed.
The next worst thing is to program by debugger. This is better than programming by print. But still, when the programming is written, weren't you able to know where the potential issue come from already?
Then I start to meet good programmers. The thing is most of them put much time upfront. Instead of spending time in debugging the program. Since they know, if you would like to be efficient in long run. This is the way to go.
I read TCRC and then Gries. Perhaps later I will read DEK (or finish reading.....). Then I realize how much time I have been wasting in debugging. That's not a bad conviction. In a way, it is empowering. It's a bit like you start to use a certain emacs macro correctly without retyping. Or a unix command without manning the command. Or start to use perl one-liner instead of a combination of awk/grep/sed. This is powerful.
33_P
For good and bad reasons, I have voluntarily/unvoluntarily programming for many years. Unlike many wiz kids, I wasn't natural in terms of computers. My understanding of programming largely comes from "intuition".
That's bad.
In fact, that could result in the worst type of programming technique - debugging by print. It is the worst because you want to dump the guts of the program and you think that means you know what's going on. Your feeling, instead of logic, are playing a role.
What's the problem? Well sometimes you can't print everything. If the bad logic occurs in the inner loop, then you can potentially have display messages which cannot be analyzed.
The next worst thing is to program by debugger. This is better than programming by print. But still, when the programming is written, weren't you able to know where the potential issue come from already?
Then I start to meet good programmers. The thing is most of them put much time upfront. Instead of spending time in debugging the program. Since they know, if you would like to be efficient in long run. This is the way to go.
I read TCRC and then Gries. Perhaps later I will read DEK (or finish reading.....). Then I realize how much time I have been wasting in debugging. That's not a bad conviction. In a way, it is empowering. It's a bit like you start to use a certain emacs macro correctly without retyping. Or a unix command without manning the command. Or start to use perl one-liner instead of a combination of awk/grep/sed. This is powerful.
33_P
Feynman and Alcohol
I read an article by Feynman, to paraphase him, he basically said he would not drink too much because he wants to do physics.
If anyone would like to work with their brain, indeed, keep alcohol away from you.
33_P
If anyone would like to work with their brain, indeed, keep alcohol away from you.
33_P
5th writing of the insertion sort
Got it right! I start to see the nuts and bolts of the 7 lines.
Also more importantly, why it is 7 but not 6.
33_P
Also more importantly, why it is 7 but not 6.
33_P
Language Learning and Programming
For a while I believed I have absolutely no talents in programming. Same could be said for language learning. Somehow I just don't think I am natural on anything which requires writing.
But then two events happened, I was able to read a large amount of books and I was able to read in Spanish in a short period of time (less than half a year). Admittedly, these are not things people can't do better. Though, it does show I have minimal amount of talents on things I felt I had none.
I hope the same story could be applied to programming. After all, to learn one thing, the key is to practice and practice. Intelligence helps, but persistence is the real key.
33_P
But then two events happened, I was able to read a large amount of books and I was able to read in Spanish in a short period of time (less than half a year). Admittedly, these are not things people can't do better. Though, it does show I have minimal amount of talents on things I felt I had none.
I hope the same story could be applied to programming. After all, to learn one thing, the key is to practice and practice. Intelligence helps, but persistence is the real key.
33_P
Status at 20110418 (b)
Finished 2-2.1 . Not something difficult. Also looked at 2-2.4. I don't think I know the answer on top of my head but you can call it a kind of Zen's questions.
When I write it down on paper I would report.
Browse read : 155/1155
Exercise up to 2-2.2
33_P
When I write it down on paper I would report.
Browse read : 155/1155
Exercise up to 2-2.2
33_P
Status at 20110418
After couple of days of tiring housework, I decided to work on the book slowly again. Just finished Section 6.1 and I start to feel comfortable about the terminology of heap sort.
Another interesting thing happens in my mind, I start to hope to do the next exercise. Just like when you are young and you are see a Math problem books. You want to solve all problems in it. It's not much different here.
Sometimes I think I might be just the programmer version of Julie in Julie and Julia. Well, I guess real-life is always difficult. It's just difficult in different ways for different people.
Browse Read: 154/1155
Exercise up to : 2.2-1
33_P
Another interesting thing happens in my mind, I start to hope to do the next exercise. Just like when you are young and you are see a Math problem books. You want to solve all problems in it. It's not much different here.
Sometimes I think I might be just the programmer version of Julie in Julie and Julia. Well, I guess real-life is always difficult. It's just difficult in different ways for different people.
Browse Read: 154/1155
Exercise up to : 2.2-1
33_P
Thursday, April 14, 2011
4th writing of insertion sort
Preciseness is still a problem. It turns out I wrote something like. (Assuming non-decreasing order)
Listing 1
1 for j = 2 to N
2 key = A[j]
3 i = j -1
4 while i > 0 and A[i] > key
5 A[i+1] = A[i]
6 A[i] = key
7 i = i -1
There's nothing wrong with this code but this is not strictly insertion sort. At line 6, key is exchanged when shifting of the array to right. This is not necessary because we can do (as in TCRC)
Listing 2
1 for j = 2 to N
2 key = A[j]
3 i = j -1
4 while i > 0 and A[i] > key
5 A[i+1] = A[i]
6 i = i -1
7 A[i]= key
This reduces an extra operation in the inner loop.
I also rewrite the C and perl version of the insertion sort. It is a breeze though it is still easy to make mistakes. This type of exercise is great to be done routinely.
* Got to remind myself to refresh on Python and Java. I hope that everytime I write an algorithm, I can think through in at least these 4 langauges.
33_P
Listing 1
1 for j = 2 to N
2 key = A[j]
3 i = j -1
4 while i > 0 and A[i] > key
5 A[i+1] = A[i]
6 A[i] = key
7 i = i -1
There's nothing wrong with this code but this is not strictly insertion sort. At line 6, key is exchanged when shifting of the array to right. This is not necessary because we can do (as in TCRC)
Listing 2
1 for j = 2 to N
2 key = A[j]
3 i = j -1
4 while i > 0 and A[i] > key
5 A[i+1] = A[i]
6 i = i -1
7 A[i]= key
This reduces an extra operation in the inner loop.
I also rewrite the C and perl version of the insertion sort. It is a breeze though it is still easy to make mistakes. This type of exercise is great to be done routinely.
* Got to remind myself to refresh on Python and Java. I hope that everytime I write an algorithm, I can think through in at least these 4 langauges.
33_P
Status at 20110414
My reading goes slowly. Finished all exercises at 2-2. Writing proofs and solving exercises are always mind-provoking. I also found that seriously read through heap sort takes some mental power.
Ex 2-1.3 is a trivial problem with a very simple pseudocode answer. Though writing a good proof is a tougher problem. I might put my proof here and see how wrong it is.
Ex 2-1.4 reminds me my class in logic design. At the end of the day, my solution still requires defining sub-routines of XOR and NOT. It seems to me they are necessary.
-Browse reading : 150/1144.
-Exercise up to 2-2.1.
Ex 2-1.3 is a trivial problem with a very simple pseudocode answer. Though writing a good proof is a tougher problem. I might put my proof here and see how wrong it is.
Ex 2-1.4 reminds me my class in logic design. At the end of the day, my solution still requires defining sub-routines of XOR and NOT. It seems to me they are necessary.
-Browse reading : 150/1144.
-Exercise up to 2-2.1.
Friday, April 8, 2011
Status at 20110408
* Spent 15 minutes to read through Chapter 5. Also learned what is hiring problem.
* Also read through p. 147 to p. 150. I guess I will cruise through the sorting Chapters. Since they are more interesting.
* I start to see why so many are big fans of writing beautiful algorithm. As a scientific pursuit, algorithmic study is not a bad one.
* So far,
First Read: 150/1144
Exercise Read: 2-1.3
33_P
* Also read through p. 147 to p. 150. I guess I will cruise through the sorting Chapters. Since they are more interesting.
* I start to see why so many are big fans of writing beautiful algorithm. As a scientific pursuit, algorithmic study is not a bad one.
* So far,
First Read: 150/1144
Exercise Read: 2-1.3
33_P
Thursday, April 7, 2011
Status at 20110407
-Browse reading : 114/1144.
-Exercise up to 2-1.3.
The part which taught about Master algorithm is very worthwhile to learn it by heart.
33_P
-Exercise up to 2-1.3.
The part which taught about Master algorithm is very worthwhile to learn it by heart.
33_P
Google Code Jam
Saw this, http://code.google.com/codejam/contests.html
Still weak in terms of programming strength though. Though, somehow you build up a feeling when you drill programming books. We will see how it goes.
33_P
Still weak in terms of programming strength though. Though, somehow you build up a feeling when you drill programming books. We will see how it goes.
33_P
Wednesday, April 6, 2011
Loop Invariant
I start to learn what a loop invariant is and I wish I learned it long time ago. It is a good habit to always think like this so that one can *prove* one is doing the right thing.
Intuition can help but it will fail when situation is complicated. Besides, a loop invariant type of thinking can simply the loop and make it short. (I like short program a lot.)
Intuition can help but it will fail when situation is complicated. Besides, a loop invariant type of thinking can simply the loop and make it short. (I like short program a lot.)
Status at 20110406
Finally have time to think through 2.1-3 and 2.1-4. 2.1-3 is in the stage of putting on paper. 2.1-4, though, I still only have a table look up solution, I hope to think out a good solution.
Immersing in algorithm starts make me feel more "in the flow" in work (learning Spanish and Japanese doesn't hurt neither), exactness is a key in this line of study.
33_P
Immersing in algorithm starts make me feel more "in the flow" in work (learning Spanish and Japanese doesn't hurt neither), exactness is a key in this line of study.
33_P
Subscribe to:
Posts (Atom)