Skip to content

Chapter 1: Problem Solving

Jump to bottom
George Heineman edited this page Jul 20, 2021 · 1 revision

The following are the code listings for Chapter 1. [book.py]

Listing 1-1. Flawed implementation to locate largest value in list

def flawed(A):
  my_max = 0        ❶
  for v in A:       ❷
    if my_max < v:
      my_max = v    ❸
  return my_max

❶ my_max is a variable that holds the maximum value; here my_max is initialized to 0.
❷ The for loop defines a variable v that iterates over each element in A. The if statement executes once for each value, v.
❸ Update my_max if v is larger.

Listing 1-2. Correct function to find largest value in list

def largest(A):
  my_max = A[0]                 ❶
  for idx in range(1, len(A)):  ❷
    if my_max < A[idx]:
      my_max = A[idx]           ❸
  return my_max

❶ Set my_max to the first value in A, found at index position 0.
❷ idx takes on integer values from 1 up to, but not including, len(A).
❸ Update my_max if the value in A at position idx is larger.

Listing 1-3. A different approach to locating largest value in A

def alternate(A):
  for v in A:
    v_is_largest = True        ❶
    for x in A:
      if v < x:
        v_is_largest = False   ❷
        break
    if v_is_largest:
      return v                 ❸
  return None                  ❹

❶ When iterating over A, assume each value, v, could be the largest.
❷ If v is smaller than another value, x, stop and record that v is not greatest.
❸ If v_is_largest is true, return v since it is the maximum value in A.
❹ If A is an empty list, return None.

Listing 1-4. Find two largest values by tweaking largest() approach

def largest_two(A):
  my_max,second = A[:2]                ❶
  if my_max < second:
    my_max,second = second,my_max

  for idx in range(2, len(A)):
    if my_max < A[idx]:                ❷
      my_max,second = A[idx],my_max
    elif second < A[idx]:              ❸
      second = A[idx]
  return (my_max, second)

❶ Ensure my_max and second are the first two values from A in descending order.
❷ If A[idx] is a newly found maximum value, then set my_max to A[idx], and [.keep-together]#second# becomes the old my_max.
❸ If A[idx] is larger than second (but smaller than my_max), only update second.

Listing 1-5. Three different approaches using Python utilities

def sorting_two(A):
  return tuple(sorted(A, reverse=True)[:2])    ❶

def double_two(A):
  my_max = max(A)                              ❷
  copy = list(A)
  copy.remove(my_max)                          ❸
  return (my_max, max(copy))                   ❹

def mutable_two(A):
  idx = max(range(len(A)), key=A.__getitem__)  ❺
  my_max = A[index_max]                        ❻
  del A[index_max]
  second = max(A)                              ❼
  A.insert(idx, my_max)                        ❽
  return (my_max, second)

❶ Create a new list by sorting A in descending order and return its top two values.
❷ Use built-in max() function to find largest.
❸ Create a copy of the original A, and remove my_max.
❹ Return a tuple containing my_max and the largest value in copy.
❺ This Python trick finds the index location of the maximum value in A, rather than the value itself.
❻ Record my_max value and delete it from A.
❼ Now find max() of remaining values.
❽ Restore A by inserting my_max to its original location.

Listing 1-6. Algorithm to find two largest values in A using tournament

----
def tournament_two(A):
  N = len(A)
  winner = [None] * (N-1)          ❶
  loser = [None] * (N-1)
  prior = [-1] * (N-1)             ❷

  idx = 0
  for i in range(0, N, 2):         ❸
    if A[i] < A[i+1]:
      winner[idx] = A[i+1]
      loser[idx] = A[i]
    else:
      winner[idx] = A[i]
      loser[idx] = A[i+1]
    idx += 1

  m = 0                            ❹
  while idx < N-1:
    if winner[m] < winner[m+1]:    ❺
      winner[idx] = winner[m+1]
      loser[idx]  = winner[m]
      prior[idx]  = m+1
    else:
      winner[idx] = winner[m]
      loser[idx]  = winner[m+1]
      prior[idx]  = m
    m += 2                         ❻
    idx += 1

  largest = winner[m]
  second = loser[m]                ❼
  m = prior[m]
  while m >= 0:
    if second < loser[m]:          ❽
      second = loser[m]
    m = prior[m]

  return (largest, second)

