Tutorial Exercises Week 02

Exercise 1 - Function Pointers

Given the following function prototypes and assignments: 
int  add (int n1, int n2);
link reverse (link ls);
void square (double *x);

 x1 = add;
 x2 = reverse;
 x3 = square;
Give the correct variable declarations for x1, x2, and x3.

Exercise 2 - Stacks

Write a program which, given a string containing round, curly, and square brackets, will print 'success' if the parentheses are correctly balanced, and 'fail' otherwise. 
 
 
> ./check_parens "()"
success
> ./check_parens "([])"
success
> ./check_parens "([]){}"
success
> ./check_parens "([]){"
fail
> ./check_parens "([sdfdf]ss)fdfsd"
success
Hint: the problem is similar to the postfix expression evaluation problem.

Exercise 3 - Testing

What is the difference between black box and white box testing ADTs?

Exercise 4 - Blackbox testing

Imagine you have the following test file defined in a file called testStack.c and it includes the Stack.h interface from Exercise 1: 
#include "Stack.h"

int main(int argc, char * argv[]){
    printf("Testing new stack\n");
    Stack s = createStack();
    assert(s->size == 0);
    printf("Test passed\n");
    return 0;
}
When compiling my test file using 
gcc -Wall -Werror -c testStack.c
I get the following compile error 
testStack.c:12:5: error: dereferencing pointer to incomplete type
What does this mean?

Exercise 4 - Timing

  1. You can obtain overall timing data on the execution of programs on Linux via the bash shell's built-in time command. You use it simply by preceding the command you want to run with the word time, e.g. 

    $ time ./program < aBigInputFile > aBigOutputFile

    The output from the time command looks like: 

    0.22user 0.03system 0:01.90elapsed 13%CPU (0avgtext+0avgdata 17488maxresident)k
0inputs+13488outputs (0major+1760minor)pagefaults 0swaps

    Describe what the first four components on the first line (in green) are and how they are related.

  2. Consider the following shell script to run some timing tests: 

    #!/bin/sh

cat /dev/null > log
for size in 1000 10000 100000 1000000
do
	for order in random sorted reverse
	do
		echo === Testing for $order input, size $size === >> log
		for i in 1 2 3 4 5
		do
			case $order in
			random) flag="R" ;;
			sorted) flag="A" ;;
			reverse) flag="D" ;;
			esac
			{ ./seqq $size $flag | time sort > /dev/null ; } 2>> log
		done
		echo "" >> log
	done
done

    The seqq prints sequences of numbers in the range 1..Max. It takes two command line parameters:

    Answer the following based on your understanding of the script:

    1. How many times will the sort command be invoked?
    2. What sequences of numbers are going to be generated by seqq?
    3. Where does the output from the script go?
    4. What does the line cat /dev/null > log do?
    5. What does the line echo "" >> log do?

Exercise 5 - Algorithmic Complexity

  1. Consider two functions f(n) and g(n) for the same task. The time cost for f(n) is time(f(n)) = 100n, while the time cost for g(n) is time(g(n)) = 2n2.

    1. Which function is faster for n=10?
    2. Which function is faster for n=20?
    3. Which function is faster for n=100?
    4. Which function is faster for n=1000?
    5. What is the crossover point where f() becomes more efficient than g()?

  2. Analyze the behaviour of each of the following functions, and determine their algorithmic complexity.


    a. Nested Loop
    void f3(int n) {
        int i,j;
        for (i=1; i<=n; i++) {
          for (j=1; j<=n; j++) {
           printf("hello");}
          }
        }
    }     b. Linear Search

    // Pre: n > 0 && valid(int[n],a) && valid(int,val)
    // Post: return value = (∃ i ∈ [0..n-1], a[i] == val)
    bool found(int a[], int n, int val) {
         int i;
         for (i = 0; i < n; i++) {
             if (a[i] == val) return 1;
        }
        return 0;