CECS 342 Final Review 2024

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/112

encourage image

There's no tags or description

Looks like no tags are added yet.

113 Terms

1
New cards

The binding of the keyword double to the data type "double" was done at...

Language design time

2
New cards

What does it mean that Haskell is a Pure Functional Programming Language?

The evaluation of expressions has no pure side effects

3
New cards

Which Language features is not a feature of Haskell

Mutable Variables

4
New cards

The average case time complexity to access a random element is

O(1) array and O(n) for lists

5
New cards

The average case time complexity to insert/delete an element is

O(n) for array and O(1) for lists

6
New cards

Which technique can be used to transform a recursive function definition into an equivalent tail recursive function definition?

accumulating parameters

7
New cards

product [ ] = 1

product (x : xs) = x + product xs

pattern matching

8
New cards

max ab = a

max::ord a => a -> a -> a

9
New cards

head (x:xs) = x

head :: [a] -> a

10
New cards

Which Haskell language feature is used where other languages would use NULL pointers?

algebraic data types, in particular sum/co-products

11
New cards

What makes a recursive function definition tail recursive?

it contains exactly one recursive call and its return value is immediately returned by the calling function

12
New cards

foldr(+) 0 [1,2,3]

6

13
New cards

foldl(-) 0[1,2,3]

2

14
New cards

foldr(-) 0[1,2,3]

-6

15
New cards

foldr(+) 5[1,2,3]

11

16
New cards

Consider the Haskell function definition

const x __ = x

Evaluate

Const(1+) 10 100

101

17
New cards

Consider the Haskell function definition

const x_ = x

What is the type const?

const :: a -> b -> c

18
New cards

Consider the Haskell function definition

const x __ = x

Evaluate

foldr (const(1+)) 0[2,1,3]

3

19
New cards

Consider the Haskell function definition

const x __ = x

Evaluate

fold1(const(1+)) 0 [2,1,3]

4

20
New cards

foldr (++) [ ] [ x, y, z]

what is the data type?

[[a]] -> [a]

21
New cards

Consider the Haskell Function definition

(++) [ ] ys = ys

(++) (x:xs) ys = x : (xs++ys)

Evaluate

"c" ++ "++"

"c++"

22
New cards

Consider the Haskell Function definition

(++) [ ] ys = ys

(++) (x:xs) ys = x : (xs++ys)

What is the type of (++) ?

(++) :: [a] -> [a] -> [a]

23
New cards

Consider the Haskell Function definition

(++) [ ] ys = ys

(++) (x:xs) ys = x : (xs++ys)

What does the function foldr (++) [ ] do?

flatten a list of lists

24
New cards

A list [1, 2, 3] in Haskell is syntactic sugar for

1: (2: (3: [ ]))

25
New cards

Consider the following Haskell function definitions:

foldr _ z [ ] = z

folder f z (x :xs) = f x (foldr f z xs)

foldl _ z [ ] = z

foldl f z (x:xs) = foldl f (f z x) xs

Which of these functions are tail recursive?

foldl but not not foldr

26
New cards

Consider the following Haskell function definitions:

foldr _ z [ ] = z

folder f z (x :xs) = f x (foldr f z xs)

foldl _ z [ ] = z

foldl f z (x:xs) = foldl f (f z x) xs

what is the type of foldr?

foldr :: (a -> b -> b) -> b -> [a] -> b

27
New cards

Consider the following Haskell function definitions:

foldr _ z [ ] = z

folder f z (x :xs) = f x (foldr f z xs)

foldl _ z [ ] = z

foldl f z (x:xs) = foldl f (f z x) xs

what is the type of foldl?

foldl :: (b->a->b) -> b -> [a] -> b

28
New cards

Consider the following Haskell data type and function definitions:

data (a,b) = (a,b)

fst (a, _ ) = a

snd ( _ , b) = b

Evaluate the expression

let f pp = snd p - fst p in f(1, 3)

2

29
New cards

Consider the following Haskell data type and function definitions:

data (a,b) = (a,b)

fst (a, _ ) = a

snd ( _ , b) = b

What algebraic data type is (a,b)?

product

30
New cards

Consider the following Haskell data type and function definitions:

data (a,b) = (a,b)

fst (a, _ ) = a

snd ( _ , b) = b

What kind of functions are fst and snd?

projections

31
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

What can Maybe be used for?

optional values

32
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

instance Foldable Maybe

where

foldr _ z Nothing = z

foldr f z (Just x) - f x z

Evaluate the expression sum Nothing

0

33
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

instance Foldable Maybe

where

foldr _ z Nothing = z

foldr f z (Just x) - f x z

Evaluate the expression sum ( Just 2 )

2

34
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

instance Foldable Maybe

where

foldr _ z Nothing = z

foldr f z (Just x) - f x z

Evaluate the expression product Nothing

1

35
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

instance Foldable Maybe

where

foldr _ z Nothing = z