❶ These arrays store the winners and losers of match idx; there will be N – 1 of them in the tournament.
❷ When a value advances in match m, prior[m] records earlier match, or –1 when it was initial match.
❸ Initialize the first N/2 winner/loser pairs using N/2 invocations of less-than. These represent the matches in the lowest round.
❹ Pair up winners to find a new winner, and record prior match index.
❺ An additional N/2 – 1 invocations of less-than are needed.
❻ Advance m by 2 to find next pair of winners. When idx reaches N – 1, winner[m] is largest.
❼ Initial candidate for second largest, but must check all others that lost to largest to find actual second largest.
❽ No more than log(N) – 1 additional invocations of less-than.

Listing 1-7. Four different functions with different performance profiles

def f0(N):      def f1(N):            def f2(N):             def f3(N):
  ct = 0          ct = 0                ct = 0                 ct = 0
  ct = ct + 1     for i in range(N):    for i in range(N):     for i in range(N):
  ct = ct + 1       ct = ct + 1           ct = ct + 1            for j in range(N):
  return ct       return ct               ct = ct + 1              ct = ct + 1
                                          ct = ct + 1          return ct
                                          ct = ct + 1
                                          ct = ct + 1
                                          ct = ct + 1
                                          ct = ct + 1
                                        return ct

Listing 1-8. Four different functions with different performance profiles

def is_palindrome1(w):
  """Create slice with negative step and confirm equality with w."""
  return w[::-1] == w

def is_palindrome2(w):
  """Strip outermost characters if same, return false when mismatch."""
  while len(w) > 1:
    if w[0] != w[-1]:     # if mismatch, return False
      return False
    w = w[1:-1]           # strip characters on either end; repeat

  return True             # must have been palindrome

Listing 1-9. A linear-time algorithm to compute the median value in an unordered list

def partition(A, lo, hi, idx):
  """Partition using A[idx] as value."""
  if lo == hi: return lo

  A[idx],A[lo] = A[lo],A[idx]    # swap into position
  i = lo
  j = hi + 1
  while True:
    while True:
      i += 1
      if i == hi: break
      if A[lo] < A[i]: break

    while True:
      j -= 1
      if j == lo: break
      if A[j] < A[lo]: break

    if i >= j: break
    A[i],A[j] = A[j],A[i]

  A[lo],A[j] = A[j],A[lo]
  return j

def linear_median(A):
  """
  Efficient implementation that returns median value in arbitrary list,
  assuming A has an odd number of values. Note this algorithm will
  rearrange values in A.
  """
  lo = 0
  hi = len(A) - 1
  mid = hi // 2
  while lo < hi:
    idx = random.randint(lo, hi)     # select valid index randomly
    j = partition(A, lo, hi, idx)

    if j == mid:
      return A[j]
    if j < mid:
      lo = j+1
    else:
      hi = j-1
  return A[lo]

Listing 1-10. A linear-time Counting Sort algorithm

def counting_sort(A, M):
  counts = [0] * M
  for v in A:
    counts[v] += 1

  pos = 0
  v = 0
  while pos < len(A):
    for idx in range(counts[v]):
      A[pos+idx] = v
    pos += counts[v]
    v += 1

Listing 1-11. Another attempt to try to compute two largest values in unordered list

def two_largest_attempt(A):
  m1 = max(A[:len(A)//2])
  m2 = max(A[len(A)//2:])
  if m1 < m2:
    return (m2, m1)
  return (m1, m2)

All content drawn from Learning Algorithms: A Programmer’s Guide to Writing Better Code (c) 2021

Clone this wiki locally