CS 1 Placement Exam, academic year 2020-2021

Due: July 31, 2020

This placement exam will help us identify the right place for you to start in computer science courses at Caltech. It is to your benefit to work through this exam accurately and individually. You should be able to work through this task in a few hours. There is no time limit; however, if the exam takes you more than 10 hours, that is a good indication you should start with CS 1.

Before you begin the exam, please review the notes on the cover letter. These notes answer frequently-asked questions about the CS 1 placement exam. Also carefully review the submission notes and coding notes below.

Return the completed exam by July 31, 11:59pm PDT. Submit your answers by email to placement@cms.caltech.edu. Please note that we do not want executables, just the source code you have written. Read the submission notes below for more on this. Note that failure to submit your placement exam correctly may result in you failing the exam.

Questions also may be addressed to placement@cms.caltech.edu. Email is preferred, but you may also send questions to Maria Lopez at (626) 395-3034. DO NOT SEND QUESTIONS THAT HAVE ALREADY BEEN ANSWERED BELOW. However, you may ask for clarifications.

The placement exam consists of two problems, described below. You must write programs to answer both problems to pass the exam. Please read the instructions very carefully before you begin! On rare occasions, we have failed students because they have not read the instructions carefully and have submitted incorrect exams. We hate doing this, so if after reading the material below you still have questions for us, please send us an email and we will reply promptly. Also read the submission notes and coding notes below before you begin; failure to abide by the guidelines listed there may result in your failing the exam. That said, these are not difficult problems and writing programs to solve them should be straightforward if your knowledge of programming is equivalent to that of a student who has taken CS 1.

To help ensure that you read the instructions and coding notes, we are putting them before the problems. Please do not skip to the problems right away! If you do, you are very likely to fail the exam on a technicality. That said, the instructions and notes are not complicated and are not designed to trip you up; we simply want you to know what we expect.


Computer languages you can use

As CS 1 uses the Python programming language exclusively, and CS 2 uses the Java programming language exclusively, we ask that you use either (or both) of these languages to write your code. If your submission is written in any other languages, we will politely ask you to resubmit it.

Please use a reasonably current version of the language(s) you are using. For Python, you must use Python 3, ideally the most recent version. For Java, try to use the most recent version as well.


What to submit and how

Please submit your placement test answers as a single email attachment containing one (1) zip file. The zip file should contain the following directory structure:

CS1_placement_exam_XXX  [directory; replace XXX with your name as described below]
   /problem1  [directory]
      ... files for problem 1 ...

   /problem2  [directory]
      ... files for problem 2 ...

   README.txt  -- OPTIONAL: any notes you want us to read

The name of the zip file should be CS1_placement_exam_XXX.zip where XXX should be replaced with your name. Please don't use spaces; use underscores to separate your first and last names e.g. if your name is "John Smith", you would submit a zip file called CS1_placement_exam_John_Smith.zip. The zip file, when expanded, should contain a single CS1_placement_exam_XXX directory (same substitution for XXX as described above); this directory should have two subdirectories, called problem1 and problem2. They must have those exact names (all lower-case except for the digit); we will be using automated scripts to help us grade your submissions, so if they have incorrect names, the scripts will not work. If you have extra notes on your submissions (e.g. how to compile them) include them in the README.txt file in the CS1_placement_exam_XXX directory. If not, just don't include that file in your zip file. You shouldn't need to submit any other files. The code for problem 1 and problem 2 should be independent; if you have a file of utility functions that is shared between both problems, please include it twice (once in each directory). Also, please do not send executable programs in your submission! We don't need them, since we will compile all of your code ourselves. All of the files in your directories should be in plain text format.

If your submission is not in the format as described above, we will ask you to resend it in that format. If you don't, your placement exam will not be graded. We expect that you know (or can learn) how to create a zip file with the correct structure.

The files you need to submit for each program will be described in detail below.


Other submission notes


General coding notes

We shouldn't have to say this, but we will: All of your code must be written by you and you alone. You are not allowed to get any kind of help from anyone else while writing the placement exam. You can consult on-line or printed documentation for the language(s) you use, but you are not allowed to ask questions about the problems either in-person or online before submitting your placement exam. If we find out that you have violated this rule, you will fail the placement exam.

