LAB 9

Matching pairs

The idea with two indexes…
Draw a picture
What if the array is already sorted?
What is then an optimal approach? Using Binary Search or using two indexes?

Algorithm:

boolean matchingPairs(int[] A, int s)
   sort(A)
   i := 1 
   j := A.length
   while i < j and A[i] + A[j] != s do
                                // (*) = Maintenance Snapshot
      if A[i] + A[j] > s
         then j--
         else i++
   if i >= j 
      then return false
      else return true

Loop invariant:

    LI: For every i'' such that i''<i there is no matching pair for i''
        For every j'' such that j''>j there is no matching pair for j''

    Proof.

    Initialization: (before the loop) 
        Only possibilities are i''=0 and j''> A.length
        And thus trivially there are no matching pairs for i'' and j'' in A

    Maintenance: (at the step (*))

        Assume that at the point (*) we have indexes i and j.

        Assume that in the previous step indexes were i' and j'.

        Now we distinguish cases:

        Case 1: j was decreased in the previous step
                i.e., j=j'-1 and i=i

            From LI we have that LI holds for all j'' such that j ''> j'
            now it remains to show that it also holds for j''= j'.
            That is, there is no matching pair for j'.

            Assume i_j' is a candidate for a matching pair with j'

            We distinguish different possibilities for i_j'


            1. i_j'<i 

                According to LI there is no matching pair for
                i_j'

            2. i_j'=i  

                Since j was decreased in the previous step
                then we know that 
                    A[i']+A[j']>s
                Since i'=i (i didn't change) then also
                    A[i']+A[j']>s
                Thus, i is not matching pair for j'

            3. i_j'>i

                Since A is sorted we have that 
                    A[i_j']>A[i]

                Since A[i']+A[j']>s 

                then it holds 
                    A[i_j'] + A[j'] > s 

                Thus, there is no i_j'>i that is matching pair of j'

            All together, 
            there is no matching pair for j'' s.t. j'' = j' (=j+1), and 
            from LI (of the previous step) 
                no matching pair for j'' s.t. j'' > j'.

            Thus, no matching pair for j'' s.t. j'' > j.



        Case 2: i was increased in the previous step
                i.e., i=i+1 and j=j'

            // Can be shown in the same way as Case 1


    Termination.

        The loop either terminated because:

            - i=j. From LI it means that
                 for each i''<i (=j) there is no matching pair, and 
                 for each j''>j (=i) there is no matching pair.
                 Thus, there is no matching pair in A

            - S[i]+S[j]=s, i.e., matching pair is found

Discussion

What is a loop invariant?
Snapshot-view of the problem vs Assertion view
- Imagine how the progresses from step i to step i+1
- Focus on implement the transitions
- In principle, the transition is organized to maintain loop invariant
Think of the middle case (not exact algorithm step)
Then code to match transitions (= transition of Loop Invariant)
Highlights from the book “HOW TO THINK ABOUT ALGORITHMS” about loop invariants

Find closest sum to s

Story: Imagine in DeSpar you receive a coupon for 50 Eur.,
and you want to either spent or lose as least as possible
Variant of matching pairs
Find i,j, and s’=A[i]+A[j] such that for every other i’ and j’

|s-A[i]-A[j]|>=|s-A[i’]-A[j’]|
Hint: adaptation idea: store i and j that we closest s

Algorithm:

structure Pair

    int i_opt;
    int j_opt;



Pair MatchingPairs(int [] A)

i := 1
j := A.length

i_opt := i
j_opt := j
minDiff := s - A[i_opt] - A[j_opt]

while i<j && A[i]+A[j] != s

    if absolute(s - (A[i]+A[j])) < minDiff
        i_opt := i
        j_opt := j

    if A[i]+A[j] > s
        then j--
        else i++



if A[i]+A[j] = s
    return Pair(i,j)
    else Pair(i_opt,j_opt)

Exact Contiguous Sum

Problem:
We are given an array of positive integers A and a positive number s.
The question is whether there exists a segment A[i..j] of A
such that the sum of the numbers of this segment equals s.

A[i]+A[i+1]+..+A[j-1]+A[j] = s

Straightforward approach

boolean ContiguousSum(int [] A, s)

  for i := 1 to A.length do
     for j := i to A.length do
        sum := 0
        for k := i to j do
           sum += A[k]
        if sum = s
           then return true
  return false

runtime: cubic

Ideas: …

boolean ContiguousSum(int [] A, s)

  for i := 1 to A.length do
        sum := 0
        for j:= i to n do
            sum := sum + A[j]        
            if sum = s 
                then return true // jumping out the window solution :(
  return false

runtime: quadratic

Can we do better?
Let’s look it again…

(pause)

We iterate over array with i
We want that each i’<i the contiguous sum does not start at i’
What to do?
Let us look at snapshots:
- sum = A[i]<s
- sum = A[i]+A[i+1] < s
- sum = A[i]+A[i+1]+A[i+2] < s
- sum = A[i]+A[i+1]+A[i+2] = s YEAH! but if not we ctd.
- …
- sum = A[i]+A[i+1]+A[i+2]+A[i+3]+A[i+4] > s (at some moment)
- remove A[i] from the above sum ?
- i is not in the segment because we try all possible segments for i
- thus we look at the next one i:=i+1
- what about sum, should we recompute it?
- not all right?
- s’ := s - A[i]
- what about j (=i+4 in the lase case)
- should it start from i again?
- no…
- why it is sufficient to ctd with A[i+1]+A[i+2]+A[i+3]+A[i+4], j=i+4
- and not necessary to look into with A[i+1]+A[i+2]+A[i+3]
- because we know that A[i+1]+A[i+2]+A[i+3] < s
- since A[i]+A[i+1]+A[i+2]+A[i+3]<s
- running time: n^2 or n ?
Try now!

(pause)

We develop the algorithm on fly

Algorithm (first attempt):

    boolean ContiguousSum(int [] A, s)

    i := 1
    j := 1

    sum := A[i]

    while i<=n && sum!=s

        while j< n && sum < s     // move j
            j++
            sum := sum + A[j]

        if sum > s                // move i
            sum := sum - A[i]
            if i<n                // move i if i<n 
                i++
            if i>j                // e.g., when A[j]>s then sum=A[j(=i)]
                j := i

        if sum<s and j=n        // edge case -- find way to solve it
            i : = n+1           // just to exit


    if sum = s 
        then return true
        else return false

Algorithm with a single loop:

   boolean ContiguousSum(int [] A, s)

    i := 1
    j := 1

    sum := A[i]

    while i<=A.length && j<=A.length && sum != s

        if j<=A.length && sum < s                       // move j
            j++                                         // if sum<s and j=n 
            if j<n
             sum := sum + A[j]


        if i<=A.length && sum > s                         // move i
            i++
            if i < j
                sum = sum - A[i] 
            else                                          // i >= j  
                sum := A[i]
                j := i


    if sum = s    
        then return true
        else return false

Loop invariant

For every i' < i  
For every j' < j:
For i'<=j'
     A[i']+..+A[j'] != s

AND

sum := A[i]+..+A[j]

perhaps better

(
For every i' <= i  
For every j' < j:
For i'<=j'
     A[i']+..+A[j'] != s

OR

For every i' < i  
For every j' <= j:
For i' <= j'
     A[i']+..+A[j'] != s
)


AND

sum := A[i]+..+A[j]

Maximal Integral

Problem:
We are given an array of integers A (also negative ones)
The question is to find the segment A[i..j] that has the biggest sum
(A[i]+A[i+1]+..+A[j-1]+A[j] = sum).

Idea:
- like an integral (surface bellow and above)
- how to solve it?
- straight: quadratic
- more optimal approach?

(pause)

Hint: Divide & Conquer
Develop picture on board
Discuss

(pause)

Show alg

Alg using Divide & Conquer approach:

Structure Inter{
    int ms; // max sum
    int ml; // max left
    int mr; // max right
    int is; // interval sum
}


Inter MaxContSum(int [] A, int l, int r)

    Inter inter


    if l<r

        int m := (l+r)/2

        lInt := MaxContSum(A,l,m)

        rInt := MaxContSum(A,m+1,r)

        inter.ms :=  max(lInt.ms,rInt.ms,lInt.mr+rInt.ml)

        inter.ml := max(lInt.is + rInt.ml, lInt.ml)

        inter.mr := max(rInt.is + lInt.mr, rInt.mr)

        inter.is := lInt.is+rInt.is

    else  // base case

        inter.ms := A[l]

        inter.ml := A[l]

        inter.mr := A[l]

        inter.is := A[l]


    return inter

Running time??
Master theorem

T(n) = 2 T(n/2) + n^0

=> T(n) = \Theta(n)