Code Review - Counting Inversion

Dec. 30, 2016

Study the algorithm on code review:

Counting Inversions

Previous study:

Count inversions - Extended merge sort - 3 Lecture Notes Study

Goal:

1. Time complexity: O(n*) -> O(nlogn)

2. Review the process of analysis by following lecture notes, the recurrence relationship using divide conquer - T(n) = 2*(T/2) + O(n), and then, using the combinatorics - do some analysis on the time complexity.

Master Theorem - Get back to the basics!

Count inversions - Extended merge sort - 3 Lecture Notes Study

August 5, 2016 

Choose topic: extended merge sort
Algorithm: count inversions

count inversions - extended merge sort
1. http://jane4532.blogspot.ca/2013/06/zz-google-onsite-interview.html
2. http://www.geeksforgeeks.org/counting-inversions/
3. http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
4. https://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm

5.  https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerI.pdf
6. http://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf


problem statement:

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. 
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Lecture Notes -

1. First lecture study:

http://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf

1. How many inversions at most in the array n?

n(n-1)/2, special case, like {n, n-1, ..., 1}, any two nodes in the array is one inversion pair.

or: What is the maximum number of inversions for a list of length n? 

n(n-1)/2

2. If each inversion is counted once, then the time of the algorithm is O(n^2), n is the number of elements in the array. Not optimal, we should not count each inversion.

3. Ideas to solve the algorithm:

Bubble sort? 

Selection sort?

Insertion sort? 

These are O(n^2)

Bubble and insertion sort count each individual inversion. To do better we must not count each individual inversion. 

So, better algorithm is to beat O(n^2), using merge sort, nlogn - divide and conquer - sort and count inversion in the same time.

In merge sort we do not swap all elements that are out of order with each other, we make larger distance "swaps". 

Questions: Sorting and counting inversion - merge part how to count the inversions.

Keywords in the lecture notes (7):

Collaborative filtering 

inversions 

Meta-search tools
Rank analysis
Recurrence Analysis  - T(n) = 2 T(n/2) + cn 

similarity/ dissimilarity / in the middle 

the number of out of place rankings 

Actionable Items: 

1. Merging part with diagram:   <- Julia, can you draw a diagram as well 

2. Count Inversions: Algorithm pseudo code - write down here: 

2. 2nd Lecture Notes Study: 

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerI.pdf

Julia, write down favorite notes one sentence a time, on page 16, 17 

------- 

Counting inversions: how to combine two subproblems?
Q. How to count inversions (a,b) with a ∈ A and b ∈ B? 
A. Easy if A and B are sorted!

Warmup algorithm. 

Sort A and B. 

For each element b ∈ B, 

- binary search in A to find how elements in A are greater than b. 

list A                               list B

7    10    18  3  14           17    23    2  11  16

sort A                              sort B
3   7    10  14  18            2   11    16  17  23

binary search to count inversions (a, b) with a ∈ A and b ∈ B

3   7    10  14  18            2   11    16  17  23
                                       5    2      1     1   0
-------

3. 3rd Lecture Notes Study:  (Inversions Count)

http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf

Play to win; stop Recognize when you are using negative self-talks and replace it with positive; when in doubt, remember: Play to win.

Great tips for sports coaching, https://t.co/6m29a8l1z0

— jianmin chen (@jianminchen) July 22, 2016

Memorize 8 tips to help you to perform to your highest potential in Tennis (? code practice, etc.):
1. Let go of what others think
2. Perform for yourself, not to impress or to "not disappoint" others
3. Accept that you will make mistakes, and let them go
4. Focus on what you can control
5. Recognize when you are using negative self-talk and replace it with positive
6. Rather than performing perfectly, perform to see improvement
7. Be objective about your performance, not subjective
8. Focus on the Journey, not the Destination

Play not to lose or Play to win - Julia plays to win! 

Some people play not to lose. I play to win each and every second I'm on court. #SpeedTakes aggression. pic.twitter.com/ae5xlriogs

— Simona Halep (@Simona_Halep) July 2, 2016

Merge N sorted Array - merge sort from bottom-up implementation

July 21, 2016

   Merge N sorted arrays - C# practice



Time complexity analysis:

