CS 277 | lab

Learning Objectives

Practice using built-in dictionaries in Python
Conceptualize (and implement) dynamic programming
Use built-in time functions to measure performance differences.

Reminder: You can fill out an optional survey on Moodle after each lab!

Setup

From your CS 277 git directory, run the following:

git fetch release
git merge --allow-unrelated-histories release/lab_dynamic -m "Merging initial lab_dynamic files"

Upon a successful merge, your lab_dynamic files are now in your lab_dynamic directory.

You will only need to modify the following file: dynamic.py

Assignment Description

When we covered recursion, we acknowledged that certain functions (such as factorial or Fibonacci) are easy to write using recursion but are not efficiently implemented using recursion. For example, to get the sixth Fibonacci number using pure recursion you had to calculate the second Fibonacci number five times. These ‘overlapping subproblems’ are an unnecessary workload – as in the case of Fibonacci (see lab slides) where the naive recursive solution is exponential in time complexity.

One strategy to compensate for this is dynamic programming – where you store the solution to a subproblem after computing it once and build your solution from the ‘bottom up’ rather than the ‘top down’. For example in the case of Fibonacci, it is both easier and faster to compute the 0th and 1st number before calculating the 2nd number. The alternative – the naive recursion – is top down because we try to calculate the nth number (which requires the n-1 and n-2 numbers, which require n-2, n-3, n-4, and so on…).

At the end of the day, you calculate the same values but you do so using significantly fewer total operations. It sounds pretty obvious but getting it to work usually requires a firm understanding of dictionaries and for more complex problems the dynamic programming solution may not be so clear cut. The exercises here should gradually acclimatize you to some of the complexity – and the benefits – of dynamic programming.

Part 1: Dictionary basics

The implementation details for a dictionary will be discussed after Fall break but many of the more interesting data structures (including graphs) use a dictionary. You’ve already seen a few examples of a dictionary in earlier assignments (as well as how a tree can be used to create a dictionary) but to ensure the fundamentals are clear the first exercise of this lab is to create a dictionary using Python built-ins.

# INPUT:
# a string, inFile, giving the path to an input file
# OUTPUT:
# A dictionary containing the key, value pairs for each line in the file
# (Input file is formatted as <key>: <value>)
# You may assume keys are strings and should store values as integers
dict<str,int> parseFile_dictionary(str inFile):

The input files for this function are all formatted as key, value pairs separated by : – the only thing you need to do is insert each key, value pair into a built-in python dictionary. In case you don’t remember the syntax here:

myDictionary[key]=value # Assign a key, value pair
x = myDictionary[key] # Access the value associated with a key

Note that if the key is not present in the dictionary, trying to access its’ value will cause an error, much like how trying to access an index out of bounds on a list will. If you want to check for the presence or absence of a key, Python has a simple solution for this as well:

if key in myDictionary: #Will be true if the key is in the dictionary and false otherwise

Part 2: Dynamic Fibonacci

# INPUT:
# A int, n, containing the max fibonacci number being calculated
# OUTPUT:
# A *dictionary* containing all fib numbers from 0 to n as integers
dict<int,int> dynamic_fib(int n):

As covered in class much earlier in the semester, the Fibonacci function has a very straightforward recursive solution but the recursive solution is not efficient. For the second part of this lab, you are tasked with implementing a dynamic programming version of Fibonacci. Without using recursion, consider how you can calculate all the Fibonacci numbers in order (and store them in a dictionary as you do so). Your final output should be a dictionary of every Fibonacci number.

While efficiency of your solution won’t be graded, the provided code also shows how you can use Python to time a specific function. The exact time difference is a function of your computer hardware (and software) but if you implement your solution correctly you should see a significant time difference (my own implementation was ~4 orders of magnitude faster or 10,000x faster) between your solution and the provided recursive Fibonacci.

Part 3: Memoized Rod-cutting Problem

# INPUT:
# A int, n, containing the length of the rod we want to cut
# A dictionary, pricing, which contains the wholesale price for selling a rod of length x
# (You may assume the dictionary contains a price for each x from 0 to n)
# OUTPUT:
# A *dictionary* containing the optimal price you can get for a rod of length 0 to n
dict<int,int> rod_cut(int n):

The final dynamic programming problem is the ‘rod-cutting problem’ where – given a rod of length n and a list of prices for rods of all possible lengths – your job is to identify the best possible price you can get by cutting the rod into any number of pieces. Once again, this is a problem that has a straightforward but very inefficient recursive solution but a much faster dynamic programming solution.

However unlike previous labs, figuring out how to solve this problem is also a task left to you. Good luck!

HINT: A dynamic programming solution should figure out the optimal price for a rod of length 0, then length 1, then length 2, and so on…

lab_dynamic