Introduction to Algorithms No.9

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 a running time.
-------------------------------------------------
Big O-notation determines the upper bound of a running time. Big Omega-notation the lower. Theta-notation the both.
-------------------------------------------------

Chapter 4. Divide and Conquer
I have learnt how to get a recursion of a running time of an algorithm. And I have also learnt how to calculate the recursion and get the running time. Taking merge-sort, I have the following recursion:
-------------------------------------------------
T(n) = T(floor(n/2)) + T(ceil(n/2)) + f(n), f(n) in Theta(n).
-------------------------------------------------
Let's think about the recursion in terms of "Divide and Conquer" (and Combine). T(n) is the (worst) running time of merge-sorting a n-size array. T(floor(n/2)) + T(ceil(n/2)) is the summation of the  running time of two DIVIDED arrays. And that sorting of the each array is called CONQUER. The last item, f(n) (in Theta(n)), is the running time of COMBINE. In other words, the sorting of the two sorted arrays takes f(n) time. And I have learnt how to solve the recursion and get the running time.

Chapter 5. Probabilistic Analysis and Randomized Algorithms
I have learnt the foundation of probabilistic analysis and how to describe a uniform distribution in programming.



Thank you.




Comments

Post a Comment

Popular posts from this blog

Introduction to Algorithms No.3

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.
Read more

Introduction to Algorithms No.7

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
Read more

Introduction to Algorithms No.10

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.
Read more