Practice Problems

The purpose of the practice problems is to allow you to test your understanding of the material we are covering in lecture. There are two types of practice problems:

  • “be-a-computer” warm-up exercises. You should do these warm-up exercises by hand. We’ll provide code to allow you to check your answers.
  • Programming Problems. We will be using a system named Kattis for these problem. Kattis is a website that allows students to submit solutions to programming problems, and have them evaluated automatically by running a series of test cases on the submitted solutions. You can find information about how to use Kattis here.

All the files necessary to solve these problems are located in a pp/ directory in your repository (make sure you run git pull upstream master to get the files). This directory contains a bac subdirectory with files you can use to check your solution to the be-a-computer exercises, and a kattis directory with the files you’ll need to solve the Kattis problems.

Make sure you read our Using Kattis page before you start working on the Kattis problems!

Problems below with a (*) are challenge problems.

Programming Basics

Be-a-computer exercises

Kattis problems:

Note: some of the above Kattis problems refer to files being in a hw directory; please disregard this and look in the kattis directory instead.

Functions and Lists

Be-a-computer exercises

Kattis problems

Dictionaries

Be-a-computer exercises

Kattis problems

Classes and Objects

Be-a-computer exercises

Coding problems: (Not on Kattis)

Functional Programming

Be-a-computer exercises

Recursion

Be-a-computer exercises

Kattis problems

Note: Many of the above problems could be solved with an iterative algorithm as well. We expect you to solve these problems recursively, but please note that Kattis cannot tell whether your solution to a problem is recursive or not, so getting an “Accepted” judgement does not necessarily mean that your solution is correct.

Note (2): Several of these problems are from a placement exam. Please ignore any warning about what happens “on the exam”. Those warnings refers to the placement exam, not to the CS 121 exam.

Exam 1

Note: These problems are not representative of the problems you will encounter in the exam. They simply build the kind of skills that will be important to do well in the exam.

Exam 2

Note: Unless otherwise noted, these problems are not representative of the problems you will encounter in the exam. They simply build the kind of skills that will be important to do well in the exam. Unless otherwise noted, do not use recursion in these problems.
  • Black Friday (file: blackfriday.py)
  • Ferry Loading 4 (file: ferryloading4.py)
  • Permutation Encryption (file: permutationencryption.py)
  • Torn to Pieces (file: torn2pieces.py) This question is challenging. We recommend writing two functions: one that computes a dictionary that maps a station to a list of the stations to which it is directly connected and another that looks for a path between two stations (this second function should be recursive)
  • Shortest Manhattan Distance (file: shortmanhattan.py). This recursion problem is from a previous CS 121 exam.
  • It’s All About the Miles (file: miles.py). This recursion problem is also from a previous CS 121 exam.