Two sum problem
2016년 2월 18일 목요일
2009년 8월 3일 월요일
Dumber's Computer Alogrithm - 1. Things to know before learning computer algorithms
Chapter 1-2 discuss why computer algorithms are important and introduces the basic mathmatical notations by taking example of two basic sorting algorithms: Insertion sort and merge sort. I skipped details of why computer algorithms are important since I am writing this posting because I did understand the computer alogrithms are important!!
1. First exampe- Insertion sort
Insertion sort can be compared to sorting cards in hand. Imagine you have a deck of cards on the desk and you open one card at a time from the top of the deck and move it to your left hand. What you need to do is that every time you open a new card from the deck you want to insert the card to the appropriate positions between cards in your left hand to sort them in an ascending order, where leftmost card is the smallest one and rightmost one is the larget one in your hand.
Let's see why would you do to do this step by step.
Step 1. expose the first card on the top of the deck of cards on the desk and move it to your left hand. You did not have any card by far so you don't have to do anything. Let say you picked "3" (For simplicity, we assume a number on the card is unique among cards on the desk)
Step 2. expose the second card (let's say it has "2") from a deck of cards and move it to your left hand. This time you should compare a new card with an existing card to see if which one is the smallest. Since "2" is smaller than "3", you insert the card to the left of the existing card.
Step 3. expose the third card (it has "1" this time) and you examine existing ones. You insert a new card to the left of all existing cards in your hand.
Step 4. you repeat steps above until all the cards on the desk are exposed and moved to your left hand. After all, you will have a deck of playing cards sorted in an ascending order.
Given simple steps shown above, let's think how we would mimic these steps in a computer program.
Each card can be represented as a numerical digit. How can a deck of cards be represented then?
How about an array containing numerical digits, each of which is unique among others in the array.
Wait a minute, how can you insert a new number between two numbers in an array just like inserting a new card between existing cards in the hand.
We can't unless we copy a number which is in the position where a new number is inserted to a next empty slot to the left. If there are more than one numbers in the array. we should copy them one slot to the left from the largest number to the smallest number which still larger than a new number.
Ok, now we are ready to rewrite the sorting steps above.
This book suggests to use a pseudo code to describe an algorithm. Here is how a insertion sort be described in pseudo code.
Insertion sort(A)
1: for i = 2; i < length[A] ; i++
2: key = A[i]
3: j = i -1
4: while j > 0 && A[j] > key
5: if A[j] > key
6: A[j+1] = A[j]
7: j = j -1
8: A[j + 1] = key
huh.. I got sweat again. This gives me headache always.
Let's see how this pseudo code can be comparied to a "sorting playing card" scenario shown earilier.
In "sorting playing card" scenario, we picked the first card from the top of a card deck. In the pseudo code (line 1), i starts from 2 to represent the case where one card is already in the deck(Step 1) and a second card is picked.
What should be done from now on, is to compare a new number, (key in line 2) with existing numbers already expose. Since this pseudo code sorts numbers in the same array, numbers positioned eariler than a "key" are those already exposed.
From line 4 to 8, key is compared with existing numbers starting from the largest one to fine an appropriate place for "key" to be inserted. If currenly examined number is larger than a key (line 5: A[j+1] = A[j]), the number is moved to the left (line 6: A[j+1] = A[j]). After all a variable, j points to the place where numbers on the left of this are smaller than key. We finally insert a "key" to the right place (line 8: A[j + 1] = key) and expose a next number (line 1)
2. Loop invariants and correctness of algorithm
So far so good, now I learned how to write a pseudo code to describe a algorithm. It seems pretty straightforward. However, here a tricky part begins.. I should be able to prove that my pseudo code is correct. New term, Loop invariant, which seems daunting, is introduced.
In short, Loop invariant is a truth statement that is true before/during/after a loop.
1. First exampe- Insertion sort
Insertion sort can be compared to sorting cards in hand. Imagine you have a deck of cards on the desk and you open one card at a time from the top of the deck and move it to your left hand. What you need to do is that every time you open a new card from the deck you want to insert the card to the appropriate positions between cards in your left hand to sort them in an ascending order, where leftmost card is the smallest one and rightmost one is the larget one in your hand.
Let's see why would you do to do this step by step.
Step 1. expose the first card on the top of the deck of cards on the desk and move it to your left hand. You did not have any card by far so you don't have to do anything. Let say you picked "3" (For simplicity, we assume a number on the card is unique among cards on the desk)
Step 2. expose the second card (let's say it has "2") from a deck of cards and move it to your left hand. This time you should compare a new card with an existing card to see if which one is the smallest. Since "2" is smaller than "3", you insert the card to the left of the existing card.
Step 3. expose the third card (it has "1" this time) and you examine existing ones. You insert a new card to the left of all existing cards in your hand.
Step 4. you repeat steps above until all the cards on the desk are exposed and moved to your left hand. After all, you will have a deck of playing cards sorted in an ascending order.
Given simple steps shown above, let's think how we would mimic these steps in a computer program.
Each card can be represented as a numerical digit. How can a deck of cards be represented then?
How about an array containing numerical digits, each of which is unique among others in the array.
Wait a minute, how can you insert a new number between two numbers in an array just like inserting a new card between existing cards in the hand.
We can't unless we copy a number which is in the position where a new number is inserted to a next empty slot to the left. If there are more than one numbers in the array. we should copy them one slot to the left from the largest number to the smallest number which still larger than a new number.
Ok, now we are ready to rewrite the sorting steps above.
This book suggests to use a pseudo code to describe an algorithm. Here is how a insertion sort be described in pseudo code.
Insertion sort(A)
1: for i = 2; i < length[A] ; i++
2: key = A[i]
3: j = i -1
4: while j > 0 && A[j] > key
5: if A[j] > key
6: A[j+1] = A[j]
7: j = j -1
8: A[j + 1] = key
huh.. I got sweat again. This gives me headache always.
Let's see how this pseudo code can be comparied to a "sorting playing card" scenario shown earilier.
In "sorting playing card" scenario, we picked the first card from the top of a card deck. In the pseudo code (line 1), i starts from 2 to represent the case where one card is already in the deck(Step 1) and a second card is picked.
What should be done from now on, is to compare a new number, (key in line 2) with existing numbers already expose. Since this pseudo code sorts numbers in the same array, numbers positioned eariler than a "key" are those already exposed.
From line 4 to 8, key is compared with existing numbers starting from the largest one to fine an appropriate place for "key" to be inserted. If currenly examined number is larger than a key (line 5: A[j+1] = A[j]), the number is moved to the left (line 6: A[j+1] = A[j]). After all a variable, j points to the place where numbers on the left of this are smaller than key. We finally insert a "key" to the right place (line 8: A[j + 1] = key) and expose a next number (line 1)
2. Loop invariants and correctness of algorithm
So far so good, now I learned how to write a pseudo code to describe a algorithm. It seems pretty straightforward. However, here a tricky part begins.. I should be able to prove that my pseudo code is correct. New term, Loop invariant, which seems daunting, is introduced.
In short, Loop invariant is a truth statement that is true before/during/after a loop.
Dumber's Computer Alogrithm - Purpose of these postings
Finally, I found time to open a computer algorithm book that was buried in the pile of books in my room. I stared brushing off my memory and learning from the basics.
The series of postings under the title, "Dumber's computer alogrithm" will include my own interpretation of a famous book, "Introducing to computer alogrithm". Reason why I use a word, "my own interpretation" is that I will write what I understood from this book in a way that might best serve my goal, " Simplify as much as possible to make them easy remember".
Therefore, many details such as mathmatical notations, theorem proofs may/ may not be including depending on whether I understood them well enough to rewrite them in this posting. If not they may be omitted.
You are advised in advance that this posting does not fully represent what were written in the original book, "Introduction to Computer Algorithm". For those who insists to pursue the gory details of the book, I posts the following link where you can purchase the book directly without wasting time in my blog.
http://www.amazon.com/s/ref=nb_ss_gw?url=search-alias%3Daps&field-keywords=MIT+introduction+to+computer+algorithms
The series of postings under the title, "Dumber's computer alogrithm" will include my own interpretation of a famous book, "Introducing to computer alogrithm". Reason why I use a word, "my own interpretation" is that I will write what I understood from this book in a way that might best serve my goal, " Simplify as much as possible to make them easy remember".
Therefore, many details such as mathmatical notations, theorem proofs may/ may not be including depending on whether I understood them well enough to rewrite them in this posting. If not they may be omitted.
You are advised in advance that this posting does not fully represent what were written in the original book, "Introduction to Computer Algorithm". For those who insists to pursue the gory details of the book, I posts the following link where you can purchase the book directly without wasting time in my blog.
http://www.amazon.com/s/ref=nb_ss_gw?url=search-alias%3Daps&field-keywords=MIT+introduction+to+computer+algorithms
2009년 8월 2일 일요일
I am a dummy learner!! Are there anyone like me?
I always gets sweat when reading a computer alogrithm. With all the mathmatical notations and equations explaining the correctness and efficiency of alogrithms, I just got overwhelmed.
In additions, I forgets what I learned so easily. Especially when it comes to computer algrothms and other theories, they just evaporates quickly after I manages to understand them after spending hours.
This blog is not for anyone else. It is for me to help me from revisiting the same old book or the website to refresh me memories about the computer alogrithms and theories.
However, if and only if there are others who have the same problem as me.
You may benefit from this blog.
In additions, I forgets what I learned so easily. Especially when it comes to computer algrothms and other theories, they just evaporates quickly after I manages to understand them after spending hours.
This blog is not for anyone else. It is for me to help me from revisiting the same old book or the website to refresh me memories about the computer alogrithms and theories.
However, if and only if there are others who have the same problem as me.
You may benefit from this blog.
피드 구독하기:
글 (Atom)
