Please enable JavaScript.

Coggle requires JavaScript to display documents.

Divide and Conquer (Counting Inversions (Computing a distance function on…

- - - - Using other people which the website deemed similar to make recommendations for you
    - - Searching the same query on multiple search engines then "synthesizing the results by looking at similarities and differences between rankings
  - - - Comparing orderings between a set collection
    - - We label the movies according to MY ranking from 1-n
        
        Order the other person's ranking based off mine
        
        See how many pairs are out of order
        
        By counting the number of inversions we can say how out of order they are
        
        We say that two indices i < j form an inversion if
        \(a_i > a_j\) i.e. two elements ai and aj are “out of order.”
        We will seek to determine the number of inversions in the sequence a1,..., an.
        
        3 and 4 both come earlier in the array than 2 but they're larger than 2
  - - - We want to see how similar or different those rankings are
  - - - How to combine?
        
        Easy if sorted
        
        IF sorted
        Scan A and B from left to right.
        Compare ai and bj.
        If ai < bj, then ai is not inverted with any element left in B.
        If ai > bj, then bj is inverted with every element left in A.
        Append smaller element to sorted list C.
- - - - Once you identify the pattern you're done
  - - - You prove formally by induction on n
  - - - You make a guess with no constants specified
        
        You plug it into the recurrence relation with the constants added on
        
        Try and solve so that it reduces back to your guess
        
        You make educated guesses until you reach the end
- - - - The run time involves solving a recurrence relation which is just the equation for how to break down the current problem
  - - - The divide and conquer improves the performance however
        
        Brute force: \(\Theta^2\)
        Divide and Conquer: \(nlog(n)\)
- - - - T(n) \(\leq\) 2T(n/2) + cn when n > 2
        cn = time to combine the solutions from the two recursive calls
        
        T(2) \(\leq\) c
        If the input is 2 or less the runtime is constant
  - - - What's the pattern?
        
        At each level the number of subproblems double
        
        At level j we have a total of \(2^j\) subproblems
        
        Work each level at e= Work subproblem does * # of subproblems
        
        \(2^j(\frac{cn}{2^j}) = cn\)
        j = level
        
        At each level each subproblem does half of the level before it.
        
        Each subproblem does \(n\over2^j\)
        
        Summing it over all levels
        
        The upper bound of cn applies to the total amount of work at each level
        
        Total work = Work at each level * # of levels
        
        # of levels
        
        This is the same as going from n to our base case 2
        
        1 more item...
        
        Work at each level = cn
    - - Let's just make an assumption that since we're halving at each level we think it'll \(T(n) \le cn log_2n \text{for all } n \ge 2\)
        
        Prove by induction
        
        Base case is when n = 2
        
        \(c*2 * log_2(2) \to 2c\)