I attended the "CLRS textbook study" meeting on 3/20/2017 of the "Algorithms and data structure problems" Pittsburgh group. This was the second meeting of the group. In the first meeting, it was decided that algorithms would be studied using the standard book CLRS. Unfortunately, CLRS does not seem appropriate given the audience. Below is my guess of what may be appropriate for the group.

We begin by explicitly stating what appears to be a simple problem: find the sum of any 2 distinct integers from a list of integers such that they equal a specific value. For example, given the data set [1, 2, 3, 4, 5, 6], which 2 distinct integers sum to 11? Mathematically, this can be stated as follows

Concepts are demonstrated via code snippets. They code snippets were executed using Python 2.7.6. They were written in such a way that anyone with basic coding skills could read the code. In other words, the goal was not to be Pythonic or use Python's standard library to solve the problem. Let me re-iterate, the goal of the code snippets is to demonstrate concepts.

The integer list is sorted and the quantity of integers is small enough such that brute force is acceptable.

Now, let's talk about all the possible addition permutations. Here I am using the term permutation as it is strictly defined in mathematics. For a discussion of the difference between permutations and combinations, refer to Combinations and Permutations at MathIsFun.Com. The above example corresponds to permutations without repetition which means that we should use the equation below

Another perspective is to note that the nested for loops result in O(n

Since the above approaches are not scalable, we need to step back and try something different. In this case, we can take advantage of the fact that the list of integers is sorted. Since we have an integer value and we know what the sum must be, we can compute the integer value that we need to find. We can than do a search over an ordered list for the integer that we need to find. For the search, we will use the binary search from Problem Solving with Algorithms and Data Structures using Python By Brad Miller and David Ranum.

Now, let's talk about the number of computations involved. It is commonly known that a binary search is O(log n). Since have to do the binary search once for each integer, have to multiply by n. This results in a performance of O(n [log n] ). For the rationale of why the base of the log does not matter, refer to Wikipedia: Sorting algorithm.

This complication is easily addressed by just sorting the integer list. It is commonly known that all comparison sorts cannot perform better than O(n [log n]) in the average or worst case. For background information on this, refer to Wikipedia: Sorting algorithm. Consequently, the computations required to determine if 2 integers in an unsorted integer list sum to a particular value is

The total computation complexity is O(2 * n [log n] ) = O(n [log n] )

Some people will recognize that the above material corresponds to exercise 2.3-7 of the book Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (CLRS) [Edition 3]. Below is the actual exercise

Note that Zhao HG on GitBook demostrates that the problem of finding two elements that sum to a given value in a sorted list of n integers can be solved in O(n) time as follows:

The above material demonstrates a common process. You start out with what appears a simple problem. You try a brute force approach but quickly realize that it won't scale. You then look for patterns like symmetry to reduce the number of required computations. If you are lucky, this will be good enough. If not, an alternative approach will have to be tried.

- x + y = x
_{0}

- where

- x ∈ N and y ∈ N for some finite set of integer values N

- x
_{0}: the integer to which x and y sum

- x != y

- x ∈ N and y ∈ N for some finite set of integer values N

- where

**Simplest Case**The integer list is sorted and the quantity of integers is small enough such that brute force is acceptable.

__Code Snippet 1__SomeIntegerList = [1, 2, 3, 4, 5, 6] DesiredSumOfIntegers = 11 for SomeIntegerA in SomeIntegerList: for SomeIntegerB in SomeIntegerList: if SomeIntegerA == SomeIntegerB: continue SumOfIntegers = SomeIntegerA + SomeIntegerB print "SomeInteger A = ", SomeIntegerA, ", SomeInteger B = ", SomeIntegerB, ", Sum of Integers = ", SumOfIntegers if DesiredSumOfIntegers == SumOfIntegers: print "DesiredSumOfIntegers = ", DesiredSumOfIntegers, " was found"

__Output of Code Snippet__SomeInteger A = 1 , SomeInteger B = 2 , Sum of Integers = 3 SomeInteger A = 1 , SomeInteger B = 3 , Sum of Integers = 4 SomeInteger A = 1 , SomeInteger B = 4 , Sum of Integers = 5 SomeInteger A = 1 , SomeInteger B = 5 , Sum of Integers = 6 SomeInteger A = 1 , SomeInteger B = 6 , Sum of Integers = 7 SomeInteger A = 2 , SomeInteger B = 1 , Sum of Integers = 3 SomeInteger A = 2 , SomeInteger B = 3 , Sum of Integers = 5 SomeInteger A = 2 , SomeInteger B = 4 , Sum of Integers = 6 SomeInteger A = 2 , SomeInteger B = 5 , Sum of Integers = 7 SomeInteger A = 2 , SomeInteger B = 6 , Sum of Integers = 8 SomeInteger A = 3 , SomeInteger B = 1 , Sum of Integers = 4 SomeInteger A = 3 , SomeInteger B = 2 , Sum of Integers = 5 SomeInteger A = 3 , SomeInteger B = 4 , Sum of Integers = 7 SomeInteger A = 3 , SomeInteger B = 5 , Sum of Integers = 8 SomeInteger A = 3 , SomeInteger B = 6 , Sum of Integers = 9 SomeInteger A = 4 , SomeInteger B = 1 , Sum of Integers = 5 SomeInteger A = 4 , SomeInteger B = 2 , Sum of Integers = 6 SomeInteger A = 4 , SomeInteger B = 3 , Sum of Integers = 7 SomeInteger A = 4 , SomeInteger B = 5 , Sum of Integers = 9 SomeInteger A = 4 , SomeInteger B = 6 , Sum of Integers = 10 SomeInteger A = 5 , SomeInteger B = 1 , Sum of Integers = 6 SomeInteger A = 5 , SomeInteger B = 2 , Sum of Integers = 7 SomeInteger A = 5 , SomeInteger B = 3 , Sum of Integers = 8 SomeInteger A = 5 , SomeInteger B = 4 , Sum of Integers = 9 SomeInteger A = 5 , SomeInteger B = 6 , Sum of Integers = 11 DesiredSumOfIntegers = 11 was found SomeInteger A = 6 , SomeInteger B = 1 , Sum of Integers = 7 SomeInteger A = 6 , SomeInteger B = 2 , Sum of Integers = 8 SomeInteger A = 6 , SomeInteger B = 3 , Sum of Integers = 9 SomeInteger A = 6 , SomeInteger B = 4 , Sum of Integers = 10 SomeInteger A = 6 , SomeInteger B = 5 , Sum of Integers = 11 DesiredSumOfIntegers = 11 was foundYou will notice that "1 + 2" as well as "2 + 1" equal 3. This corresponds to the commutative property of addition. If create a matrix of the possible addition permutations, a symmetric matrix is created.

Now, let's talk about all the possible addition permutations. Here I am using the term permutation as it is strictly defined in mathematics. For a discussion of the difference between permutations and combinations, refer to Combinations and Permutations at MathIsFun.Com. The above example corresponds to permutations without repetition which means that we should use the equation below

- Here n is the number of integers in the list and r = 2 because we are taking 2 numbers at a time. Below is a table which evaluates the above equation. It shows how quickly the number of required additions increase as the number of integers in the list increases.

Number of Integers Number of in the List Additions ------------------ --------- 2 2 3 6 4 ` 12 5 20 6 39 10 90 100 9,900 150 22,350 500 249,500 1,000 999,000

^{2}). Clearly, the above approach is not scalable.**Reduce Computations by Taking Advantage of Symmetry**__Code Snippet 2__SomeIntegerList = [1, 2, 3, 4, 5, 6] DesiredSumOfIntegers = 11 i = 0 for SomeIntegerA in SomeIntegerList: i = i + 1 j = 0 for SomeIntegerB in SomeIntegerList: j = j + 1 if j > i: print "i = ", i, ", j = ", j SumOfIntegers = SomeIntegerA + SomeIntegerB print "SomeInteger A = ", SomeIntegerA, ", SomeInteger B = ", SomeIntegerB, ", Sum of Integers = ", SumOfIntegers if DesiredSumOfIntegers == SumOfIntegers: print "DesiredSumOfIntegers = ", DesiredSumOfIntegers, " was found"

__Output of Code Snippet__i = 1 , j = 2 SomeInteger A = 1 , SomeInteger B = 2 , Sum of Integers = 3 i = 1 , j = 3 SomeInteger A = 1 , SomeInteger B = 3 , Sum of Integers = 4 i = 1 , j = 4 SomeInteger A = 1 , SomeInteger B = 4 , Sum of Integers = 5 i = 1 , j = 5 SomeInteger A = 1 , SomeInteger B = 5 , Sum of Integers = 6 i = 1 , j = 6 SomeInteger A = 1 , SomeInteger B = 6 , Sum of Integers = 7 i = 2 , j = 3 SomeInteger A = 2 , SomeInteger B = 3 , Sum of Integers = 5 i = 2 , j = 4 SomeInteger A = 2 , SomeInteger B = 4 , Sum of Integers = 6 i = 2 , j = 5 SomeInteger A = 2 , SomeInteger B = 5 , Sum of Integers = 7 i = 2 , j = 6 SomeInteger A = 2 , SomeInteger B = 6 , Sum of Integers = 8 i = 3 , j = 4 SomeInteger A = 3 , SomeInteger B = 4 , Sum of Integers = 7 i = 3 , j = 5 SomeInteger A = 3 , SomeInteger B = 5 , Sum of Integers = 8 i = 3 , j = 6 SomeInteger A = 3 , SomeInteger B = 6 , Sum of Integers = 9 i = 4 , j = 5 SomeInteger A = 4 , SomeInteger B = 5 , Sum of Integers = 9 i = 4 , j = 6 SomeInteger A = 4 , SomeInteger B = 6 , Sum of Integers = 10 i = 5 , j = 6 SomeInteger A = 5 , SomeInteger B = 6 , Sum of Integers = 11 DesiredSumOfIntegers = 11 was foundNow, let's talk about the number of computations involved in using nested for loops while taking advantage of the symmetry. Even though the number of computations is cut in half, the approach is still not scalable.

**Alternative Approach: Search for the other integer**Since the above approaches are not scalable, we need to step back and try something different. In this case, we can take advantage of the fact that the list of integers is sorted. Since we have an integer value and we know what the sum must be, we can compute the integer value that we need to find. We can than do a search over an ordered list for the integer that we need to find. For the search, we will use the binary search from Problem Solving with Algorithms and Data Structures using Python By Brad Miller and David Ranum.

__Code Snippet 3__def binarySearch(alist, item): first = 0 last = len(alist) - 1 found = False while first <= last and not found: midpoint = (first + last) // 2 if alist[midpoint] == item: found = True else: if item < alist[midpoint]: last = midpoint - 1 else: first = midpoint + 1 return found SomeIntegerList = [1, 2, 3, 4, 5, 6] DesiredSumOfIntegers = 11 for SomeInteger in SomeIntegerList: IntegerOfInterest = DesiredSumOfIntegers - SomeInteger if IntegerOfInterest == SomeInteger: print "IntegerOfInterest was not found" break print "SomeInteger = ", SomeInteger, ", IntegerOfInterest = ", IntegerOfInterest, ", DesiredSumOfIntegers = ", DesiredSumOfIntegers if binarySearch(SomeIntegerList,IntegerOfInterest) == True: print "IntegerOfInterest was found" break else: print "IntegerOfInterest was not found" print "---"

__Output of Code Snippet__SomeInteger = 1 , IntegerOfInterest = 10 , DesiredSumOfIntegers = 11 IntegerOfInterest was not found --- SomeInteger = 2 , IntegerOfInterest = 9 , DesiredSumOfIntegers = 11 IntegerOfInterest was not found --- SomeInteger = 3 , IntegerOfInterest = 8 , DesiredSumOfIntegers = 11 IntegerOfInterest was not found --- SomeInteger = 4 , IntegerOfInterest = 7 , DesiredSumOfIntegers = 11 IntegerOfInterest was not found --- SomeInteger = 5 , IntegerOfInterest = 6 , DesiredSumOfIntegers = 11 IntegerOfInterest was foundLet's analyze the code snippet.

- Since the integers that sum must be distinct, the diagnol on the matrix have values of N/A. This resulted in the following if statement

if IntegerOfInterest == SomeInteger: print "IntegerOfInterest was not found" break

- Secondly, we should remove the integer that we are on from the binary search. However, removing an item from a list is expensive. For the details, refer to How to remove an element from a list by index in Python? at StackOverFlow.Com. Consequently, elected not to remove the integer that we are on from the list. Also, having 1 extra element in the search list is not a major impact when there are a large number of integers.

**Complicate Problem by Having Integer List Not Sorted**This complication is easily addressed by just sorting the integer list. It is commonly known that all comparison sorts cannot perform better than O(n [log n]) in the average or worst case. For background information on this, refer to Wikipedia: Sorting algorithm. Consequently, the computations required to determine if 2 integers in an unsorted integer list sum to a particular value is

- n [log n] cost for sorting the unordered integer list

- n [log n] cost for searching for the other integer

**Above material corresponds to exercise 2.3-7 of the book Introduction to Algorithms by Cormen, ...**Some people will recognize that the above material corresponds to exercise 2.3-7 of the book Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (CLRS) [Edition 3]. Below is the actual exercise

def two_sum(a, x): l, r = 0, len(a)-1 while l < r: if a[l] + a[r] == x: return True elif a[l] + a[r] < x: l += 1 else: r -= 1 return False

**Summary**The above material demonstrates a common process. You start out with what appears a simple problem. You try a brute force approach but quickly realize that it won't scale. You then look for patterns like symmetry to reduce the number of required computations. If you are lucky, this will be good enough. If not, an alternative approach will have to be tried.