ICS -Sheet 11 - Solved

Introduction to Computer Science                                                                                                

Problem 11.1: fork system call                                                                                                               (2+3 = 5 points)
Consider the following C program:

1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <unistd.h>
4

5                                    static void action(int m, int n)

6                                    {

7                                    printf("(%d,%d)\n", m, n);

8                                    if (n > 0) {

9                                    if (fork() == 0) {

10                                   action(m, n-1); 11            exit(0);

12                                     }

13                                     }

14                                     }

15

16                       int main(int argc, char *argv[])

17                       {

18                       for (int i = 1; i < argc; i++) {

19                       int a = atoi(argv[i]); 20           action(a, a);

21                         }

22                            return 0;
23 }

a) Assume the program has been compiled into cnt and that all system calls succeed at runtime. How many child processes are created for the following invocations of the program? Explain how you arrived at your answer

(1) ./cnt
(2) ./cnt 1
(3)    ./cnt 2

(4)    ./cnt 1 2 3

b) Remove the line exit(0) and compile the program again. What is printed to the terminal and How many child processes are created for the following invocations of the program? Explain how you arrived at your answer.

(1) ./cnt                                                                                                                                                                        1

(2) ./cnt                                                                                                                                                                        2

(3) ./cnt 1(4) ./cnt 1 2 3Problem 11.2: stack frames and tail recursion (1+2 = 3 points)                              2

 

As discussed in class, function calls require to allocate a stack frame on the call stack. A simple recursive function with a recursion depth n requires the allocation of n stack frames, i.e., the memory complexity grows linear with the recursion depths. In order to improve performance, compilers of high-level programming languages try to optimize the execution of recursive functions.

If a function does a function call as the last action of the function, then this function call can reuse the current stack frame. A recursive function that has this behaviour is called tail recursive. (See also Tail Recursion Explained - Computerphile on YouTube.)

Below is a definition of the function powLin :: Integer -> Integer -> Integer calculating the function powLin(x,n) = xn.

1         powLin :: Integer -> Integer -> Integer

2         powLin x n

3                              | n == 0            = 1
4                                       | otherwise = x * powLin x (n-1)

a)    The function powLin has a linear time complexity. Define a recursive function powLog, which has a logarithmic time complexity. You can utilize the following law:

 if n is even otherwise

b)    Define a tail recursive function powTail with a logarithmic time complexity.

Below is a template for your solution providing some test cases.

1 module Main (main) where

2

3 import Test.HUnit
4

5         powLin :: Integer -> Integer -> Integer

6         powLin x n

7                                | n == 0 = 1
8                                       | otherwise = x * powLin x (n-1)

9

10         powLog :: Integer -> Integer -> Integer

11         powLog x n = undefined

12

13         powTail :: Integer -> Integer -> Integer

14         powTail x n = undefined

15

16                                                                                         powLinTests = TestList [ map (powLin 0) [0,1,2,3,10] ~?= [1,0,0,0,0]

17                                                                                         , map (powLin 2) [0,1,2,3,10] ~?= [1,2,4,8,1024]

18                                                                                         , map (powLin 5) [0,1,2,3,10] ~?= [1,5,25,125,9765625]

19                                                                                         ]

20

21                                                                                         powLogTests = TestList [ map (powLog 0) [0,1,2,3,10] ~?= [1,0,0,0,0]

22                                                                                         , map (powLog 2) [0,1,2,3,10] ~?= [1,2,4,8,1024]

23                                                                                         , map (powLog 5) [0,1,2,3,10] ~?= [1,5,25,125,9765625]

24                                                                                         ]

25

26                                                                                             powTailTests = TestList [ map (powLog 0) [0,1,2,3,10] ~?= [1,0,0,0,0]

27                                                                                             , map (powLog 2) [0,1,2,3,10] ~?= [1,2,4,8,1024]

28                                                                                             , map (powLog 5) [0,1,2,3,10] ~?= [1,5,25,125,9765625]

29                                                                                             ]

30

31 main = runTestTT $ TestList [powLinTests, powLogTests, powTailTests]

Students who prefer to write imperative code in C can solve this problem using the following C template.

1 #include <assert.h>
2

3                      static int pow_lin(int x, int n)

4                      {

5                      if (n == 0) {

6                                            return 1;
7                      }

8                      return x * pow_lin(x, n-1);

9                      }

10

11         static int pow_log(int x, int n)

12         {

13                             return -1;
14 }

15

16         static int pow_tail(int x, int n)

17         {

18                             return -1;
19 }

20

21         int main(void)

22         {

23         int ns[] = { 0, 1, 2,        3,             10 }; 24       int t0[] = { 1, 0, 0, 0,             0 }; 25          int t2[] = { 1, 2, 4, 8,             1024 };

26                                            int t5[] = { 1, 5, 25, 125, 9765625 };
27

28                                     for (int i = 0; i < sizeof(ns)/sizeof(ns[0]); i++) {

29                                     assert(pow_lin(0, ns[i]) == t0[i]);

30                                     assert(pow_log(0, ns[i]) == t0[i]);

31                                     assert(pow_tail(0, ns[i]) == t0[i]);

32                                     assert(pow_lin(2, ns[i]) == t2[i]);

33                                     assert(pow_log(2, ns[i]) == t2[i]);

34                                     assert(pow_tail(2, ns[i]) == t2[i]);

35                                     assert(pow_lin(5, ns[i]) == t5[i]);

36                                     assert(pow_log(5, ns[i]) == t5[i]);

37                                     assert(pow_tail(5, ns[i]) == t5[i]);

38                                     }

39                                     return 0;

40                                     }

Problem 11.3: type classes (haskell)                                                                                                     (1+1 = 2 points)
The following Haskell module defines types for the two-dimensional shapes Rectangle, Circle, and Triangle.

1 module Main (main) where

2

3 import Test.HUnit
4

5 data Point = Point { x :: Double, y :: Double } deriving (Show)

6

7 -- Rectangles
8

9 data Rectangle = Rectangle { p1 :: Point, p2 :: Point } deriving (Show)

10

11 -- Circles
12

13 data Circle = Circle { m :: Point, r :: Double } deriving (Show)

14

15 -- Triangles
16

17 data Triangle = Triangle { a :: Point, b :: Point, c :: Point } deriving (Show)

18

19 -- Test cases
20

21         pa = Point { x = 0, y = 0 }

22         pb = Point { x = 10, y = 10 }

23         pc = Point { x = 0, y = 20 }

24

25         rect                = Rectangle { p1 = pa, p2 = pb }

26         circle             = Circle  { m = pa, r = 10 }

27         triangle = Triangle { a = pa, b = pb, c = pc }

28

29                                                                    tests = TestList [ area rect ~?= 100.0

30                                                                    , floor (area circle) ~?= 314

31                                                                    , area triangle ~?= 100.0

32                                                                    , area (bbox rect) ~?= 100.0

33                                                                    , area (bbox circle) ~?= 400.0

34                                                                    , area (bbox triangle) ~?= 200.0

35                                                                    ]

36

37 main = runTestTT tests

a)    Define a type class Area declaring a function area, which returns the area covered by a shape type as a Double. The types Rectangle, Circle, and Triangle shall become instances of the Area type class.

b)    Define a type class BoundingBox extending the Area type class and declaring a function bbox, which returns a Rectangle representing the bounding box of a shape. The types Rectangle, Circle, and Triangle shall become instances of the BoundingBox type class.

Your implementation should pass the test cases.