It was harrowing to not be able to see you again.
There were impulsions, fluctuations, excitations during the last 4 years. In this time, all those things should be forgotten. Now I believe it is doomed. I think it would be better not to contact you again.
Merry Christmas and best wishes to you.
The problem is:
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
1.Sort the elements in S using merge sort.
2.Remove the last element from S. Let y be the value of the removed element.
3.If S is nonempty, look for z= x – y in S using binary search.
4.If S contains such an element z, then STOP, since we have found y and z such that x= y+ z. Otherwise, repeat Step 2.
5.If S is empty, then no two elements in S sum to x.
Step 1 takesΘ(n lg n) time. Step 2 takes Θ(1) time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm isΘ(n lg n). The following is my implement code:
Continue reading “Notes of Introduction to Algorithm(Exercise 2.3.7)”
I often went to the ZOJ(Zhejiang University Online Judge)site to do some exercise before I took part in the Zhejiang Province Programming Contest. Attending this activity gives me much joy and my fellows in the contest and our coach are both very kind.
It is not difficult to devise an algorithm that can find both the minimum and the maximum of n elements using Θ(n) comparisons. Simply find the minimum and maximum independently, using n – 1 comparisons for each, for a total of 2n – 2 comparisons.In fact, at most 3(n/2) comparisons are sufficient to find both the minimum and the maximum in the array of size n.We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
Continue reading “Select maximum and minimum using 3*(n/2) comparisons”
Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in Θ(n) time. Seems so fast? The answer is no. It just uses extra space to cut down the runtime. However I have extended the range to -k to k in the following implementation.
Continue reading “Notes of Introduction to Algorithm(Counting Sort)”
Recently I am reading the book CLRS Introduction to Algorithms, Second Edition. I find that I really hook on it! It’s a great book about the Algorithm and I think I will wirte some notes about reading the book and write some C/C++ code for the pseudo code on this book.
Quicksort is a sorting algorithm whose worst-case running time is Θ(n^2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(n lg n). Quicksort, like merge sort, is based on the divide-and-conquer method.
Continue reading “Notes of Introduction to Algorithm(Quick Sort)”
Unlike the mergesort and quicksort, heapsort doesn’t require massive recursion or multiple arrays to work and the time complexity of heapsort is O(n log(n)) . It utilizes a special data structure called heap. Before we take a look at the Heap sort algorithm, let’s explain the the (binary) heap data structure.
Continue reading “Notes of Introduction to Algorithm(Heap Sort)”
