Exam 1: Scheme and Image Basics

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.

This examination has a prologue that must be completed by the Friday afternoon before the exam is due. The prologue is intended to help you get started thinking about the examination. The prologue is optional. However, if you intend to invoke the “there's more to life” option (see below), you must turn in the prologue by the specified deadline.

There are seven problems on this examination. Each problem is worth the same number of points. Although each problem is worth the same amount, problems are not necessarily of equal difficulty.

Read the entire exam before you begin.

We expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about three to four hours, depending on how well you've learned the topics and how fast you work. You should not work more than five hours on this exam. Stop at five hours and write “There's more to life than CS” and you will earn at least the equivalent of 70% on this exam, provided you filled in the prologue by the specified deadline. You may count the time you spend on the prologue toward those five hours. With such evidence of serious intent, your score will be the maximum of (1) your actual score or (2) the equivalent of 70%. The bonus points for errors are not usually applied in the second situation.

We would also appreciate it if you would write down the amount of time each problem takes. Each person who does so will earn two points of extra credit for the exam. Because we worry about the amount of time our exams take, we will give two points of extra credit to the first two people who honestly report that they have completed the exam in four hours or less or have spent at least four hours on the exam. In the latter case, they should also report on what work they've completed in the four hours. After receiving such notices, we may change the exam.

This examination is open book, open notes, open mind, open computer, open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. If you use code that you wrote for a previous lab or homework, cite that lab or homework as well as any students who worked with you. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. And, in case it's not clear, you may not ask others (in person, via email, via IM, via IRC, by posting a please help message, or in any other way) to put answers on the Web.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say “This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing.” You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must include both of the following statements on the cover sheet of the examination.

Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky.

Exams can be stressful. Don't let the stress of the exam lead you to make decisions that you will later regret.

You must present your exam to me in two forms: both physically and electronically. That is, you must write all of your answers using the computer, print them out, number the pages, put your name on the top of every page, staple them together, and hand me the printed copy. You must also email me a copy of your exam with the subject CSC 151.01 Exam 1 (Your Name). You should create the emailed version by copying the various parts of your exam and pasting them into an email message. In both cases, you should put your answers in the same order as the problems. Failure to name and number the printed pages will lead to a penalty of at least two points. Failure to turn in both versions may lead to a much worse penalty.

While your electronic version is due at 10:30 p.m. Tuesday, your physical copy will be submitted in class on Wednesday. It is presumed the physical copy matches the electronic copy. Any discrepancies (other than formatting) will be considered a misrepresentation of your work and referred to the Committee on Academic Standing.

In many problems, we ask you to write code. Unless we specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. You should use examples other than those that may be provided with the exam. Do not include resulting images; we should be able to regenerate those.

Unless we explicitly ask you to document your procedures, you need not write introductory comments.

Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please check your spelling and grammar. Because we should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. We will limit that form of extra credit to five points.

We will give partial credit for partially correct answers. We are best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (8am-10pm), feel free to try to call me (cell phone - 641-990-2947).

I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.

Topics: Documentation, unit testing, writing procedures, numeric values

Expressing numbers in their rational, fractional form often helps us avoid errors due to rounding. Moreover, to keep simple fractions from being expressed with arbitrarily large numbers (for example, 1/2 = 123456789/246913578), we typically like to express them in what is called “reduced” form.

What does it mean for a fraction to be reduced? Simply put, the numerator and denominator should share no factors in common. Put another way, we should not be able to divide the numerator and denominator by the same whole number to get smaller whole numbers.

Conveniently, a mathematical quantity known as the “greatest common divisor” (or gcd, as it is sometimes called) expresses a notion that will help us reduce fractions. The gcd is simply the largest factor shared by two given numbers. Thus, if the fraction's numerator and denominator do not have a gcd of 1, then the fraction could be reduced by dividing both terms by this number. Hence to reduce a fraction, it seems we should divide both the numerator and denominator by the gcd. The results would subsequently have a gcd of one, so we would know the fraction is reduced.

We will put this knowledge to use with a simple set of routines to add two fractions. You might recall that to add fractions, we need to place the numerator over a common denominator. The simplest way to do this is to just multiply the two denominators. In order to make sure we are preserving the fractions' values, multiplying each by one, the numerator of each would also need to be multiplied by the same number; that is, the other fraction's denominator.

More precisely, to add two fractions a/b and c/d, we put the result over the common denominator b*d, and the two numerators become a*d and c*b, respectively. Putting it all together we have the sum a/b + c/d = (a*d + c*b) / (b*d). We could write a pair of routines, (numerator-sum-fraction num1 den1 num2 den2) and (denominator-sum-fraction num1 den1 num2 den2) to calculate these simple results.

> (numerator-sum-fraction 1 8 1 16) ; 1/8+1/16 = (1*16 + 1*8)/(8*16) = 24/128
24
> (denominator-sum-fraction 1 8 1 16)
128
> (numerator-sum-fraction 1 8 -1 16) ; 1/8 - 1/16 = (1*16 + (-1)*8)/(8*16) = 8/128
8
> (denominator-sum-fraction 1 8 -1 16)
128

You may have noticed that these fractions are not reduced. To accomplish that, we could write a procedure (reduction-factor num1 den1 num2 den2) that calculates the (unreduced) numerator and denominator of the fraction sum and finds their greatest common divisor. Luckily, the built-in Scheme function (gcd a b) can do this for you. This algorithm works when we follow the common and decent convention of using only positive denominators.

How would you implement (numerator-sum-fraction-reduced num1 den1 num2 den2) and (denominator-sum-fraction-reduced num1 den1 num2 den2) to calculate the reduced fraction sum? Now that we have broken down the problem, it should be relatively easy: Give the simple numerator divided by the reduction factor. You would do likewise for the denominator.

(define numerator-sum-fraction-reduced
  (lambda (first-numerator first-denominator second-numerator second-denominator)
    ; STUB
    0))