foldr f z (Just x) - f x z

Evaluate the expression product ( Just 2 )

2

36
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

instance Foldable Maybe

where

foldr _ z Nothing = z

foldr f z (Just x) - f x z

Evaluate the expression length ( Just "abc")

1

37
New cards

Consider the following Haskell data type definitions:

data Maybe a = Nothing | Just a

instance Foldable Maybe

where

foldr _ z Nothing = z

foldr f z (Just x) - f x z

Evaluate the expression length nothing

0

38
New cards

Const int x = 5

functional or imperative?

functional

39
New cards

void swap (int *a, int *b) {

int h = *a ;

*a = *b;

*b = h;

functional or imperative?

imperative

40
New cards

int f (int x) {

return 2 *x+1;

}

functional or imperative?

functional

41
New cards

x + x + 5

functional or imperative?

imperative

42
New cards

Which of the following is an example of a sum/co-product type in Haskell?

data shape = Circle Float

| Rectangle Float Float

43
New cards

In Haskell, which keyword is used to define algebraic data types?

data

44
New cards

What is the purpose of deriving clause in Haskell data type declarations?

automatically generates instance definitions for certain type classes

45
New cards

What is a recursive data type?

data type that refers to itself and definition

46
New cards

type def purpose?

?

47
New cards

Static void swap ( int *a , int i, int j ){

int h = a[ i ]

}

a[ i ] = a[ j ]

48
New cards

Record (also called structure of struct)

Product

49
New cards

Enumerated type

sum/co-product

50
New cards

Tuple

Product

51
New cards

Tagged union

sum/co-product

52
New cards

qsort [ ] = [ ]

qsort (x : xs) = sortp xs [ ] [ ]

where

sortp [ ] us vs = qsort us ++ x : qsort vs

sortp (y :ys) us vs = ?

if y < x then sort p ys ( y : us) us

else sort p ys (y : us)

How many times will each element in the input list xs?

2

53
New cards

qgsort [ ] = [ ]

qsort (x : xs) = sortp xs [ ] [ ]

where

sortp [ ] us vs = qsort us ++ x : qsort vs

sortp (y :ys) us vs = ?

if y < x then sort p ys ( y : us) us

else sort p ys (y : us)

how many times will each element in the input list x?

1

54
New cards

qsort [ ] = [ ]

qsort (x : xs) = sortp xs [ ] [ ]

where

sortp [ ] us vs = qsort us ++ x : qsort vs

sortp (y :ys) us vs = ?

if y < x then sort p ys ( y : us) us

else sort p ys (y : us) gsort [ ] = [ ]

Which of the following is true?

sortp is tail recursive but qsort is not

55
New cards

Lecture note Tree

data Tree a = node a (Tree a) (Tree a) | Leaf

countNodes Leaf = 0

(Nodes_left right) = 1 + countNodes left + countNodes right

how many nodes?

3 nodes

56
New cards

?

x : merge xs (y:ys)

57
New cards

int main ( ) {

Node n1 = {1, Null};

Node n2 = {2, &n1};

Node n3 = {3, &n2};

printList (&n3);

return 0;

}

3 2 1

58
New cards

?

countLeaves = 4

59
New cards

Which of the these languages does not have a static type system by default?

Python

60
New cards

What Characterizes a static type system?

The types of values have to be determined at compile time/before runtime

61
New cards

What does the sizeof operator in C return?

The size of a data type in bytes

62
New cards

Runtime stacks enable

All of the above

- Recursion

- Unique Sets of parameters per subroutine activation

- Unique Sets of variables per subroutine activation

63
New cards

In C, we first declare an int* then assign it via malloc, then without explicitly deallocating it, assign it another value from malloc. What did we create?

A memory leak

64
New cards

A generator implemented using the yield keyword in C# or Python behaves similar to which Haskell feature?

Lazy Lists

65
New cards

Generic Functions in c++ are specifically using which keyword?

Templates

66
New cards

What is the main reduction rule of the operational semantic of lamda-calculus?

Beta Reduction

67
New cards

Runtime stacks enable

All of the above

- Recursion

- Unique Sets of parameters per subroutine activation

- Unique Sets of variables per subroutine activation

68
New cards

Consider the following C program:

01 #include

02 #include

03

04 int main() {

05 int *p;

06

07 p = malloc(sizeof(int));

08

09 if (p == 0) {

10 fputs("ERROR: Out of memory\n", stderr);

11 return 1;

12 }

13

14 *p = 42;

15 printf("%d\n", *p);

16

17 free(p);

18

19 return 0;

20 }

In which lines of this program will heap memory be allocated and/or deallocated?

7 and 17

69
New cards

Consider the following C program:

01 #include

02 #include

03

04 int main() {

05 int *p;

06

07 p = malloc(sizeof(int));

08

09 if (p == 0) {

10 fputs("ERROR: Out of memory\n", stderr);

11 return 1;

12 }

13

14 *p = 42;

15 printf("%d\n", *p);

16

17 free(p);

18

19 return 0;

20 }

In which lines of this program are we referring to static memory?

10 and 15

70
New cards

Consider the following C program:

01 #include

02 #include

03

04 int main() {

05 int *p;

06

07 p = malloc(sizeof(int));

08

09 if (p == 0) {

10 fputs("ERROR: Out of memory\n", stderr);

11 return 1;

12 }

13

14 *p = 42;

15 printf("%d\n", *p);

16

17 free(p);

18

19 return 0;

20 }

Is the heap memory really necessary in the above program?

No, since we're only allocation memory for one int, we could have used the stack for that

71
New cards

Consider the following C program:

01 #include

02 #include

03

04 int main() {

05 int *p;

06

07 p = malloc(sizeof(int));

08

09 if (p == 0) {

10 fputs("ERROR: Out of memory\n", stderr);

11 return 1;

12 }

13

14 *p = 42;

15 printf("%d\n", *p);

16

17 free(p);

18

19 return 0;

20 }

How would the program's behavior change if we remove line 17?

The behavior wouldn't change, since the heap memory allocated in line 7 would be freed in line 19 when the process terminates

72
New cards

A list [ 1, 2, 3 ] in Haskell is syntactic sugar for....

1:2:3: [ ]which is equivalent to 1: (2: (3: [ ]))

73
New cards

What is the main advantage of generic programming?

It improves source code re-usability

74
New cards

What is the type of the following polymorphic Haskell function?

head (x:xs) = x

head :: [a] -> a

75
New cards

What is the type of the following polymorphic Haskell function?

tail (x:xs) = xs

tail :: [a] -> [a]

76
New cards

What is the type of the following polymorphic Haskell function?

max a b = if a

maximum :: (Foldable t, Ord a) => t a -> a

77
New cards

Which C#/LINQ keywords are used to implement generators?

select & yield

78
New cards

Which of the following statements about the stack and the heap is incorrect?

The stack is usually larger than the heap

79
New cards

Translate the C# generator Quux into Haskell Function

quux :: [Int] -> [Int]

Using Lazy Lists:

quux xs = 1 : map (3*) xs

80
New cards

How many times will this yield return

var ns = Quux(Quux( new int [ ]{2,5})

7

81
New cards

What is the output of the following code?

var ns = Quux(Quux(new int[ ] {1, 3}));

foreach (var n in ns)

Console.WriteLine(n);

1

3

18

45

82
New cards

Consider the following generator written in C#:

IEnumerable Quux (IEnumerableseg)

{

yield return 1;

foreach (var n in seg yield return 3 * n;

}

Translate the C# generator Quux into Python.

def quux(seq):

yield 1

for n in seq:

yield 3 * n

83
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in normal order i.e. leftmost, outermost redux first:

What is the first step?

(1 + 2) (1 + 2)

84
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in normal order i.e. leftmost, outermost redux first:

What is the second step?

3 * (1 + 2)

85
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in normal order i.e. leftmost, outermost redux first:

What is the third redux?

3 * 3

86
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in normal order i.e. leftmost, outermost redux first:

What is the fourth redux?

9

87
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in applicative order i.e. leftmost, outermost redux first:

What is the first step?

(/x -> x * x) 3

88
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in applicative order i.e. leftmost, outermost redux first:

what is the second step?

3 * 3

89
New cards

Evaluate the Haskell lambda-expression:

(\x -> x * x) (1 + 2)

step-by-step in applicative order i.e. leftmost, outermost redux first:

what is the third step?

9

90
New cards

Match the language typically executed:

C

Compiled to native code

91
New cards

Match the language typically executed:

C++

Compiled to native code

92
New cards

Match the language typically executed:

C#

Compiled (to managed code that is then executed by the .NET runtime)

93
New cards

Match the language typically executed:

Python

Interpreted (after being compiled to byte code)

94
New cards

int a = 5;

int b [1000]

int c (int d) {return a * b[d];}

Match the symbol with the memory segment (where money will be allocated to store its value).

a

static, Data Segment

95
New cards

Match the language typically executed:

Haskell

Compiled to native code or interpreted

96
New cards

int a = 5;

int b [1000]

int c (int d) {return a * b[d];}

Match the symbol with the memory segment (where money will be allocated to store its value).

*b

static, BSS Segment

97
New cards

int a = 5;

int b [1000]

int c (int d) {return a * b[d];}

Match the symbol with the memory segment (where money will be allocated to store its value).

*c

static, text segment

98
New cards

int a = 5;

int b [1000]

int c (int d) {return a * b[d];}

Match the symbol with the memory segment (where money will be allocated to store its value).

d

Automatic(static)

99
New cards

Match the generic programming features to the languages

Polymorphic types and type classes

Haskell

100
New cards

Match the generic programming features to the languages

Mainly void*

C