N sorted array, each array length is k, so the time complexity:

2k * N/2 + 4k * N/4 +... + 2^logN k * N/ (2^logN) = kN logN,

Today's research topic:
Coding is more of science, or just muscle memory, go for the intuition.

Review:
1. bottom-up implementation merge sort

2. Master Theorem - T(N) = 2T(N/2) + O(N)

3. Time complexity - come out kNlogN analysis

Read the article, and understand better about merge sort:

https://en.wikipedia.org/wiki/Merge_sort

Keywords:

Bitonic Mergesort
external merge sort - disk/ tape drives
external merge sort
merge sort
  - not inplace - must be allocated for the sorted output to be stored in
parallel mergesort
polyphase merge sort
natural merge sort - similar to a bottom up merge sort
stable sort,
TimSort,
tiled merge sort algorithm

Bottom-up implementation
Top-down implementation

comparison-based sorting algorithm

master theorem

average and worst-case performance

Lecture notes study:  (work on lecture notes, write down some interesting topic, do some research!)
http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf

Actionable item:
Add study time 10 minutes for computer science, review theorems, lecture notes when writing a new blog.

Leetcode 23: Merge K Sorted Lists

July 19, 2016

 Problem statement:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 Julia's first two practices in 2015:
1. Naive solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/MergeKSortedLists_A_No23.cs


2. Implementation using merge sort: August 12, 2015
https://github.com/jianminchen/Leetcode_C-/blob/master/MargeKSortedLists_B_No23.cs

Come back to work on this problem in 2016, July 19:

Study those blogs:
1. Most favorite one:
http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

Specially, the third discussion using divide and conquer, the conclusion that the merge solution is same time efficiency using heap solution Nklog(k), k is the number of arrays, and N is the length of the array, assuming that each array has same length.

1. http://www.cnblogs.com/TenosDoIt/p/3673188.html

2. http://bangbingsyb.blogspot.ca/2014/11/leetcode-merge-k-sorted-lists.html

3. http://codeganker.blogspot.ca/2014/08/leetcode_26.html

4. http://www.cnblogs.com/springfor/p/3869217.html

5. https://github.com/shawnfan/LintCode/blob/master/Java/Merge%20k%20Sorted%20Arrays.java

7. Excellent article - Julia, share your personal story as well.
http://codeganker.blogspot.ca/2014/08/leetcode_26.html

Read the article: 

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf

Julia's question and answer: 
1. Ideas to improve practice?
Answer:
  Ideas to construct the practice:
   1. Need to work on blog 7 - 3 solutions using C#, apply to "merge k sorted array".

Learn bottom-up merge sort, and know the time complexity as well.

C# solution - merge k sorted array - using bottom-up implementation merge sort
https://gist.github.com/jianminchen/d5fab2036647d380f20c908e91a81132

   2. Write down the proof of "divide and conquer" time complexity comparison using heap, O(nk logk)
       Show some simple example to help understand the time complexity.
   3. Warm up the code practice a few times, aiming to write 20 minutes for a solution
   4. Need to figure out master theorem quickly.

2. Can you work on a small example to illustrate some analysis?
Copy the image from Princeton's lecture note:

3. Can you write some C# code this time to make your own mark?

Actionable items:

Read the article, and write down questions - prepare a further reading list. (30 minutes reading )
https://en.wikipedia.org/wiki/Merge_sort
Notes:

keywords:  (remember 14 keywords)
average and worst-case performance
Bitonic Mergesort
Bottom-up implementation
comparison-based sorting algorithm
external merge sort - disk/ tape drives

external merge sort
master theorem
merge sort - not inplace - must be allocated for the sorted output to be stored in
parallel mergesort
polyphase merge sort
natural merge sort - similar to a bottom up merge sort

stable sort, 
TimSort, 
tiled merge sort algorithm
Top-down implementation

Variants:
  1. reducing the space complexity
  2. cost of copying

locality of reference

memory hierarchies
cache-aware version of merge sort algorithm
tiled merge sort algorithm

Parallel merge sort

Merge sort parallelizes well due to use of the divide-and-conquer method.

-
Comparison with other sort algorithms

heapsort   vs merge sort

O(1) auxiliary space instead of merge sort's O(n).

