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:
Throughout this guide, you will see some small Tasks 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.
One of the first steps of problem solving is constructing a mental representation of the problem, known as problem representation. 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.
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:
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.
Information about the initial state is highlighted, while information about the goal state is bolded
Write an expression to determine whether 21 is within 5 years of the constant TARGET-AGE
.
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.
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 |
Next, try repeating the above tasks with this more complicated problem (task 1) from homework 4:
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.
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
).
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.
As a reminder, information about the initial state is highlighted, and information about the goal state is bolded.
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.
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
).
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.
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 |
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.
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:
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.
There are two tables involved in this problem, ART
and CURRENCY-CONVERSION
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.
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.
Task: Now, try combining the answers to the above questions to create a diagram summarizing the data structures involved in the problem.
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, alongside the actual code in Pyret:
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.
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:
Here's an assortment of other strategies that I have found helpful in the past.
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).