Questions

These questions should be answered in the fileanswers.txt which can be found in thelinux-lab02 directory created at the start of this lab.

1.

Look at the information displayed bytop:

  a)

What is the computer’s current load average?

(1)

  b)

How many processes (top calls them “tasks” here) are there on the system?

(1)

  c)

How would you show only the processes started by your user?  Refer to the manual page if you are unsure.

(1)

(3)

Questions

2.

What effect does an ampersand (&) have when included after a command?

(1)

3.

top andps both display information about running processes.  How does the number of processes listed bytop compare to the number listed byps?  Why do these numbers differ?

(3)

(4)

Questions

4.

What effect does adding a directory to yourPATH variable have?

(1)

5.

Assume you have the following variables set:

A=Apple

B=Ball

C=Cat

What would the output be if you used theecho command to print the following?

  a)

$A

(1)

  b)

$A$B

(1)

  c)

$AB

(1)

  d)

$Cat

(1)

  e)

${C}at

(1)

  f)

"$A $B $C"

(1)

  g)

'$A $B $C'

(1)

  h)

\$A

(1)

(9)

Activity 1: The Newton-Raphson-Seki Method

In Lab 1, we wrote code to improve guesses of the zeros of:

via the iterated process:

where

However, because we didn't know how to write loops, we had to calculate each new guess separately.

Now that we do know about loops in C, we're going to improve the code in several ways, starting by making it keep improving guesses until it gets close to an answer.

Our "stopping condition" here is going to be when one of two things is true:

· the difference between and is small (say, 10−6)

o Hint: this is the same as being small – or its square being small [which has the advantage that the square will always be positive] (You can write a small literal value like1e−6 (for 10−6))

or

· we have tried more than 20 times to improve our guess without getting close. (This is an important additional limit, as otherwise if the method failed somehow, we’d be stuck iterating forever – if we do hit this limit, we will know wedidn't find a root.)

This is best represented with ado … while loop in C, as our main condition is “when this thing is true”.

6.

Make a copy of your code from Activity 2 calledcuberoots.cin the clabdirectory within linux-lab02, and edit it in the following ways:

We no longer needx1 orx2, because inside our loop we're going to update our guess directly. (We do need to store the "delta", which we can use a variable called dxn for.)

Modify your calculations to calculatedxn and then updatex0 with the new value (as if it werex1). You may want to rename "x0" to "xn" here, since we're updating it with a new guess each time…

(1)

7.

Write ado…while loop around the line you just wrote.

You will need to add anint type variable to count the number of iterations you have done – because of the scope of a while loop, you need to declare thisoutside the loop.

The condition for the while loop is for it tocontinue, so you need to test if the magnitude ofdxn is larger than1e-6 and we haven't made more than 20 attempts. Remember, the && operator combines two logical tests with a Boolean AND.

(3)

8.

Test your code to see if it converges to the correct answer for a given value ofw.

It would be more useful if we could ask the user for a value ofw to calculate the cube-root of when the code is run, to save us having to recompile the code each time.

Add code before your loop to prompt the user for a number, and then read in a value to use for w. (You may usefgets +sscanf or justscanf here.)

(3)

9.

Run your code and check it works for different values ofw. Add a comment to the code to evidence this.

(1)

10.

Your code should be commented and laid out appropriately.

(3)

11.

Your code should compile with no errors or warnings.

(1)

Your submission for this exercise is 1 piece of C source code.

(14)

Questions

12.

In the above example using pipes, why is it necessary to sort the data files before using theuniq command?  Read the manual pages foruniq if you are unsure.

(1)

13.

Read the manual pages for thegrep command.

  a)

In a single sentence, summarise what thegrep command does.

(1)

  b)

What command would you use to search for word “Chapter” in the

~/linux-lab02/extras/Bash-Beginners-Guide.txt file?

(1)

14.

What does the following command do?  Explain both the individual stages, and the effect of running it (i.e. what will the end result be)?

sort ~/.bash_history | uniq -c | sort -n | tail > commands.txt

(6)

15.

What is the difference between using> and>> for redirection?  Try redirecting output to a file several times using each.

(2)

16.

How would you count the number of processes usingps andwc?

(2)

(13)

Note: “true” and “false” in C

When we talk about conditional tests in C, things like2 == 1 to express the comparison “2 is equal to 1”, then we usually say that the result is eithertrue orfalse. (In this case, of course, it is false.)

C doesn’t have a true concept of “true” and “false” as special values, however. Instead, it uses the value0 to represent “falseness”, andany other value at all to represent “trueness”.

Built-in conditional tests like the one above will provide the value1 as their “true value”, but literally any other non-zero value will also be considered to mean “true” if you pass it to something that looks for true or false.