It's OK to look up information about algorithms and/or data structures on the internet; we're not testing you on your ability to memorize information. However, if you are using any non-trivial data structures, you must write them from scratch and not use e.g. library code from the STL or the Java class libraries. You can use the random number generator(s) provided by your language instead of writing your own, and you can use the fundamental built-in data structures of your language (e.g. the String or ArrayList Java classes, or strings, dictionaries or lists in Python) as you like. If you're not sure about a specific data structure, send us an email and ask us before spending a large amount of time reimplementing something from the language's standard libraries.

Our standards are extremely high. Therefore, we have a lot of coding guidelines you need to follow when writing your programs. This may take a while to read, but we think that reading it is better than failing the placement exam.

Most importantly: This is not just an exam to see if you know how to program. It's an exam to test your knowledge of programming as a whole. The question we are trying to answer is "Would taking CS 1 be a waste of time for you?" If the answer is clearly "no", then you will probably not pass the placement exam even if you do know how to program at some level. Do not take it personally if you don't pass. It is not a reflection on your intelligence or on your aptitude for programming, just on your current level of knowledge. In fact, every year a number of students who do pass the test end up taking CS 1 anyway. One reason you might want to do this is if you want to be a teaching assistant for CS 1 at some later date. Another might be that you want to learn Python in a low-stress situation.

A corollory to the previous point is this: If your programs work correctly, this does not guarantee that you will pass. It's necessary but not sufficient.

Coding style

Your code should be written in a professional style. Specifically:

Automatic fails

For your convenience, here is a quick summary of items that will cause you to automatically fail the placement exam. You might think we are being insanely anal about all of this, and you would be right! You are entering Caltech, and Caltech has very high standards. If you're ready to place out of CS 1, none of these should cause you any problems.


Other notes

In the event that you fail the placement test, we will send you our comments by email explaining how your submission fell short of our standards. However, do not argue with us to try to raise your grade! Unless we have made some gross error (e.g. mistaken your submission for a different one), our decision will stand. Any other attempt to argue with us to change the result will be ignored.

Also, in the event that you fail the test, please don't ask us for a do-over, or ask us if there is any other course you could take (or out-of-course work you could do) instead of taking CS 1. If we feel that you would benefit from taking CS 1, you should take it. Of course, if you don't intend to be a CS major and none of the courses you intend to take require CS 1 as a prerequisite, do whatever you like. But if you do need CS 1 credit, you can only get it by taking CS 1 or placing out of it.

We realize that it isn't pleasant to fail any test, but this is not something you are going to be graded on and it will never appear on your permanent record. We are also not interested in hearing how many programming courses you have taken and gotten As on, how many programming competitions you have won, etc. All of these are fine things to put on your resume, but they are irrelevant to the placement exam. If we failed you, there is some fundamental problem or problems with your programming (at least in the small sample that we've seen), and you will have to take CS 1 to fix these problems. (Usually the problem is not that you're a bad programmer but that you don't know something that CS 1 teaches.) Remember: Caltech is one of the top universities in the entire world, and our standards are extremely high. Most people who fail the placement test have no problem breezing through CS 1 anyway, so we don't feel you will be severely inconvenienced. In many cases, students who failed the CS 1 placement exam aced CS 1 itself and became top-notch CS 1 TAs, making lots of money in the process and getting great recommendation letters from us as a result. So don't worry about it!

Finally, please realize that the CS 1 placement exam is for incoming freshmen only. If you are e.g. a rising sophomore and forgot to take the placement test before coming to Caltech, you can't take it later.


The CS 1 Placement Exam:


Problem 1: Implementing a One-Dimensional Cellular Automaton

Files to hand in

In either case, the file must be in the problem1 directory in your zip file.

Problem description

In this problem, you are to write a program that simulates the operation of a one-dimensional cellular automaton. Many of you are familiar with Conway's "game of life", which is a two-dimensional cellular automaton; a one-dimensional cellular automaton is much simpler, and for this problem your program will simulate a particularly simple one-dimensional cellular automaton. If you like, you can read background material on one-dimensional cellular automata on the internet before attempting this problem; here is a good link, and here is another. You will be implementing a particularly simple kind of one-dimensional cellular automaton called an "elementary cellular automaton", with some additional restrictions described below. Note: do not write a game-of-life simulation for this problem, or you will fail the placement exam! Also, do not call your program "GameOfLife" or something similar, or you will lose marks. One-dimensional cellular automata are not the same as two-dimensional ones, although they are related.

