---
title: (unofficial) cs111 problem solving guide
---

# Breaking Down Computer Science Problems

Solving problems on computer science projects or homeworks can often be a daunting task, especially when you're not sure where to start. This guide aims to facilitate the process of problem solving in computer science.

By the end of this guide, you'll have practiced:
* Defining problem representation and understanding why it's important
* Identifying strategies for generating problem representations
* Constructing several kinds of problem representations for different contexts
* Intepreting representations constructed by experts

Throughout this guide, you will see some small **Task**s for you to complete, as well as our answers, which can be revealed by clicking on the arrow. Although you are not obligated to complete the tasks before revealing the answers, you will get the most out of this guide if you attempt the tasks beforehand.

## Problem Representation: An Overview
One of the first steps of problem solving is constructing a mental representation of the problem, known as [problem representation](https://www.projectpals.com/project-based-learning-blog/why-is-problem-representation-so-important-for-problem-solving). At its core, problem representation is the act of organizing the information given in a problem into a more efficient manner. Although shorter problems can sometimes be solved without explicitly thinking about their representation, being able to break down and reorganize information is critical to effective problem-solving, especially as problem statements get longer.

### Identifying Initial and Goal States
Problem representation usually requires identifying the **initial state** (the present situation or information) and the **goal state** (the desired situation or product) of the problem. Consider this example problem (task 3) from [homework 2](https://hackmd.io/@cs111/hw2-f22#Part-2-Writing-Expressions):
:::info
Write an expression to determine whether 21 is within 5 years of the constant `TARGET-AGE`.
:::
**Task:** Visually mark the parts of the problem that tell us about the initial state and goal state, respectively.

:::spoiler Once you are done, click to reveal our answer!
Information about the initial state is ==highlighted==, while information about the goal state is **bolded**

:::info
Write **an expression** to determine whether **==21== is within ==5 years== of the ==constant `TARGET-AGE`==**.

:::
<br/>

As you can see, this problem is simple enough that visually scanning the problem more or less suffices to identify the initial and goal states. However, sometimes it is not immediately obvious from the problem what the initial and goal states are. In these scenarios, it helps to explicitly write out the iniital and goal states.

**Task:** Using the same example problem from homework 2, write out (in prose or list form) the initial and goal states.

:::spoiler Click here to see our answer!
| Initial state | Goal state |
| - | - |
| Our initial state consists of three numbers: 21, 5, and the constant `TARGET-AGE` | The goal state is an expression that compares the numbers in a way that determines whether or not 21 is within 5 years of `TARGET-AGE` |
:::
<br/>

Next, try repeating the above tasks with this more complicated problem (task 1) from [homework 4](https://hackmd.io/@cs111/hw4-f22#Part-1-Prices-Under-Exchange-Rates):

:::info
Companies that do business internationally need to be able to quote prices in different currencies, following a table of exchange rates. This is the kind of situation where one would have two separate tables: one with the prices of items, and another with the exchange rates per country. For this problem, we'll be computing currency conversions for an online art store in which artists and clients may be in different countries.

The store has two tables, that are both in your starter code. One is for artwork, called `ART`: it tracks the unique id, cost and base currency for each piece.

table: id :: Number, cost :: Number, currency :: String

The other table is for currency conversion, called `CURRENCY-CONVERSION`. Each row holds the conversion rate (the multiplicative factor) to convert from the first currency (`from-c`) to the second (`to-c`).

table: from-c :: String, to-c :: String, conv-rate :: Number

**Task 1:** Consider a function `get-art-in-1` that takes an artwork (by ID number) and a desired currency (a string) and returns the price of the artwork in the given currency. The given currency may or may not be the one listed for the piece in the artwork table. If the artwork is listed in a different currency, use the conversion table to produce the price. You can assume that every artwork queried is listed exactly once in the artwork table, and that every pair of currencies you need is listed exactly once in the currency conversion table.
:::
::: spoiler Answer: Visually marking initial and goal state information
As a reminder, information about the initial state is ==highlighted==, and information about the goal state is **bolded**.
:::info
Companies that do business internationally need to be able to quote prices in different currencies, following a table of exchange rates. This is the kind of situation where one would have two separate tables: one with the prices of items, and another with the exchange rates per country. For this problem, we'll be computing currency conversions for an online art store in which artists and clients may be in different countries.

The store has two tables, that are both in your starter code. One is for artwork, called ==`ART`: it tracks the unique id, cost and base currency for each piece==.

table: id :: Number, cost :: Number, currency :: String

The other table is for currency conversion, called ==`CURRENCY-CONVERSION`. Each row holds the conversion rate (the multiplicative factor) to convert from the first currency (`from-c`) to the second (`to-c`)==.

table: from-c :: String, to-c :: String, conv-rate :: Number

**Task 1:** Consider a **function `get-art-in-1`** that takes an ==artwork (by ID number) and a desired currency (a string)== and **returns the price of the artwork in the given currency**. The given currency may or may not be the one listed for the piece in the ==artwork table==. If the artwork is listed in a different currency, **use the ==conversion table== to produce the price**. You can assume that every artwork queried is listed exactly once in the artwork table, and that every pair of currencies you need is listed exactly once in the currency conversion table.
:::
:::spoiler Answer: Summarizing initial and goal states
| Initial state | Goal state |
| - | - |
| Our initial state is the artwork's ID number, the desired currency, and the two tables (`ART` and `CURRENCY-CONVERSION`) | Our goal state is a function that uses our initial information to produce the price of the given art piece |
:::

### Representing Data Structures and Algorithms
Problems in computer science often involve **data structures** which are used to organize information for the computer, as well as **algorithms** which detail the steps the computer takes to complete a task. Being able to understand and represent these is another important aspect of problem representation in computer science.

#### Data structures
After identifying the initial and goal states, it is often helpful to think about the data structures invovled in the problem. Answering the following questions can help guide your thinking about data structures:
1. What data structures are involved in this problem? Which types of data structures are involved?
2. How are these data structures organized? Do they have any special structure or function (i.e. ordering, etc.)?
3. If there are multiple data structures invovled: How are these data structures related to each other? Are there shared or corresponding parts in various data structures?

Using the answers to these questions to *visualize or diagram data structures and their relations* can also be helpful.

**Task:** Answer the above questions for the sample problem from homework 4.

:::spoiler 1.
There are two tables involved in this problem, `ART` and `CURRENCY-CONVERSION`
:::
:::spoiler 2.
The `ART` table has columns for art id, price of the art piece, and the currency the price is listed in. The `CURRENCY-CONVERSION` table has columns for two currencies and a column for the multiplicative conversion factor between the two.
:::
:::spoiler 3.
The `currency` column in the `ART` table corresponds to one of the currencies in either the `from-c` or `to-c` columns in the `CURRENCY-CONVERSION` table.
:::
<br/>

**Task**: Now, try combining the answers to the above questions to create a diagram summarizing the data structures involved in the problem.
:::spoiler Our diagram!
:::

#### Algorithms
Similarly, thinking about the algorithms involved in reaching a goal state is a useful aid for planning an approach. *Pseudocode* is a powerful tool that makes the process of mapping out algorithms easier. Pseudocode is written by writing "code" that doesn't necessarily belong to any language, but rather outlines general steps that programmers can then convert into "correct" code in their language of choice. For example, here is the pseudocode for the `candy-with-attr` function from [lab 3](https://hackmd.io/@cs111/lab3-spring2022#16-Chocolate-and-anything), alongside the actual code in Pyret:
###### Pseudocode

function chocolate-only(row):
    checks whether the chocolate column in the row is true

function candy-with-attr(table, attr):
    function filter-helper(row):
        checks whether the attr column in row is true and
        if chocolate is true
    choco-and-attr = length(filter(table, filter-helper))
    choco-only = length(filter(table, chocolate-only))
    return chocolate-and-attr / choco-only

###### Pyret

fun chocolate-only(r :: Row) -> Boolean:
    r['chocolate']
end

fun candy-with-attr(table :: Table, attr :: String) -> Number:
    fun filter-helper (r :: Row) -> Boolean:
        r[attr] and r['chocolate']
    end
    choco-and-attr = filter-with(table, filter-helper).length()
    choco-only = filter-with(table, chocolate-only).length()
    choco-and-attr / choco-only
end

As you can see, since pseudocode is meant to be understood by humans, it can afford to not be exact in terms of syntax. While the majority of the pseudocode looks similar to real code, sections that were ambiguous, unclear, or unknown in terms of how to actually implement were just left in natural language describing the operations that would need to be done.

**Task:** Write pseudocode for the `get-art-in-1` function from homework 4 that we have been working with. Feel free to be as verbose or specific as you want! The important part is to capture the overall structure of the code.

:::spoiler Our pseudocode

function get-art-in-1(id, currency):
    id-row = look up row in ART table with value in id column == id
    row-currency = extract value in currency column from id-row
    price = value of price column from id-row
    if currency == row-currency:
        return price
    else:
        conversion-row = find row in CURRENCY-CONVERSION where the value in 
        the from-c and to-c match currency and row-currency (or vice versa)
        conv-r = value of conv-rate column in conversion-row
        if from-c == row-currency:
            return price * conv-r
        else: # to-c == row-currency, need a backwards conversion
            return price * (1 / conv-r)

:::

## Conclusion
Programming is a difficult skill to learn, and this document is meant to help familiarize you with some of the basic strategies used to solve computer science problems. That being said you've been using these strategies already without realizing it or not, none of the above or below strategies is a silver bullet! Summarizing what we've learned so far, here are several of the tools available to you before you start coding:
* **Visually mark up the problem.** This helps reduce the wall-of-text nature of the handouts and enables you to hone in on key information about the question.
* **Explicitly restate the initial and goal states.** Putting things into your own words makes it clear what you know (and don't know) and is generally a useful check for your own understanding.
* **Diagram!** Drawing out parts of the problem or creating other visual representations reduces the load on your working memory and allows you to efficiently see relationships between various parts of the problem.
* **Write pseudocode.** This is another way of writing out the steps of what you need to accomplish, but in a form that is closer to what you will eventually need to write. Learning to read and write pseudocode also helps align your thought processes with that of the computer.

### Addendum: Miscellaneous Strategies
Here's an assortment of other strategies that I have found helpful in the past.
* **Reread the problem.** Read the problem out loud. Read the problem out loud to a friend. Have a friend read the problem out loud to you. A lot of the time, the key information you were missing was tucked away in the handout or in the wording of the problem somewhere. If your initial representation of the problem is insufficient, then sometimes revisiting the original statement helps!
* **Write and work through some concrete examples.** You've heard us say it before, and you'll hear us say it over and over again: writing examples is not only a critical skill for programmers, but also a powerful tool to help ground your understanding of the problem. It also just so happens that writing and working through a concrete example takes you through most of the steps of representing data structures and algorithms that we just covered :^)
* **Take a break.** Go take a walk, read a book, eat a snack, take a nap, or anything that doesn't involve computer science for a few minutes/hours/days. Take late days if need be. Let your brain do its thing in the background - it's incredible how often a fresh, well-rested pair of eyes can pick up on things you may have missed before. A tired, panicked coder is never a very effective coder.
* **Think aloud.** This may not have immediate effects, but narrating your thoughts as you solve a problem can be a great way to identify where in the problem-solving process you might be getting stuck. Try recording yourself talking out loud as you work through a problem; you can go back and listen to your thought process to understand your own thinking better.

#### Disclaimer
:::success
This guide was written by James Park '23 (EDUC/CSCI), a four-time TA of cs111 as part of his capstone project for the education department, and is not (yet) officially endorsed by the course. This would theoretically be offered to students as supplemental material before beginning Project 1 (after finishing homework 4).
:::