Before this is due, we will have expanded your abilities so that you can make extensive use of loops in your code to go along with functions and conditionals. Pick one of the options below to complete. We are now getting to the point where you don't want to just start coding. You want to start by sitting down and thinking about what your code needs to do and how you are going to make it do it, paper and pen might even be helpful for this. I can almost promise that every minute spent really thinking about what you are going to be doing will save you 2 minutes of coding/recoding/debugging.
After each problem description I've given you sample input and output files. If you run the program with the input I give, you should get something pretty much identical to my output.
As a side note, be sure to save the code from all the programs you do. It is quite possible that later in the semester other assignments will include things that overlap with them and your code will be reusable.
Standard Problem:
If you choose this option, you will write a little program that does encryption and decryption of a message that you type in. You will also write the code to decrypt that same message. By using redirection of I/O you will be able to easily test to see if it works. Your program will not only have a main, but at least three other functions called encrypt, decrypt, and readTo10.
The encryption your program does will be a 2 part encryption. First, it will offset the characters in the ascii set by a given amount. Then to make things harder, it will throw in a random character after every nth character in the message. So the input of your program will be an e or d followed by two numbers, offset and spacing. Offset is what you will add to all the character values and should be between 1 one 10. Spacing is how far it is between the randomly inserted characters. After that, on a new line, will be the message itself. If the first letter was an e you should do encryption, otherwise do decryption.
Both the encrypt and decrypt functions will have a return type of char. You probably need to pass in the offset and spacing values. Depending on how you design your code, other values might need to be passed in as well.
The encrypt function will first check to see if it is time to insert a random character. If it is it will return a random character generated using the rand function. You can just put return rand()%26+'a'; into the code at that point. The rand function is part of stdlib.h and you can use "man 3 rand" to get more information on it. If it isn't time to insert a new character, you should read one character from standard input, scanf("%c",&oneChar), then return the character that is "offset" positions above it in the ascii table, oneChar+offset.
The decrypt function does something very similar to the encrypt function. If it is at a position where a random character would have been inserted, it reads in one character and ignores it. Whether or not is has reached "spacing" yet, it will read in a character and then return the character that is "offset" below that character in the ascii table.
The readTo10 function is just reads in characters until it gets to one with an integer value of 10 which is a newline. You need this to make sure that you read all the way to the end of the first line before the message.
Back in main, after you read in the 'e' or 'd', the two integers, print them out, and call readTo10, you will want to go through a loop as long as there is more to be read. If you are using file redirection you can do this by looking at the return value from scanf. We haven't looked at this previously, but if you do a "man scanf", you will find that its return type is not void. Instead, it returns how many things it read in. If you try to read a character and this value is less than one then there was nothing left to read. I will leave it to you to decide how to turn this return value into something that will tell the loop in your main to stop. If you just type in your output instead of using I/O redirection, you will have to use ctrl-C to stop when you have put in everything you want.
To see what the program wants to read in and will print out look at the files below at examples that I did. Your encrypted version doesn't have to match mine perfectly, there is randomness after all, but when you decrypt your encrypted one it needs to be identical to the input you use.
orginal file : encrypted file : decrypted file
Graphics Problem:
For this problem I want you to take the ray tracing code that we wrote in class and use it to write a very basic ray tracer that just maps out the objects, but doesn't do any lighting or anything like that. The way a ray tracer works is that you pick the location of the viewer (p0) and then pass rays through a plane in front of the viewer (p1) and see if they hit anything. You pass one ray for each pixel of the image you want to draw.
To keep things simple, we will assume the eye (p0) is at the location (0,-1,0). We will also use coordinates such that the X-axis points to the right, the Y-axis points out in front of you, and the Z-axis is up. This is a good right handed coordinate system. We will have the plane that we are casting rays through be a square that goes from (-1,0,1) at the top left to (1,0,-1) at the bottom right. Input will come in a standard format and you shouldn't prompt the user for input. The reason for that is because we want to output to be a file full of numbers.
The format of the input is as follows. It begins with a number giving you the number of pixels to draw across or up and down the image. So if the value were 10 (which would make a really small image) you would test 100 rays. Remember that loops are your friend since a real input will likely be 100 (10,000 rays) or bigger. On the line after that number will be either the character 's' or the character 'p', standing for sphere or plane. If the letter is 's' the next line will have four numbers for the center position and radius of the sphere. If it is a 'n' then the next line will have six numbers giving a point in the plane and the normal vector.
First your program should print the size of the image. If you read in 100, print out a line with "100 100". You are then to run through all the rays passing through the viewing plane and for each out output the distance between the eye and the intersect point if that ray intersects the object. If the ray doesn't intersect the object output a negative value. You should go across each row in the x direction and move down one row at a time in the z direction. So the first ray you trace will go through (-1,0,1). This output can actually be treated as something like an image of what you are seeing. Below the links for the sample inputs and outputs is a link to a Java JAR file that will let you view your output. On the lab machines you can run it by typing "java -jar RasterViewer.jar". This will give you the various usage options. To see the "image" you need to at least provide a filename for it to read. Use redirection in C to send the output of your program to a file.
Note that you might not get an output that matches mine character for character. However, if you view them they should look very similar.
sphere input : sphere output : plane input : plane output
Biology Problem:
An interesting twist that biology has taken over the past few decades is the ability to look at the populations of different species and how they interact with one another. Often, the way in which different populations vary over time can be approximated by simple mathematical expressions. In this assignment you will use your basic knowledge of loops, conditionals, and functions to examine a simple case where you have two different populations that interact in a preditor-prey manner.
The simplest form of this problem is the rabbit and fox scenario. The idea is that each summer you go out and count the population of rabbits and foxes in a certain region. This region is fairly well isolated so you don't have animals coming in or leaving. In addition, the climate is extremely temperate and there is always enough grass so environmental factors don't seem to impact the populations. All that happens is each year the rabbits try to eat and have babies while not getting eaten and the foxes try to catch rabbits. We will make up some formulas for what happens to the population from one year to the next and you will write a program to do this sequence.
Over the course of each year the rabbit population will be impacted in the following ways. Some rabbits will be born, some rabbits will die of natural causes, and some rabbits will be eaten. Similarly some foxes will be born and some will die. The number of rabbits eaten depends upon the population of foxes in the previous year (more foxes eat more rabbits) and the number of foxes who are born and die depends on the number of rabbits because foxes can't live long or have young without finding rabbits to eat. We can combine these things to come up with some equations that predict the numbers of foxes and rabbits in a given year based on the number in the previous year.
Here we assume that the natural tendancy of rabbit populations is to increase without foxes around and the natural dendancy of fox population is to decrease with rabbits around. The 4 constants should have positive values. A represents the normal increase in rabbit population without predation. B is the predation rate and is multiplied by both the rabbit population and the fox population because if either one is small, the predation rate is small. C is the rate at which foxes would normally die out without being able to bear young (if they didn't have enough food). D is the rate at which fox will bear young when they do have rabbits to feed on.
The input for your program is the initial rabbit population, R(0), the initial fox population F(0), and the four constants. To start you off, you might try values of 100, 10, 0.01, 0.001, 0.05, and 0.001. You can play with these values to try to find some that produce interesting results. Print out the first 1000 iterations of your loop. To make it so that you can see your results easily, I want your output to be only numbers. Never prompt for anything. The advantage of this is that you can create a file that is easy to plot with a program like gnuplot. When you run the program you redirect the output to a file then you can run gnuplot and plot it with that to see what it looks like. If you print 3 numbers per line, n R F, and put it in a file called pop.txt then you can plot that in gnuplot with a command like plot 'pop.txt' using ($1):($2), 'pop.txt' using ($1):($3). There are many other options in gnuplot and you can use the help command in gnuplot to see them.
For extra credit, put a comment in your code documenting some interesting behaviors that you saw at different input values.
Physics Type:
Computers are used extensively for simulating physical systems, especially when the system is hard/impossible to build in a lab. For this assignment I'm interested in having you write a very simple simulation of the gravitational Kepler problem. You will also explore the accuracy of what you are doing a little bit. Imagine you have a body in orbit around a star. We'll assume that the star is much larger than the other body so it stays at the origin, (0,0), of our coordinate system. The other body starts at some position (x,y) with a velocity (vx,vy). A simple "integrator" for a system like this can be constructed by discretizing Newton's laws (a fancy way fo saying that we avoid calculus and do things in a way that is more computer friendly). Newton's second law tells us F1=m1*a1 and fro gravity F=-G*m1*m2/(r*r). We're going to simplify this a fair bit for our toy system and just say that a=-1/(r*r). We can break this into components and get ax=-x/(r*r*r) and ay=-y/(r*r*r). Now, the trick on the computer is to say that instead of moving smoothly, the particle jumps over certain timesteps, dt. So after one timestep the new position is x=x+dt*vx and y=y+dt*vy. Similarly, vx=vx+dt*ax and vy=vy+dt*ay. Doing this in a loop "integrates" the motion of the body. (Use the sqrt function in math.h to calculate r.)
This integrator is very simple, but far from perfect. If you start with your body at (1,0) with a velocity of (0,1) it should be in a nice circular orbit staying that distance forever. By measuring how that distance changes, you can get a measure of how accurate, or inaccurate, the integrator is. You can play with other positions and velocities to see what happens. as well.
If you choose this part, you will write a program that takes the initial x, y, vx, and vy as well a a timestep, dt, as inputs.It should then advance the system for a total time of 10.0 (so if dt=0.1 that requires 100 iterations). At the end of it you should measure the distance from the origin and print a message giving that and the original distance. Then check to see if the change is less than 1%. If it is, say that the integration was accurate enough, otherwise say it isn't. In a comment in your code you should tell me how small you had to make your timestep for this to be reached given the coordinate 1 0 0 1. (I should note that this measure of accuracy is only good for circular orbits. We aren't going to do enough physics to go beyond that, but if you happen to want to, the real objective is to conserve total energy. You can get extra credit by comparing inital and final total energies of the system.)
For fun you can change it so it prints the x and y values during the simulation and see what is happening with gnuplot in a manner similar to what is described in the biology problem. This can also be helpful for debugging. I have included such prinouts in the sample output.
Logic/Football:
This problem is something of a standard at high school programming contests. You should prompt the user for a football score and then print out the ways that score could have been achieved. For large numbers that is a long list, so I'll ask that you only print 5 ways it could have been reached.
If you aren't familiar with football there are several ways to score and they result in different numbers of points. (I'm going college rules a full description of which can be found here.)
Math Type:
One of the useful things that you learn in calculus is that functions can be approximated. Your calculus text will mention both the Maclaurin series approximation and the Taylor series approximation. They are basically the same other than Maclaurin series are always taken about x=0 and this is what we will be working with here. The definition of the Maclaurin series is f(x)~sum_i(x^i * (d/dx)^i(f(0)) / i!). So this is the sum from i=0 up to some n (or infinity if you want to be really accurate). In the sum we have x raised to the i power (not an xor here) times the ith derivative of f(x) evalutated at 0 divided by i factorial. Obviously, this is a real pain to use on functions where taking the derivative isn't easy. However, for some functions where the derivatives are straightforward, performing this approximation is very easy. Examples of that would be e^x, sin(x), and cos(x). I want you to write a program that does a Maclaurin approximation of cos(x). That's not really that hard because the derivative is -sin(x), which has a derivative of -cos(x) which goes to sin(x) then back to cos(x). Also note that you are always evaluating at x=0 so all the terms for sin go to zero.
The first few terms in this series are:
1-0-x^2/2!+0+x^4/4!-0-x^6/6!+0+x^8/8!+...
For the assignment, I want you to ask the user for the x to use, as well as an accuracy. Use the math library function cos to get the real value of cosine at that value of x. Then iterate until the difference between the series value and what that function gives you is less than the input accuracy. After the loop, print out the real value, the value you got from the series, and how many terms you had to sum in it. (For extra credit, make your program use a Taylor series instead. This means inputing another value x0 which the series is expanded around.)
Utilizing the Stack:
This problem is smaller than the others in some ways, but it has an interesting twist to it. For this one you won't code so much, but you definitely have to think more. When given a set of numbers, there are many different things that you can calulate from them. The average (arithmetic mean), median, mode, and geometric mean are values you should all have heard about at some point in your math educations even if you don't remember exactly what they are. In the sciences, another value that is particularly important is the standard deviation (root mean square/RMS). This value is defined as the square root of the average of the squares of the deviations of the values. That's a few too many clauses stuck together. We could write it mathematically as this sqrt(sum((x_i-average)^2)/N), where x_i is the ith number in the sequence, average is the average of the numbers, and N is the number of numbers. I've used ^2 here for squaring, but of course you can't do it that way in C as ^ is bitwise xor.
Calculating this number takes two passes through the values. The first one has to find the average while the second finds the sum of the deviations. We haven't yet learned about a way to store off a variable number of values nicely yet (and even if you know about arrays you aren't allowed to use them for this). For this path I want you to write a program that calulates the RMS value given an input like the following: N x1 x2 x3 ... xn. The user will input how many numbers there are, then each number. They will not input them twice. You can use a static local variable here (feel free to ask what that is in class, but not a global variable).