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

JavaScript Array developer.Mozilla.org - 3+ hours study

July 2, 2016

First thing in the morning, read JavaScript Array webpage, and then, start to work on the target:

1. Memorize all the content on the page.  (Estimated time to understand every term on the page: 10+ hours)

https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/prototype

2. List all concepts to learn
3. Questions about the content

Training on JavaScript - start from memorizing JavaScript Array APIs

Time spent:
3 hours (July 2, 2016)

https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/prototype

Design drills to memorize the JavaScript function names:

1. Properties

Array.prototype
Array.length

Method   (33 methods)

Array.from()
Array.isArray()
Array.of()

Array.prototype.concat()
Array.prototype.copyWithin()
Array.prototype.entries()
Array.prototype.every()
Array.prototype.fill()

Array.prototype.filter()
Array.prototype.find()
Array.prototype.findIndex()
Array.prototype.forEach()
Array.prototype.includes()

Array.prototype.indexOf()
Array.prototype.join()
Array.prototype.keys()
Array.prototype.lastIndexOf()
Array.prototype.map()

Array.prototype.pop()
Array.prototype.push()
Array.prototype.reduce()
Array.prototype.reduceRight()
Array.prototype.reverse()

Array.prototype.shift()
Array.prototype.slice()
Array.prototype.some()
Array.prototype.sort()
Array.prototype.splice()

Array.prototype.toLocaleString()
Array.prototype.toSource()
Array.prototype.toString()
Array.prototype.unshift()
Array.prototype.values()

Inheritance:

Function -> properties ->   (5, please remember: c, d, l, n, p)
Functon.caller
Function.displayName
Function.length
Function.name
Function.prototype

Function -> Methods -> (6, please remember: a, b, c, i, t, t)
Function.prototype.apply()
Function.prototype.bind()
Function.prototype.call()
Function.prototype.isGenerator()
Function.prototype.toSource()
Function.prototype.toString()

Object

Methods

Object.prototype.__defineGetter__()
...

2. Study notes (July 2, 2016):

a global object,
list-like objects
Access(index into) an Array item
Loop over an array - forEach
push - Add to the end of an Array
pop  -  Remove from the end of an Array
shift - Remove from the front of an Array
unshift - Add to the front of an array
     Adds one or more elements to the front of an array and returns the new length of the array.
push - find the index of an item in the Array
pop  - Remove an item by Index Position
splice - Remove an item by Index Position
slice  - Copy an Array
    julia's comment: slice or dice, slice is just to get part of array, can be the whole array. 
           function syntax, startIndex, endIndex, arr.slice([begin[, end]])
from - Array.from(), creates a new Array instance from an array-like or iterable object. 
isArray - Array.isArray(), returns true if a variable is an array, if not false. 
of  - Array.of(), creates a new Array instance within a variable number of arguments, regardless of number or type of the arguments. 

Mutator methods - modify the array
copyWithin - Copies a sequence of array elements with the array
fill - Fills all the elements of an array from a start index to an end index with a static value.

splice - Adds and/or removes elements from an array.
join - joins all elements of an array into a string.

Iteration methods:
forEach()
entries()
every()
some()
filter()
find()
findIndex()
keys()
map()
reduce()
reduceRight()
values()

Question: Syntax - what kind of definition? [ <- optional argument?

traversal and mutation operations 
Arrays can be stored at non-contiguous locations in the array, JavaScript arrays are not guaranteed to be dense.
Questions: When to use typed arrays? 
   JavaScript arrays are not guaranteed to be dense, so typed arrays are guaranteed to be dense. (? Look into it later)

Questions: an associated array - what is "associated" meaning? 

zero-indexed - 
using bracket notation - renderer['ed].setTexture(model, 'character.png')  - works properly
with dot notation - cannot be referenced with dot notation, must be accessed using bracket notation. 

Array.length talk -     A JavaScript array's length property and numerical properties are connected. Several of the built-in array methods (e.g., join, slice, indexOf, etc.) take into account value of an array's length property when they are called. Other methods (e.g., push, splice, etc.) also result in updates to an array's length property. 
  Questions: built-in array methods ? Array.prototype.join, those functions are defined for all iterable object. 

Good reading with one example, two lines of JavaScript code: 
Creating an array using the result of a match
RegExp.exec, String.match, and String.replace (? study later)

Memorize this example - one regular express a time

// Match one d followed by one or more b's followed by one d
// Remember matched b's and the following d
// Ignore case

var myRe = /d(b+)(d)/i; 
var myArray = myRe.exec('cdbBdbsbz')

Question: review regular expression in JavaScript?

Array instances 
All array instances inherit from Array.prototype. 

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