This is an open book take home exam. You must do all your work yourself. If you need to discuss any question, come see me! It is due to be returned at class time on Thursday 9 March 2000. It will count 25% of your total grade. The test contains 250 points, each obviously worth 0.1%.

First, work Question 0 which is good for 10 points. Then select any six of the following ten questions, for 40 points each. If you work more than six questions, the first six I see will be graded. Write your answers in clear complete English; use a word processor if you have one. 10 + (6*40) = 250.

0: (Required Question) 10 pts. The following code fragment in Perl prints something out. What does it print out? Explain why, in detail.The quality of the explanation determines 50% of the credit.

This question is intended to test your ability to hand simulate code and to reliably predict the results. Obviously on a take-home midterm, you can run the code to try it out - but please do that AFTER you've hand-simulated it. There will be no computer available at final exam time.

$s1="this=that&one=two&mystuff=yourstuff&yourstuff=trash";
$s2='s3';
$s3="DoubleQuoted";
$s4 = $s1.'$s2';
$s5 = $s2."$s3";
$FORM{$s4} = 'OboyoBoy';
@breakout = split(/\&/,$s4);
print $FORM{$s5};
print $breakout[2];

Now choose six of the following questions. (Note: working on the other four (later) would be a good way to prepare for the final exam.)

1. PERL BASICS. (a) 10 pts. Write a code fragment in Perl which prints out any elements of an array named @tomic which contain, as a substring, the six-character sequence 'carbon'.

