u & ri memo

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.