# Assignment 2, due Jan. 26

## Solutions

1. A scavanger hunt question: Search the notes for Jan. 22 and find:

a) What company introduced the first commercial virtual memory system, in what decade? (0.2 points)

Ferranti, in the 1960s (in the context of the Ferranti Atlas computer)

b) What IBM operating system was the first to successfully use virtual memory, in what decade? (0.2 points)

IBM's VM operating system, in the 1970s

c) What was the first variant of Unix to fully support support virtual memory, in what decade? (0.2 points)

BSD Unix, in the 1980s

d) What Microsoft operating system was the first to use virtual memory, in what decade? (0.2 points)

Windows NT in the 1990s

e) What Apple operating system was the first to use virtual memory, in what decade? (0.2 points)

MacOS X also in the 1990s

2. Background: Fibonacci numbers are conventionally defined recursively as:

n ≤ 1: fib(n) = n

n > 1: fib(n) = fib(n – 1) + fib(n – 2)

You could just as easily use this iterative algorithm, expressed in C:

```int fib( int n ) {
int i = 0
int j = 1
while (n > 0) {
int k = i + j;
i = j;
j = k;
n = n - 1;
}
return i;
}
```

A Problem Write a little tcsh script that computes the nth Fibonacci number. It can be done recursively or iteratively, so long as the user interface works something like this:

```[HawkID@servX]\$ fib 3
2
```

Depending on how you configure your path, you may need to type ./fib Turn in legible readable code, handwritten or machine printed are acceptable. Don't overcomment, but at bare minimum, you should identify the algorithm you are using (recursive or iterative) and the name of the file your script is supposed to be stored in. (2 points).

If you come away from the above assignment hating the Unix shell as a programming language, welcome to the club.

Here is a recursive solution; it's really slow, fib 9 took over 17 seconds:

```#!/bin/tcsh
# fib i  -- outputs the i'th Fibonacci number
if (\$1 < 2) then
echo \$1
else
@ iminus1 = \$1 - 1
@ iminus2 = \$1 - 2
@ result = `fib \$iminus1` + `fib \$iminus2`
echo \$result
endif
```

The iterative solution is much faster; it computes fib 9 almost instantly:

```#!/bin/tcsh
# fib i  -- outputs the i'th Fibonacci number
@ count = \$1
@ i = 0
@ j = 1
while (\$count > 0)
@ k = \$i + \$j
@ i = \$j
@ j = \$k
@ count = \$count - 1
end
echo \$i
```