(b) 10 pts. Describe in English the kinds of strings that match the following search string. Provide one example of a string that matches, and another that doesn't.

     /(\'\W{4}\')+([m-z])*/

(d) 20 pts. Write a Perl fragment which goes through a string named $mydata, finds all contiguous integer substrings and replaces them by substrings having that value incremented by 2. For instance, if $mydata="And-a 1 and-a 2 and-a 100!" then the result would be "And-a 2 and-a 3 and-a 101!".

2. PERSISTANT INFORMATION. (a) 20 pts. Joe Blitzpflk wrote Lab 1 for Moshell's CAP4020 class. He borrowed some code from Mary Marvel's cgibin directory, slightly customized it and tried to pass it off as his own. He took out all her comments and rearranged the code so it wouldn't look the same as hers. He set up his inventory.txt file with 20 units in it, and made a backup copy called inv2.txt.

The program behaved properly when he tested it. That is, five successive visits to it, showed inventory of 20, 15, 10, 8 and 0 units as he (playing the role of the customers) gradually purchased merchandise. Joe then copied his backup copy 'inv2.txt' on top of his inventory.txt file to restore the inventory, and shut down for the night. Nobody else messed with Joe's directories and nobody else accessed the web site.

However the next day, Moshell was testing Joe's website and it started out with zero inventory. Instantly he suspected that Joe had copied someone else's code, and a few quick Telnet checks confirmed it. What gave Joe away?

(b) 20 pts. Write a piece of Perl code which picks up a file called masterlist.txt. This list contains the names of some other files. Your script opens each of these files and copies its contents into a single file named combined.txt. The result is one file which contains what all the ones in masterlist used to contain.

3. DYNAMIC HTML. Moshell lectured at some length about the idea of using CGI scripts to generate HTML as needed, rather than just returning a static .html page. Here are some questions about that process.

(a) 5 pts. Should your script write its HTML into a file? Why or why not?

(b) 5 pts. What is an environment variable? Give an example of one and its use with CGI scripting.

(c) 10 pts. What privilege issues would arise if you tried to write a script which created a separate file to store the results of each customer's transaction?

(d) 20 pts. The Master Form technique was explained in class. Now it's your turn to explain it. Make sure that your explanation includes answers to these questions:

- why would someone want to do this?
- what is the role of embedded non-HTML tags?
- what possible advantages would accrue from making these tags into HTML comments?
- what possible advantages would accrue from NOT making them into HTML comments?

4. VISION AND VIDEO.

(a) 10 pts. Assume that a DVD disk holds up to about 6 GB of information. Assume that such a disk can hold a 90 minute movie. Use what you know from my lecture and lecture notes to compute how much information (in bytes) this makes available per frame of NTSC video. Show your work.

(b) 10 pts. Now assume that a computer display is set in the mode which has 1280 x 1024 pixels with 24 bit true color. How much information in bytes is required to specify this image as a still picture, without compression?

(c) 10 pts. If we tried to store a 90 minute movie with 30 frames per second of information at the screen resolution specified in (b), we would need a lot more than 6 gb of space. What compression ratio would be required to fit such a "High definition" movie onto the DVD? Is this ratio achievable with MPEG technology as described in the class or the textbook?

(d) 10 pts. If the images in (b) were palettized with an 8 bit palette, what compression ratio would have been required in (c) to fit the movie on the DVD?

5. DATA COMPRESSION BY WIERD MEANS. Mackeral Snapper proposed the following image compression technique for an 8-bit monochrome image from a specialized radar device ("Mackeral Vision")  that has 64 x 64 pixels: chop the image up into 8 x 8 pixel blocks and transmit the first one as a sequence of 65 bytes called a "code word." The first byte of the code word has the value 1 if the remaining 64 bytes of the word contains a valid block of data. It contains a 0 if the block of data is identical to the last one. In this case we don't even transmit the following 64 bytes, but skip right through to the next code word.

So, three successive identical blocks would be transmitted as

1 (64 byte description of the block ) 0 0

for a total of 67 bytes of message to transmit 3*64=192 pixels of information.

Mackeral calls his technique "MackPack.".

(a:10 pts) Figure out an image which would produce the SHORTEST possible encoded message. Describe the image and  the message.

(b:10 pts) Figure out an image which would produce the LONGEST possible encoded message. Describe the image and the message.

(c:20 pts) Assume that you had the task of transmitting some artificially generated texture maps. These maps look like "snow" with random dots in them. They are usually hand-designed to show various densities and degrees of clumping. The guy who makes them (using Photoshop) usually makes just a small sample and then copies it, wallpaper style, to fill up the Mackeral Vision screen.

Mackeral claims that his MackPack technique is a really good way to transmit these maps, and that it might even beat JPEG. You are the consultant who has been hired to find out if his claims are true. What would you do, and what do you think your conclusion might be?

6. JPEG: (a) 20 pts. In compressing an 8 x 8 pixel image by JPEG, there is a zigzag step in the process of "linearizing" the image (making it suitable for storage in a 1-dimensional array.) In the Schmooviet Union, for reasons of political orthodoxy, they insisted on linearizing the images row by row, instead. The outside world laughed at them, but the Schmooviets demonstrated startlingly high compression ratios, as they transmitted pictures of dissident scientists behind bars in the prison outside Lemongrad.

Why was their technique stupid from a JPEG viewpoint? Why did it work well in their demonstration images? Were the dissidents already so compressed from their starvation diets that they didn't take up many pixels?

(b) 20 pts. In discussing frequency-domain encoding of images, we worked with the 1-dimensional Walsh transform to explain the essential details of the 2 dimensional Discrete Cosine Transform. The basic idea was to break a signal down into its components, sorted by spatial frequency.

OLD QUESTION: Consider this signal S = {1 2 3 4 4 3 2 1}. Construct the Walsh Transform Ws of this signal, which will be an eight byte sequence of numbers. Prove that your transform is correct by re-computing S from Ws. Show your work.

I don't have an 8 x 8 Walsh inverse matrix for you and so I'm simplifying the problem to correspond to the matrix that is in the lecture notes.

REPLACEMENT QUESTION: Consider this signal S = {1 2 2 1}. Construct the Walsh Transform Ws of this signal, which will be a four byte sequence of numbers. Prove that your transform is correct by re-computing S from Ws. Show your work.

7. MPEG: Within an MPEG frame, the Macro Block (MB) is an 8x8 set of pixels. If encoded with RGB 24 bit color, this would require 64*3=192 bytes. However, MPEG-2 achieves compression ratios of up to 100:1. This means that an MB might on the average be represented by only about 2 bytes! This almost seems impossible.

(a) 10 pts. Two kinds of redundency exist in recorded video information. Define both of them, in your own words.

(b) 10 pts. Each MPEG frame belongs to one of three families: I (based on actual data), P (forward-predicted) and B (bidirectionally-predicted) frames. The technique used to calculate each MB for a P-frame is based on having the actual video image V0 that corresponds to the previous I-frame, and Vn that corresponds to the P-frame. Describe in your own words, what information is stored in one MB of a P-frame, and how an MPEG encoding system could calculate that MB from V0 and Vn.

(c) 20 pts. The motion-based compression system of  MPEG does a particularly good job when the principal motion in a frame is a pan (camera rotating on the tripod.) Why is this? What would be stored in a P-frame for an MPEG sequence in which nothing is moving? (i. e. a "still scene")? What would be stored in an I-frame for this sequence?

8. 3D GEOMETRY. (a) 20 pts. Construct a 3 x 3 homogenous matrix which rotates data points 45 degrees counterclockwise about the origin, in two dimensions.

(b) 20 pts. Draw the picture represented by the following list of points and commands. Then apply the following homogenous matrix to this list of points. Write down the new points, and draw the picture they represent. Then tell me what transformation (that is, what movement and change in two dimensional space) the matrix produces.
 
 

Command    X    Y Moveto    0    0 Drawto    1    1 Drawto    1    0 Drawto    3    0 Moveto    1    0 Drawto    1    -1 Drawto    0     0

The matrix:      0    .5    2 M =-.5    0    0     0     0    1

 9. DISTRIBUTED INTERACTIVE SIMULATION (DIS). There are twelve degrees of freedom in the state of a moving rigid object - six for position/orientation, and six for momentum. Since linear momentum = mass* velocity and mass isn't usually changing much, we usually store the velocity vector (and angular velocity values, for rotation).

We are constructing a multi-player distributed computer game for Argentine children. The hero of the pampas (that's Argentine for "prairies") is a gaucho,  which is a cowboy. For obscure reasons these Argentine cowboys don't use lassos. Instead they have a thing with two weighted balls tied together with a rope, called a bolo (no surprise, that's almost bola, Spanish for 'ball'.) They throw these things to tangle up the feet of a calf, so they can catch and brand it. Sizzle, sizzle..... (it's a tough world for calves.)

In the game, you can choose to be a gaucho or a calf. If gauchos are hostile to one another, they can throw their bolos and tangle up the horse's feet. This makes the other gaucho mad and he pounds you on the head with his game console. So normally, we pick on the calves. If you are playing a calf, you win by not getting tanglefooted. Everybody in Argentina has a two-joystick control system, for some reason. The left joystick controls the way you run (North East South West or perhaps Norte etc.) and the right one controls the bolo.

Our cowboy is pretty much simplified in this video game. In fact he and his horse together are modeled as a rigid statue, and his bola is modeled by a transparent disk (with the bola painted on a transparent texture map, of course.)

(a: 20 pts.) You are the architect of this game. You want it to have good action, and you know that Argentine telephone lines can only transmit 9600 baud.  Normally we would expect about 4 gauchos and 4 calves to be in a play session. Would you recommend using the DIS protocol concept, with dead reckoning? Explain your reasons and your alternative if you don't use DIS.  Try to be quantitative about your arguments if possible.

(b: 20 pts.) Over in Uruguay they have cable modems which can transmit at 1.5 megabaud. Would you sell the same system to them or a different one? Why?

10. ATM TECHNOLOGY. (a) 10 pts. Without considering cost, would there be any technical barriers for using ATM to play the role that Ethernet played, in implementing the DIS simulation protocol? (Read Wu, and think carefully.) Why, or why not?

(b) 10 pts. ATM is based on the idea of establishing a "Virtual Connection" (VC) from source to destination. Let's assume that we want to transmit a telephone conversation through a network which incorporates ATM switches. The VC passes through some switch which we'll call Switch 473, entering port 7 and exiting port 5. Switch 473 is not an edge switch; it's in the middle of the network somewhere.

Are ports in-7 and out-5 available for any other purposes during my phone call, or must the ATM switch wait until I hang up, before reusing these ports?

(c) 10 pts. "ATM is viable for multimedia communication because it provides a guaranteed QoS." says Wu on page 177. Define QoS (don't just write down the phrase it stands for, but explain the concepts in your own words, with examples NOT drawn from the textbook!)

(d) 10 pts. Explain how ATM's technology differs from that of Ethernet, and why this difference provides the capability of delivering the QoS required for (for instance) real-time video transmission. What might when you try to transmit realtime video through a shared Ethernet connection?