For example, the if statement wants a true or false value to choose which statements to execute (it will execute the ones in the “if block” if it gets a true value), so:

if (5) {

puts("Hello!")

}

will printHello! to the terminal, as5 is definitely not a0, and thus is “true”.

The stdbool.h header

To make things a little bit nicer, you can (as of C99 and later) use

#include <stdbool.h>

at the top of your source code. This gives you two special values,true andfalse, which are defined to be1 and0 respectively.  It also gives you a “new” type –bool – which can only hold the values0 (false) or1 (true).

bool my_result = (2 == 6);

Note, again, this doesn’t change any of the above – thetrue thatstdbool.h gives you is still just the integer 1, and any other non-zero number will also be “true” for an if statement.

In particular,

true == 5

is stillfalse (sincetrue is really1 behind the scenes), even though:

if (true)

and

if (5)

have the same result.

(true && 5 is still true though, as&& combines “trueness” not numerical value; and trying toassign the value5 to abool type variable will end up with it being set totrue.)

The two values fromstdbool.h are really provided just to make your code more readable, anddon’t have any other special “true or false” powers.(This changes somewhat in C23, but most people are still using C17 or earlier.)

Activity 2: Newton-Raphson-Seki Fractals

Whilst the Newton-Raphson-Seki method is a good approach to finding roots of equations, it has some quirks.
For example: when has multiple possible solutions the one you converge to depends strongly on what your initial guess is. This method can also behave particularly strangely for some initial guesses, and in some other situations which we won’t cover here – you aren't always guaranteed to find the root closest to your starting guess!

Consider the case of the equation:

By inspection, its roots are at x = -1, 0 and 1.  We might imagine that if we use the Newton-Raphson-Seki method to improve a guess until we find a root, we will always find the root our guess starts closest to, but this is not actually the case.

If we write a loop to try different initial guesses for the root between -2 and 2, and then perform the Newton-Raphson-Seki algorithm for each initial guess, recording which root we find…

…what we actually find is that, whilst most of the time it is true that we find the root closest to the initial guess, for initial guesses in a specific range between -1 and 0 we actually find the root x=1; and for initial guesses in a specific range between 0 and 1, we actually find the root x=-1 – in both cases, the rootfurthest from our initial guess!

If we number the roots 1, 2 and 3 in order (so "x=-1" is "root #1"), and uses 0 for "we didn't converge", then we could print out a line of numbers to represent how the root we find changes as we move our initial guess, x0 from -2 to 2:

111111111111111111111111133332222222222222222222222211113333333333333333333333333

Here, the leftmost number is the root we get with an initial guess of -2, the rightmost number is the root we get with an initial guess of 2, and the values in between are the roots intermediate guesses converge to. You can see the anomalous regions, highlighted in bold, where we briefly converge to the "wrong" root.

In this Activity, we're going to write code to investigate this same problem – starting with:

which has the cube-roots of unity (,  ,) as its three solutions… (this is Activity 1 withw = 1.0).

As two of these roots are complex numbers, we will start with code that just looks for the real root.

Rather than finding the solutions to the equation – which we already know here – we’re interested in seeingwhich solution we find, depending onwhere we start from in the complex plane.

So, we want to test different values of x0(our initial guess) in a systematic way, and print out which root [we’ll number them 1, 2, 3 in order above] we reach. We’ll print 0 if we don’t find a root before we stop iterating.

We want to try regularly-spaced values along the real line:

· we’ll write a for-loop around the existing Newton-Raphson-Seki algorithm we wrote – to change pick different initial guesses

· and use an if-elseif test to determine which root we get (and what we print out).  

17.

Create a new filefor your program calledfractal.c bycopying your code forcuberoots.c to a new file.

Remove the code for user input and simplify the rest of the code (as you no longer needw and can replace it with 1.0).

(1)

18.

Afor loop is most commonly used to repeat the statements inside it for various different values of a “loop variable”. They’re better thando…while orwhile… loops for this, as all of the “loop variable” conditions are written together at the top of thefor loop, making them easy to spot by another human reading the code.

For example with:

for(int i=0; i<10; i++) {

    d += i;

}

it is clear that there is a “loop variable”, i, which changes every time around the loop – we can see that it is initialised to 0, it is incremented each loop, and that we continue looping as long asi is less than 10.

Generally, we tend to use integer type variables as loop variables, mostly because floating-point arithmetic is slower than integer arithmetic, and is inherently inexact (which compounds errors with something like a loop). If you need a “floating-point” value that changes, you’ll often see something like:

for(int i=0; i<10; i++) {

    double myvar = i / 10.0;

  …rest of loop here…

wheremyvar is the actual value we care about, and we derive it from the loop variable directly. (This way, we also know we take exactly 10 samples, that are evenly spaced.)

In our case, we want the "value" we calculate inside the loop to be our initial guess for x – and we want the loop to iterate over many samples within whatever range we want.

(Inside the innermost loop, we want to do our Newton-Raphson-Seki algorithm we already wrote – the do-while loop from the original code – so we can find out which root we get)

  a)

Write the for loop placing it around the algorithm we already have, and adding a line to assign the real part of based on the loop variable.

You should change x0 between −2 and +2, but you may pick how many points you sample in this range.

(for each initial guess, you run the full Newton-Raphson-Seki algorithm until you converge to a guess or fail to converge)

(3)

  b)

Add a suitable if/else test after the NRS step (butinside our for-loop) to test the result of the algorithm, and print out a number indicating the root we found.

In this case, we only expect to:

1) fail to converge (if count is 20), in which case we should print 0

2) find the real root (if xn is > 0), in which case we should print 1

3) (otherwise, print 0 for now, as it's "not a root we expect”)

(2)

19.

Compile and run your code.You should find, if you sample enough points in the range, that points almost always find the real root with for any real number guess except for some ranges of guesses where you fail to converge (most obviously, for guesses close to 0).

This is interesting – but we mentioned before that there arethree solutions to our equation – two of which are complex values.

a)

Modify your code to perform its calculation using "complex double" type for xn and dxn. (You just need to change the type in the declaration).

You can also modify your test for the loop to stop when the magnitude ofdxn is small (asdxn is now complex, you should usecreal(dxn*conj(dxn))to calculate the squared magnitude and compare to the square of our "small" value…), and test ifcreal(xn) is greater than 0 in your if/else test.

At this point, try compiling and running your code again: you should get the same result, effectively. (Even though xn and dxn are now complex doubles, we aren't ever testing values for them which aren't real.)

(2)

b)

Now, we're going to extend the range of values we test – as well as scanning over the real part of our guess, we also need to scan over the imaginary part.

Add a second for-loop around the first for-loop  - this one will pick a different imaginary component for our guess (so, for each imaginary component – or row -  we will check all of the real components (or columns) we could combine with it to make a full complex number). You should also scan this imaginary component of x0 between -2 and 2, so we have a square block of values in the complex plane we sample from.

Alter your assignment to xn's initial guess to add the imaginary component the outer loop generates.

(for example, if the real and imaginary components your two loops make are called "r" and "i", you would write:

xn = r + i*I;

)

(2)

c)

We'll need toextend our if / elseif / else chain to print out 1, 2, 3 (or 0) depending on which root we found for a given. (That is: we need to add two tests to it for the two complex roots we might find, now we're testing complex guesses.)

Specifically: you should check

· if the count is 20 first (because if it is, we didn't converge, and print 0)

· then if the real part of xn is positive (if true, this is the 1st root)

· Then a test to distinguish between the two complex roots (one has positive imaginary component, and one negative imaginary component).

Also remember to print a newline at the end of each row.

(2)

20.

The result of running your code now should be a square block of single digits (1, 2, 3 or 0) representing which root we converge to for each starting point in the complex plane. Each row is a set of guesses with the same imaginary component, each column a set of guesses with the same real component.

This isn’t that readable – so we’re going to add a small amount of additional output to make this in to a “PGM format image” – a text format representing grayscale images with 1 number per pixel to give their brightness.

  a)

Print out a “header line” before everything else, which should read:
“P2 width height 3”
(This is “P2” to indicate this is PGM data, then 2 numbers giving the width and height, then the number 3 indicating what the largest value we will print out is – this will be "white" in our image, whilst "0" will be black.)

For example, if your image was 40 × 40 values, the header would be:
P2 40 40 3

(you should, of course, use the number of values your for loops sample, instead of 40)

Add a single line before the loop which prints out such a header line.

(1)

  b)

Add a space between each of our values. (This helps the PGM reader work out where one number ends and the next starts.)
Modify your print commands for the values to add a space after each one.

(1)

21.

By running your code andusing the Bash redirection operator to put its output into a file, make a file calledfractal.pgm containing an image representing your results.

Check that this file represents an image by using (in a system with XForwarding enabled):

display fractal.pgm

to view it.

You should see something like:

If the image is very small, try increasing the number of points you sample in the twofor loops…

(1)

22.

Your code should be commented and laid out appropriately.

(4)

23.

Your code should compile with no errors or warnings.

(1)

Your submission for this exercise is 1 piece of C source code and 1 PGM file.

(17)