SOVED CSE2050 Homework 03: Lists and Timing

Objectives

• Developing alternative, more efficient algorithms.
• Estimating the efficiency of an algorithm (Big-O)
• Measuring the time to execute code.

Activities

You will be developing multiple algorithms for one problem: Given a list of unique integers and a target integer, find all pairs in the list that add up to the target. For example, given a list of integers [1, 2, 3, 4, 5] and a target integer 5, the function should return
{(1, 4), (2, 3)} (a set of tuples). NOTE: It does not, and it should not, return the reverse pairs. It should not return {(1, 4), (2, 3) , (3, 2) , (4, 1)}.

1. Use test-driven development as you go - write unittests (using the unittest module) in a file TestHw3.py. To fully test the find_pairs functions, you should look for at a minimum:
2. Test the functions with different inputs and check if the output is correct.
3. Test the function with edge cases and different inputs to check the correctness of the functions. For example: test case with empty list; test case with target = 0; test case with no pairs that meet the target.
4. A test case with target that equals to double number in the list. For example, For example if input list is [1, 2, 3, 4, 5] and target is 6, the output should be {(2, 4), (1, 5)}. Pair (3,3) should not be included.
5. A test case with only expected duplicate values as the target. For example, if input list is [1, 2, 3, 4, 5] and target is 10, the output should be an empty set set(). (i.e., there is only one solution for the target but it requires duplicating a value which is not allowed so the result is the empty set).
6. Be sure to identify at least one more test than the above. Paste your test code below this bullet.
7. import unittest
   from hw3 import find_pairs_naive, find_pairs_optimized
   
   class TestPairFindingAlgorithms(unittest.TestCase):
   
   def test_basic_functionality(self):
         """Using a basic list, test hw3"""
         self.assertEqual(find_pairs_naive([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})
         self.assertEqual(find_pairs_optimized([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})
   
     def test_with_negative_numbers(self):
         """Using a list with negative numbers"""
         self.assertEqual(find_pairs_naive([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})
         self.assertEqual(find_pairs_optimized([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})
   
     def test_no_pairs(self):
         """Using a list and target where no two numbers can sum up to the target"""
         self.assertEqual(find_pairs_naive([1, 2, 3, 4], 10), set())
         self.assertEqual(find_pairs_optimized([1, 2, 3, 4], 10), set())
   
     def test_large_list(self):
         """Using a somewhat large list"""
         large_list = list(range(100))
         target = 50
         expected_pairs = {(10, 40), (11, 39), (1, 49), (2, 48), (18, 32), (17, 33), (8, 42), (24, 26), (9, 41), (15, 35), (0, 50), (16, 34), (19, 31), (6, 44), (22, 28), (7, 43), (23, 27), (14, 36), (5, 45), (13, 37), (20, 30), (21, 29), (12, 38), (3, 47), (4, 46)}
         self.assertEqual(find_pairs_naive(large_list, target), expected_pairs)
         self.assertEqual(find_pairs_optimized(large_list, target), expected_pairs)
   
   
   if __name__ == '__main__':
     unittest.main()

1. Create a file hw3.py. In this file, you need to write two functions that behave as described above: find_pairs_naive(L, n) and find_pairs_optimized(L,n).
2. Write the function find_pairs_naive(L, n). The implementation of this algorithm should iterate over the entire list using two nested loops to check for pairs that add up to the target. Note that sorting the list may be of value. Provide a listing of your find_pairs_naive(L, n) below this line.
3. Write the function find_pairs_optimized(L, n). The implementation of this algorithm should make use of a data structure or other methods to improve the efficiency of the algorithm. Each of these algorithms will be timed in follow-on steps. Provide a listing of your find_pairs_optimized(L, n) below this line.

def find_pairs_naive(L, n):

   """Utilizes O(n^2) to find a par of numbers"""

   pairs = set()

   for i in range(len(L)):

       for j in range(i + 1, len(L)):

           if L[i] + L[j] == n:

               pairs.add((L[i], L[j]))

   return pairs





def find_pairs_optimized(L, n):

   """Utilizes Dictionary to find a pair of numbers"""

   pairs = set()

   seen = {}

   for number in L:

       complement = n - number

       if complement in seen:

           pairs.add((min(number, complement), max(number, complement)))

       seen[number] = True

   return pairs

1. In the same file hw3.py, write a function measure_min_time(func, args, n_trials) which will measure the minimum time to execute the function over n trials. Provide a listing of your function measure_min_time(func, args, n_trials) below this line.

def measure_min_time(func, args, n_trials=10):

   """Takes a function and argument input and

   will keep track of the results of all n_trials and

   return the minimum amount of execution time as float"""

   min_time = float('inf')

   for _ in range(n_trials):

       start = time.perf_counter()

       func(*args)

       end = time.perf_counter()

       min_time = min(min_time, end - start)

   return min_time

1. Write a program within hw3.py that results in a table being presented along the lines as the following table is printed. Make use of properly formatted print statements so that it rounds the time to four decimal places. The number of trials (n) increases. Provide a listing of your code along with a copy of the output table.

n naive optimized

10 - -

50 - -

100 - -

150 - -

200 - -

300 - -

500 - -

def compare_algorithms():

   """Compares the naive time and optimized pair finding codes and generates a table which describes the processing 

   time of each function"""

   trials = [1800, 1850, 1950, 2150, 2500]

   print(f"n\tnaive\toptimized")

   for n in trials:

       list_to_test = generate_list(n)

       naive_time = measure_min_time(find_pairs_naive, [list_to_test, n], 100)

       optimized_time = measure_min_time(find_pairs_optimized, [list_to_test, n], 100)

       print(f"{n}\t{naive_time:.4f}\t{optimized_time:.4f}")

n naive optimized

1800 0.0676 0.0001

1850 0.0714 0.0001

1950 0.0793 0.0001

2150 0.0970 0.0001

2500 0.1310 0.0002

1. We can often calculate the running time of a function by adding up the execution cycles of every line. For instance, the below function has a O(n) running time to add up all the items in a list:

1. Add comments to find_pairs_naive and find_pairs_optimized that show line-by-line execution cycles and the total sum, as in the example above. Be sure to insert newlines in your comments as appropriate so that the indentation of your code is not thrown off – make sure your code looks good. Provide the new listing of find_pairs_naive and find_pairs_optimized below. Include a brief explanation of the results in comments under each function.

def find_pairs_naive(L, n):

   """Utilizes O(n^2) operations to take an input of a list and a number which will determine the pairs in the list

   that add up to the number"""

   pairs = set() # 1 (Assigns a variable)

   for i in range(len(L)): # n (Outer loop runs n times)

       for j in range(i + 1, len(L)): # n (Inner loop runs n times)

           if L[i] + L[j] == n:   # 1 (Assigns a variable if true)

               pairs.add((L[i], L[j])) # 1 (Performs addition)

   return pairs   #1 (Returns a value)

                   # ------------------------

                   # 1 + 2n + 3 = O(n^2)



def find_pairs_optimized(L, n):

   """Utilizes O(n) operations to take an input of a list and a number which will determine the pairs in the list

   that add up to the number"""

   pairs = set()   # 1 (Assigns a variable)

   seen = {}   # 1 (Builds blank dictionary)

   for number in L:   # n (Loop iterates n times)

       complement = n - number # 1 (Subtraction)

       if complement in seen: # 1 (Dictionary lookup)

           pairs.add((min(number, complement), max(number, complement)))   # 1 (Adds pairs)

       seen[number] = True # 1 (Dictionary set operation)

   return pairs   # 1 (Returns a value)

                   # ______________________________

                   # 2 + n + 5 = O(n)

1. Write a function generate_list(n) which will return a list with n non-repeating integer elements. You can use the random module of python.
2. Modify the previous program which changed the number of trials so that it now changes the length of the list. Keep the number of trials constant at 100 trials. Present a similar table as before for the various values of the length of the list generated n.
3. n naive optimized
4. 1800 0.0692 0.0001
5. 1850 0.0724 0.0001
6. 1950 0.0793 0.0001
7. 2150 0.1035 0.0002

2500 0.1327 0.0002

1. In addition to pasting code within this Word document and submitting, also attach TestHw3.py and hw3.py to your Husky CT submission. Be sure it is a single submission in Husky CT with all three files.

import time
import random
def find_pairs_naive(L, n):
  """Utilizes O(n^2) operations to take an input of a list and a number which will determine the pairs in the list
  that add up to the number"""
  pairs = set() # 1 (Assigns a variable)
  for i in range(len(L)): # n (Outer loop runs n times)
      for j in range(i + 1, len(L)): # n (Inner loop runs n times)
          if L[i] + L[j] == n:   # 1 (Assigns a variable if true)
              pairs.add((L[i], L[j])) # 1 (Performs addition)
  return pairs   #1 (Returns a value)
                  # ------------------------
                  # 1 + 2n + 3 = O(n^2)

def find_pairs_optimized(L, n):
  """Utilizes O(n) operations to take an input of a list and a number which will determine the pairs in the list
  that add up to the number"""
  pairs = set()   # 1 (Assigns a variable)
  seen = {}   # 1 (Builds blank dictionary)
  for number in L:   # n (Loop iterates n times)
      complement = n - number # 1 (Subtraction)
      if complement in seen: # 1 (Dictionary lookup)
          pairs.add((min(number, complement), max(number, complement)))   # 1 (Adds pairs)
      seen[number] = True # 1 (Dictionary set operation)
  return pairs   # 1 (Returns a value)
                  # ______________________________
                  # 2 + n + 5 = O(n)

def measure_min_time(func, args, n_trials=10):
  """Takes a function and argument input and
  will keep track of the results of all n_trials and
  return the minimum amount of execution time as float"""
  min_time = float('inf')
  for _ in range(n_trials):
      start = time.perf_counter()
      func(*args)
      end = time.perf_counter()
      min_time = min(min_time, end - start)
  return min_time

def compare_algorithms():
  """Compares the naive time and optimized pair finding codes and generates a table which describes the processing
  time of each function"""
  trials = [1800, 1850, 1950, 2150, 2500]
  print(f"n\tnaive\toptimized")
  for n in trials:
      list_to_test = generate_list(n)
      target = random.randint(1, n*10)
      naive_time = measure_min_time(find_pairs_naive, [list_to_test, target], 100)
      optimized_time = measure_min_time(find_pairs_optimized, [list_to_test, target], 100)
      print(f"{n}\t{naive_time:.4f}\t{optimized_time:.4f}")

def generate_list(n):
  """Generates a list of random, non-repeated numbers"""
  return random.sample(range(1, n*10), n)

if __name__ == "__main__":
  compare_algorithms()

import unittest

from hw3 import find_pairs_naive, find_pairs_optimized



class TestPairFindingAlgorithms(unittest.TestCase):



   def test_basic_functionality(self):

       """Using a basic list, test hw3"""

       self.assertEqual(find_pairs_naive([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})

       self.assertEqual(find_pairs_optimized([1, 2, 3, 4, 5], 5), {(1, 4), (2, 3)})



   def test_with_negative_numbers(self):

       """Using a list with negative numbers"""

       self.assertEqual(find_pairs_naive([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})

       self.assertEqual(find_pairs_optimized([-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], 0), {(-5, 5), (-4, 4), (-3, 3), (-2, 2), (-1, 1)})



   def test_no_pairs(self):

       """Using a list and target where no two numbers can sum up to the target"""

       self.assertEqual(find_pairs_naive([1, 2, 3, 4], 10), set())

       self.assertEqual(find_pairs_optimized([1, 2, 3, 4], 10), set())



   def test_large_list(self):

       """Using a somewhat large list"""

       large_list = list(range(100))

       target = 50

       expected_pairs = {(10, 40), (11, 39), (1, 49), (2, 48), (18, 32), (17, 33), (8, 42), (24, 26), (9, 41), (15, 35), (0, 50), (16, 34), (19, 31), (6, 44), (22, 28), (7, 43), (23, 27), (14, 36), (5, 45), (13, 37), (20, 30), (21, 29), (12, 38), (3, 47), (4, 46)}

       self.assertEqual(find_pairs_naive(large_list, target), expected_pairs)

        self.assertEqual(find_pairs_optimized(large_list, target), expected_pairs)





if __name__ == '__main__':

   unittest.main()