A one-dimensional cellular automaton consists of a one-dimensional array which stores numerical values. For this problem, the numerical values will be either 0 (off) or 1 (on). The contents of the array are initially randomly assigned to be either 0s or 1s (roughly 50% of each; it doesn't have to be exactly 50%, but it does have to be random). Each location in the array is referred to as a "cell" of the array. The contents of the array are altered to give the next generation, which depends on the previous generation and on an update rule. The update rule will compute the new value of each cell depending on the previous value of the cell, as well as the previous values of its left and right neighbors. So the new value of cell 22 (for instance) will depend on the previous values of cells 21, 22, and 23. There are many possible ways of writing an update rule, and we'll get back to this shortly.

After the program generates its initial array, it will print it to the terminal as a line of 0s and 1s (with no spaces or newlines between the digits). So the initial line might look like this (for an array of 70 cells):

1001110111000110001110010010001100101000011000101111110110010110010111

NOTE: This is the format we want for the output (each generation on one line, with no spaces between cell values).

After this, your program will generate the next generation, print it as above, generate the next generation after that, print it, and so on until some given number of generations have been printed. For instance, if 30 generations would be printed (in addition to the original generation, making 31 generations in all), the output might look something like this:

1110000011010011110011110110011001011111101011010111000000010010111001
0001000100011100001100000001100111000000001000010000100000111110000111
0011101110100010010010000010011000100000011100111001110001000001001000
0100000000110111111111000111100101110000100011000110001011100011111100
1110000001000000000000101000011100001001110100101001011000010100000010
0001000011100000000001101100100010011110000111101111000100110110000111
0011100100010000000010000011110111100001001000000000101111000001001000
0100011110111000000111000100000000010011111100000001100000100011111100
1110100000000100001000101110000000111100000010000010010001110100000010
0000110000001110011101100001000001000010000111000111111010000110000111
0001001000010001100000010011100011100111001000101000000011001001001000
0011111100111010010000111100010100011000111101101100000100111111111100
0100000011000011111001000010110110100101000000000010001111000000000010
1110000100100100000111100110000000111101100000000111010000100000000111
0001001111111110001000011001000001000000010000001000011001110000001000
0011110000000001011100100111100011100000111000011100100110001000011100
0100001000000011000011111000010100010001000100100011111001011100100010
1110011100000100100100000100110110111011101111110100000111000011110111
0001100010001111111110001111000000000000000000000110001000100100000000
0010010111010000000001010000100000000000000000001001011101111110000000
0111110000011000000011011001110000000000000000011111000000000001000000
1000001000100100000100000110001000000000000000100000100000000011100000
1100011101111110001110001001011100000000000001110001110000000100010000
0010100000000001010001011111000010000000000010001010001000001110111000
0110110000000011011011000000100111000000000111011011011100010000000100
1000001000000100000000100001111000100000001000000000000010111000001110
1100011100001110000001110010000101110000011100000000000110000100010001
0010100010010001000010001111001100001000100010000000001001001110111011
0110110111111011100111010000110010011101110111000000011111110000000000
1000000000000000011000011001001111100000000000100000100000001000000000
1100000000000000100100100111110000010000000001110001110000011100000000

Note that there is a pattern to the 0s and 1s (try squinting your eyes if you find it difficult to see). Some update rules give interesting patterns, and others don't. Your program will be able to simulate a variety of update rules.

In general, there are 256 different possible update rules you could use (since there are 8 possible previous states for a given cell and its immediate neighbors (0 0 0, 0 0 1, 0 1 0, 0 1 1, 1 0 0, 1 0 1, 1 1 0, and 1 1 1) , and each state could give rise to either a 0 or a 1 in the next generation, giving 28 or 256 different update rules). We will simplify this somewhat as follows: the update rule will sum the states of a cell and its immediate neighbors, and choose a particular next state based on the sum. The possible sums are 0, 1, 2, and 3, representing the case of all 0s, one 1, two 1s, and three 1s. An update rule is specified by giving a next state for each possible sum. For instance, an update rule might be [0, 1, 1, 0], which says that if the sum is 0 or 3, the next state is a 0; otherwise the next state is a 1. It's not hard to see that using sums for update rules will give rise to 24 or 16 different update rules.

You may have noticed that there is a problem with updating the cells on either end of the array, because these cells are missing one neighbor. The way to deal with that is to assume that the missing neighbor has a value of 0. So, to update the first cell in the array (which we'll call cell 0), you will need the previous values of cell 0 and cell 1, which you add to give the sum. Similarly, if there are 70 cells in the array, updating the rightmost cell (which we'll call cell 69, using 0-based indexing) will require the previous values of cell 68 and cell 69, which are again added to give the sum.

One very important aspect of simulating a one-dimensional cellular automaton is that you should not overwrite the contents of the previous generation while computing the next generation. Put differently, you will need two arrays while doing the update: the array of the previous values, and the array of the next values. You will go through the previous values and compute the next values (one for each cell), filling up the next value array without altering the previous value array. After you have finished computing the next values, you no longer need the previous values and you can dispose of that array (or, if you prefer, you can copy the next values into the previous value array). If this is not done, your simulation will not work properly and you won't pass the exam.

Now let's talk about the interface of your program. Your program must be runnable from a terminal (e.g. the Terminal application in Mac OS X, xterm or konsole or gnome-terminal in Linux, or the console application in Windows), and it will take six command-line arguments (not counting the name of the program). These represent:

  1. the number of cells in the automaton (minimum 1)
  2. the number of generations that are being simulated (not counting the initial generation) (minimum 0)
  3. four numbers (either 0 or 1) that represent the update rule

If you don't know what a command-line argument is or how to read command-line inputs in your computer language, you should learn about this before solving this problem. It's not hard in any of the languages we recommend. Asking the user to interactively enter inputs is not acceptable, so make sure to get this right. Otherwise, your program will be considered to be broken.

So, a sample run of the program might look like this (in a Linux or Mac OS X terminal; the $ is the terminal prompt):

$ python3 automaton.py 70 30 0 1 0 0
1110000011010011110011110110011001011111101011010111000000010010111001
0001000100011100001100000001100111000000001000010000100000111110000111
0011101110100010010010000010011000100000011100111001110001000001001000
0100000000110111111111000111100101110000100011000110001011100011111100
1110000001000000000000101000011100001001110100101001011000010100000010
0001000011100000000001101100100010011110000111101111000100110110000111
0011100100010000000010000011110111100001001000000000101111000001001000
0100011110111000000111000100000000010011111100000001100000100011111100
1110100000000100001000101110000000111100000010000010010001110100000010
0000110000001110011101100001000001000010000111000111111010000110000111
0001001000010001100000010011100011100111001000101000000011001001001000
0011111100111010010000111100010100011000111101101100000100111111111100
0100000011000011111001000010110110100101000000000010001111000000000010
1110000100100100000111100110000000111101100000000111010000100000000111
0001001111111110001000011001000001000000010000001000011001110000001000
0011110000000001011100100111100011100000111000011100100110001000011100
0100001000000011000011111000010100010001000100100011111001011100100010
1110011100000100100100000100110110111011101111110100000111000011110111
0001100010001111111110001111000000000000000000000110001000100100000000
0010010111010000000001010000100000000000000000001001011101111110000000
0111110000011000000011011001110000000000000000011111000000000001000000
1000001000100100000100000110001000000000000000100000100000000011100000
1100011101111110001110001001011100000000000001110001110000000100010000
0010100000000001010001011111000010000000000010001010001000001110111000
0110110000000011011011000000100111000000000111011011011100010000000100
1000001000000100000000100001111000100000001000000000000010111000001110
1100011100001110000001110010000101110000011100000000000110000100010001
0010100010010001000010001111001100001000100010000000001001001110111011
0110110111111011100111010000110010011101110111000000011111110000000000
1000000000000000011000011001001111100000000000100000100000001000000000
1100000000000000100100100111110000010000000001110001110000011100000000

(Here, we are assuming that your program is in Python, but Java is acceptable too.)

Notice that there are 70 digits per line (70 cells in a generation), and 31 lines (the initial generation + 30 subsequent generations). The 0 1 0 0 numbers are the update rule for this run of the program; they say that if the sum for a particular cell is 1, the value of the cell in the next generation will be 1; if the sum is 0, 2, or 3 the next value of the cell will be 0. You can check that this is in fact the case.

The output format should be exactly as shown above, except that if you have a different number of generations or a different number of cells in a generation, the display will be respectively deeper/wider. We will severely penalize you if you put spaces between the 0s and the 1s, put blank lines between the lines of numbers, have all the numbers on a single line, etc. (This exam is partly an exam to see if you can read a specification and complete it exactly as instructed.)

Note that you will need to use a random number generator to generate the initial generation. You can use a library function for your chosen language; you certainly shouldn't write your own random number generator, unless you have a lot of free time!

Please make sure that all of your code is inside of functions and/or methods, even if it would be easy to have some of the code outside of functions and methods (which is the case in Python). This even includes the code that handles command-line arguments. For Python we allow this exception: you can have a single line that calls a function at the end of the program.

One final thing: if your program receives incorrect inputs (too few command-line arguments, or incorrect ones i.e. non-numbers, negative numbers or numbers other than 0 or 1 in the update rule), it should print a meaningful error message and quit. It should not continue to execute, fail silently, crash, or interactively prompt the user for correct inputs. You should allow any integer number of cells >= 1, and any number of generations >= 0. If there are 0 generations, just print out the first (random) generation.


Problem 2: The Tower of Hanoi

Files to hand in

In either case, the file must be in the problem2 directory in your zip file.

Description of the problem

This problem is a classic computer science problem called "the tower of Hanoi" which illustrates how recursion coupled with a divide-and-conquer strategy can enable you to trivially solve a problem which appears to be very difficult. Note that there are several different ways to solve this problem; we want you to do this recursively because the whole point of this problem is to see if you are comfortable using recursion. (Non-recursive solutions will fail the placement exam, so don't submit one.)

The set-up for the problem is as follows. You have three pegs, on which there are some disks of different sizes. All the disks start on the first peg. The disks on the first peg should be set up so that all the disks have different sizes and larger disks are always underneath smaller disks. No disk is smaller than size 1. The other two pegs start off empty. Your job is to move all the disks to the second peg so that they end up in the same order as they were on the first disk (with the smaller disks on top of the larger ones). You can only move one disk at a time, and a disk can only be moved to an empty peg or to a peg whose top disk is larger than the disk being moved. Disks do not have to be placed on pegs in consecutive order i.e. it's OK to have disk 5 on top of disk 10 (but not on top of disk 4).

The algorithm to solve this problem goes like this. We'll call our pegs peg A, peg B, and peg C. Assume you want to move the top M disks (where M <= N) from peg A to peg B.

  1. First, handle the base case i.e. the case that can be solved immediately. Here, the base case is when there is only one disk to move (M = 1). In that case, you just move the disk (assuming that it's legal to move it).

  2. If M > 1, the process is as follows:

    1. Move the top M-1 disks from peg A to peg C.
    2. Move disk M from peg A to peg B.
    3. Move the top M-1 disks from peg C to peg B.

    Note that steps 1 and 3 involve recursive calls to this algorithm. We call this the recursive case.

Both of these cases should be handled in the same method. Also, use this exact algorithm (not some variant of it). In particular, don't use a non-recursive variant of the algorithm (yes, they exist!).

Amazingly enough, that's all there is to it. Recursive algorithms may seem like magic, but they can be understood by analogy with mathematical induction. With mathematical induction, you want to prove that something is true for all numbers N > 1. To do this, you prove that it's true for N = 0, and then you show that if it's known to be true for N-1, it can be proven to be true for N. Given that, you can show that it's true for any N > 0. Here, we see that we can move 1 disk (N = 1). If we know that we can move N-1 disks, then it's clear that we can move N disks (that's the recursive case).

Another useful thing to do is to take a small example (for instance, with disks of sizes 3, 2, and 1 on peg 1) and work through the above algorithm on pencil and paper until you convince yourself that it does work.

The program

Your program will be called as follows:

$ python3 hanoi.py [n1 n2 ...]

(assuming you're using Python; for Java, it would be java Hanoi [n1 n2 ...]

where $ is the terminal prompt and [n1 n2 ...] are the sizes of the disks that start on the first peg (these are command-line arguments). If no numbers are supplied, the script should print out a helpful usage message and exit. For instance, if you are calling the program with 4 disks: 4 3 2 1, it will look like this:

$ python3 hanoi.py 4 3 2 1

What this means is that the first peg will start off with four disks of sizes 4, 3, 2, and 1, with the largest (4) on the bottom, then 3, then 2 and 1 on the top.

Alternatively, if you are calling the program with 3 disks: 10 4 2, you will invoke the program like this:

$ python3 hanoi.py 10 4 2

You can see that the disk sizes do not have to be consecutive integers. In this case, the first peg will start off with a disk of size 10 at the bottom, then a disk of size 4, and then a disk of size 2 at the top.

All disk sizes must be positive integers; anything else should give rise to an error message and a usage message describing how to call the program correctly. However, you can give inputs like this:

$ python3 hanoi.py 4 10 2

or like this:

$ python3 hanoi.py 4 10 4

These are not invalid invocations of the program (so they don't give rise to a usage message), but the algorithm will not work on them, so eventually the program will fail. When it does, it should print out a meaningful error message and exit. We will use inputs like these to test how your program handles errors.

Your program should define a class called Hanoi which encapsulates all the state variables of the problem. Not defining a Hanoi class will result in your failing the placement exam. Instances of the Hanoi class should have an explicit representation of which disks are on which pegs at any given time.

Here are the methods your program should contain:

Note that it's not enough to just have methods with these names. They must work exactly as described above, or you will fail the test.

You may (in fact, you almost certainly will) want to define other methods as well, which is OK. For instance, you may want to define a helper method called by solve that takes some arguments.

In addition, you should print out the state of the problem (using your display function or method) before you start and after each move. The display should look exactly like this (for 8 disks numbered 1 through 8):

    A: 4 1
    B: 8 7 6 5
    C: 3 2

where A:, B:, C: identify the pegs and the numbers identify the disks. The "bottom" of the pegs are to the left and the "top" of the pegs are to the right. Make sure that printouts for successive moves are separated by at least one blank line. The final printout should show all the disks on peg B, so if there were 8 disks from 8 down to 1 initially, the first printout would be:

    A: 8 7 6 5 4 3 2 1
    B:
    C:

and the final printout would be:

    A:
    B: 8 7 6 5 4 3 2 1
    C:

As mentioned above, successive states of the game should be separated by a blank line when printed out. The spaces between the numbers are not optional! Your program should work for arbitrary numbers of disks and the output needs to be readable in all cases, except that for very large numbers of disks on a peg it's OK if the line wraps on the terminal. Put differently, each peg's printout should be on a single line.

Sample runs

$ python3 hanoi.py 10 4 2
A: 10 4 2
B:
C:

A: 10 4
B: 2
C:

A: 10
B: 2
C: 4

A: 10
B:
C: 4 2

A:
B: 10
C: 4 2

A: 2
B: 10
C: 4

A: 2
B: 10 4
C:

A:
B: 10 4 2
C:

$ python3 hanoi.py 4 10 2
A: 4 10 2
B:
C:

A: 4 10
B: 2
C:

A: 4
B: 2
C: 10

A: 4
B:
C: 10 2

A:
B: 4
C: 10 2

A: 2
B: 4
C: 10

<error message>

Note that you need to supply the <error message>, which arises because the algorithm wants to put the 10 disk on top of the 4 disk, which is invalid. (The algorithm given above assumes that disks start out in descending order on one disk; if they don't, it won't work correctly.)

Coding notes for problem 2

This problem is intended to test your knowledge of object-oriented programming, your ability to define and use data structures, your ability to handle error situations, and your ability to write recursive code. Therefore, in addition to just solving the problem, we want your solution to have the following features:

We realize that such a simple program can probably be solved more simply than by doing it the way we recommend, but we are trying to see how much you know about object-oriented programming, designing data structures and recursion, so please do it our way.


[End CS 1 placement exam.]


Copyright (c) 2020, California Institute of Technology. All rights reserved.