u & ri memo

Hello. I am busy. This is quick-sort: https://github.com/uriha421/introduction_to_algorithms/blob/master/II_Sotring_and_Order_Statistics/quick_sort.c I have enjoyed divide-and-conquer algorithms. I will not write articles often. Because I must prepare for Bitcoin Edge. https://bitcoinedge.org Bye~

Hello. This is the heap-sort: https://github.com/uriha421/introduction_to_algorithms/blob/master/II_Sotring_and_Order_Statistics/heap_sort.c I do not have enough time to read the textbook. Because I have something else to do, including javascript. I will explain the heap-sort tomorrow. Thank you.

Hello. I have learnt introduction in "II Sorting and Order Statistics." Sorting algorithms and order statistics really matters in computer engineering, which encourages me to learn algorithms. The sorting algorithms have heap-sort, quick-sort, counting-sort, radix-sort, and bucket-sort. The order statistics means searching the n-th smallest number in a array. Tomorrow, I will tell you heap-sort. Thank you.

Hello. Today I have completed "I. Foundation." And I have proceeded to "II. Sorting and Order Statistics." Today, I will briefly summarize what I have learnt in "I. Foundation." Chapter 1. The Roles of Algorithms in Computing I have learnt the significance of algorithms. Good algorithms are as important as good computer. As computer advances, we should understand algorithms the more. Chapter 2. Getting Started I have learnt basic sorting algorithms such as insertion-sort, selection-sort, and merge-sort. And I have also learnt "loop-invariant." An (sorting) algorithm (of an array A) called "loop-invariant" is: ------------------------------------------------- At the start of each iteration of the loop (e.g. for n in (0, N)), the subarray A[0...n] consists of the elements originally in A[0...n] , but in sorted order. ------------------------------------------------- Chapter 3. Growth of Functions I have learnt how to describe

Hello. I have completed Chapter 4, "Divide and Conquer." I have learnt how to get the running time of divide-conquer algorithms. First, I can make a recursion of a divide-conquer algorithm. Taking merge-sort, the recursion is as follows: T(n) = T(floor(n/2)) + T(ceil(n/2)) + Theta(n) Then, I can prove the following proposition: T(n) in Theta(n*log(n)) ------- f(n) in O(g(n)) <=> there exists a positive constant c such that f(n) <= c * g(n) for enough large n. f(n) in Omega(g(n)) <=> there exists a positive constant c such that f(n) >= c * g(n) for enough large n. f(n) in Theta(g(n)) <=> f(n) in O(g(n)) and f(n) in Omega(f(n)). ------- In other words, I can prove: ------- For T(n) = T(floor(n/2)) + T(ceil(n/2)) + Theta(n), there exist two positive constants c_1, c_2 such that c_1*n*log(n) <= T(n) <= c_2*n*log(n) for enough large n. ------- Therefore, I can conclude that the running time of merge-sort is Theta(n*log(n)). Thank

Hello. Today, I have started Chapter 4, "Divide and Conquer." And I have learnt "The maximum-subarray problem." Maximum-subarray algorithm can solve that problem. Suppose you have time series of stock prices, such as (5 10 4 2 3 7 1 5 6 2). You are at time 1 now. The stock price is 5 now. You know the future stock price (5 10 4 2 3 8 1 3 6 2). Then when will you buy the stock and sell it? The answer is, you should buy it at time 4 and sell it at time 6. Then you get 6. I have written two codes, which run with different running time. One algorithm runs with Theta(n^2). The other runs with Theta(n*log(n)). Therefore, the latter runs faster. The two algorithms are as follows: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/maximum-subarray_problem_slow.c https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/maximum-subarray_problem_fast.c You will be surprised to recognize that the slow program is mu

Hello. I have completed the Chapter 3, "Growth of Functions." I would like to write what I have learnt as usual. But I cannot. Because few people may understand mathematical analysis and it takes a lot of time to compile LaTex-code in blogger. How do I continue this blog? The following chapter must require the understanding of mathematical analysis. So I will find it hard to explain it. Tomorrow, I will read Chapter 4. After that, I will decide what to write. Becoming a good engineer needs the knowledge of many fields, I have recently felt. For example, micro economics, financial engineering, and statistics. Many things to study:( Thank you.

Hello. Long time not to see. I enjoyed summer vacation... This is the merge-sort algorithm: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/merge_sort.c Merge-sort is one of divide-and-conquer algorithms. It may be important to understand the concept. Let me explain it. Divide means cutting a problem into some small ones. Conquer means solving the divided problems. Then we combine the divided problems and we solve the entire problem. In merge-sort, divide is: <1 2 8 7 6 3 5 4>   --->   <1 2 8 7> <6 3 5 4>  Conquer is: <1 2 8 7> <6 3 5 4>   --->   <1 2 7 8> <3 4 5 6> Combine is: <1 2 7 8> <3 4 5 6>   --->   <1 2 3 4 5 6 7 8> Now let T(n) be the running time of sorting a n-size array. Then, we have the following recursion: T(n) = c, (if n = 1), 2T(n/2) + O(n), (if n > 1). (2T(n/2) is the running time of conquer. O(n) is the running time of combine here.) In concl

Hello. I have learnt and written the selection sort: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/selection_sort.c I have also learnt the running time of an algorithm. The running time means how long it takes to execute an algorithm. It is clear that it depends on the size of an input. It also depends on the input itself. Let's take an example of the insertion-sort algorithm. If the input array is already sorted, the running time is clearly shorter than the average running time. On the other hand, the input is reversely sorted, the running time is much longer. And it is more important to think about the running time in the worst case. Because ... I have to go to bed :( See you tomorrow.

Hello. I would have completed Chapter 2. But I have not. It takes a lot of time to think about and write algorithms. These are what I have finished writing today: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/searching_problem.c https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/add_two_n-bit_integers.c The first program is about a searching problem. It receives an array and a number that the array has, as an input. Like (5, 3, 4, 2, 1), 4. Then it returns where the number is, as an output, 3. The second program is about adding two n-bit integers. It receives two n-bit integers as an input. Like (11010), (11100). Then it returns the sum of those integers as an output. Like (110110). In addition, I have learnt "loop invariant." I would like to tell you here. But it is difficult to explain. I will show you it some other time :( Thank you.

Hello. Today, I have learnt "Insertion-Sort Algorithm" in Chapter 2, "Getting Started." I have written a C program of the insertion-sort algorithm. And I have learnt how to use Git and GitHub. So I can show you this C program in GitHub. https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/insertion_sort.c I have not read all of Chapter 2 yet, because I have learnt GitHub today. But I will complete Chapter 2 tomorrow. Thank you.

I have decided to read " Introduction to Algorithms ." This is one of the most famous textbook on algorithms. I will write what I think when I read it. Today, I will write an article on Chapter 1 Chapter 1 refers to "The Role of Algorithms in Computing." The points are as follows: - An algorithm receives an input and returns an output. - Algorithms play an important role in information technology. - A good algorithm on a bad computer may exceed a bad algorithm on a good computer. Good algorithms are as important as a good computer! Thank you.

Hello. I am a software engineer. I live in Tokyo, Japan. I have started this blog for the following reasons: - show my skills - note to self - practice writing English Thank you.