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.
Solution: int (*x1) (int, int); link (*x2) (link); void (*x3) (double *);
> ./check_parens "()"
success
> ./check_parens "([])"
success
> ./check_parens "([]){}"
success
> ./check_parens "([]){"
fail
> ./check_parens "([sdfdf]ss)fdfsd"
success
Solution
Item safePop (Stack s) {
if (stackSize(s) == 0) {
printf ("syntax error in postfix expression\n");
abort ();
} else {
return (pop(s));
}
}
char closing (char c) {
if (c == '(') {
return ')';
} else if (c == '[') {
return ']';
} else if (c == '{') {
return '}';
} else return '\0';
}
int main (int argc, char *argv[]) {
Stack s;
char *a;
int i;
if (argc < 2) {
printf ("No argument string provided\n");
return 0;
}
a = argv[1];
s = createStack();
for (i = 0; a[i] != '\0'; i++) {
if ((a[i] == '(') ||
(a[i] == '{') ||
(a[i] == '[')) {
push(s,a[i]);
} else if ((a[i] == ')') ||
(a[i] == '}') ||
(a[i] == ']')) {
if (closing (safePop (s)) != a[i]) {
printf ("fail\n");
return (0);
}
}
}
if (stackSize (s) == 0) {
printf ("success\n");
} else {
printf ("fail\n");
}
return (0);
}
What is the difference between black box and white box testing ADTs?
Solution Black box testing tests the functionality of the code. It focuses on the input and output of the functions defined in the interface. It does not rely on the underlying implementation. It can't access the underlying implementation. Our black box tests should still work even if we change the underlying implementation. White bo testing te sts the structure of the code. It relies on knowing, accessing and testing the internal state of the code. If we changed our implementation we would need to write new white box tests.
#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.cI get the following compile error
testStack.c:12:5: error: dereferencing pointer to incomplete typeWhat does this mean?
Solution
It this case we are getting the error as we are trying to use the internal structure of the ADT by saying s->size. We have no access to the underlying implementation of the stack, we we can only access the ADT by the functions and typedefs provided in the interface (.h file).
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.
Solution
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:
Solution
- The sort command is invoked once during each iteration of the innermost loop body. The outermost loop executes 4 times (for 1000..1000000). For each of its executions, the for order loop will be executed 3 times (for random, sorted, reverse). For each of the for order loop's iterations, the for i loop is executed 5 times. Total number of executions of innermost loop body =
4*3*5 = 60. So sort is executed 60 times.- The first 1000 positive integers in ascending, descending and random order.
The first 10000 positive integers in ascending, descending and random order.
The first 100000 positive integers in ascending, descending and random order.
The first 1000000 positive integers in ascending, descending and random order.- All of the output from the script goes to a file called log.
- The line
cat /dev/null > log creates an initially empty file. Reading from /dev/null always gives empty input.- The line
echo "" >> log appends an empty line to the log file, after each set of 5 runs for a given size and order combination.
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.
- For n=10, time(f(n)) = 1000, time(g(n)) = 200
- For n=20, time(f(n)) = 2000, time(g(n)) = 800
- For n=100, time(f(n)) = 10,000, time(g(n)) = 20,000
- For n=1000, time(f(n)) = 100,000, time(g(n)) = 2,000,000
- Crossover occurs when time(f(n)) = time(g(n)), i.e. when 100n = 2n2 With a little bit of simple algebraic manipulation n = 50 is the crossover point.
Analyze the behaviour of each of the following functions, and determine their algorithmic complexity.
- Nested Loop The outer loop executes n times. The inner loop executes n times. The total number of steps is n^2. Therefore, time-complexity of the algorithm is O(n^2) or quadratic. If there is a third nested loop that executes n times, then time-complexity is O(n^3).
- Linear search The function scans the array from start to finish and examines all n elements. Each element is compared against the value being searched for val. If val is found, the function immediately returns a true result and the rest of the array is ignored. The analysis is more complicated, because the performance can be different for different arrays and search values.
The most interesting case is the worst case, since it gives us an upper bound on the performance. We would normally quote the algorithmic complexity as the complexity of the worst case; in this case O(n).
- Best case: val occurs as the first element in the array. In this case only one comparison occurs.
- Worst case: val is not in the array, or only occurs as the last element. In this case there are n comparisons.
- Average case: val occurs somewhere in the middle of the array. If each value is equally likely to be searched for, then, on average, there will be n/2 comparisons.