efficient quicksot implementations generally outperform mergesort for sorting RAM-based arrays - ?

merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.

Merge sort is often the best choice for sorting a linked list.

the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others(such as heapsort) completely impossible.

Java, Array.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficicency switch to insertion sort when fewer than seven array elements are being sorted.

Python uses Timsort, another tuned hybrid of merge sort and insertion sort.

--
More reading:
30 minutes to review:
http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf


5 minutes reading:
http://infolab.stanford.edu/~ullman/fcscnotes/notes9.pdf

20 minutes reading - plan to read - parallel merge sort
http://stanford.edu/~rezab/dao/notes/Lecture04/cme323_lec4.pdf

Read 10 minutes a time - get lost and enjoy reading ...


http://web.archive.org/web/20150120063131/https://android.googlesource.com/platform/libcore/+/jb-mr2-release/luni/src/main/java/java/util/TimSort.java

Will come back very soon.

Leetcode 4: Median of two sorted arrays

Problem statement: There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).

May 17, 2015

这道题我想了好几个小时,　读了题解,　没有读明白．直到我读了Leetcode的题解,　总算读懂了题目的分析．让我感叹计算机科学的奇妙．有大学学数学分析的感觉．

下面是题解分析:

这是一道非常经典的题。这题更通用的形式是，给定两个已经排序好的数组，找到两者所有元

素中第k 大的元素。

1. O(m + n) 的解法比较直观，直接merge 两个数组，然后求第k 大的元素。

2. O(k)时间，O(1) 空间; 但是，当k 很接近m + n 的时候，这个方法还是O(m + n) 的。

不过我们仅仅需要第k 大的元素，是不需要“排序”这么复杂的操作的。可以用一个计数器，

记录当前已经找到第m 大的元素了。同时我们使用两个指针pA 和pB，分别指向A 和B 数组的第

一个元素，使用类似于merge sort 的原理，如果数组A 当前元素小，那么pA++，同时m++；如果

数组B 当前元素小，那么pB++，同时m++。最终当m 等于k 的时候，就得到了我们的答案，O(k)

时间，O(1) 空间。但是，当k 很接近m + n 的时候，这个方法还是O(m + n) 的。

3. 更好的方案

有没有更好的方案呢？我们可以考虑从k 入手。如果我们每次都能够删除一个一定在第k 大元

素之前的元素，那么我们需要进行k 次。但是如果每次我们都删除一半呢？由于A 和B 都是有序

的，我们应该充分利用这里面的信息，类似于二分查找，也是充分利用了“有序”。

假设A 和B 的元素个数都大于k/2，我们将A 的第k/2 个元素（即A[k/2-1]）和B 的第k/2

个元素（即B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设k 为偶数，所得到的结

论对于k 是奇数也是成立的）：

• A[k/2-1] == B[k/2-1]

• A[k/2-1] > B[k/2-1]

• A[k/2-1] < B[k/2-1]

如果A[k/2-1] < B[k/2-1]，意味着A[0] 到A[k/2-1] 的肯定在A [B] 的top k 元素的范围 内，换句话说，A[k/2-1 不可能大于A [ B 的第k 大元素。留给读者证明。 因此，我们可以放心的删除A 数组的这k/2 个元素。同理，当A[k/2-1] > B[k/2-1] 时，可以删除B 数组的k/2 个元素。

当A[k/2-1] == B[k/2-1] 时，说明找到了第k 大的元素，直接返回A[k/2-1] 或B[k/2-1] 即可。

因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？

当A 或B 是空时，直接返回B[k-1] 或A[k-1]；

• 当k=1 是，返回min(A[0], B[0])；

• 当A[k/2-1] == B[k/2-1] 时，返回A[k/2-1] 或B[k/2-1]

－－

Read some blogs:

http://articles.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

http://fisherlei.blogspot.ca/2012/12/leetcode-median-of-two-sorted-arrays.html

Practice code sharing: C# code: 

https://github.com/jianminchen/medianOfTwoSortedArrays/blob/master/Program.cs

2017 January 5, 

Rewrite C# program for each time complexity:

O(m+n)

O(k)

O(log(m + n)

Post 3 code review on stackexchange.com code review.