Cs 331: Exam 1

Front 1

For a persistent list, what is the time complexity of inserting something at the end of a list assuming we have a last pointer?

Back 1

O(n) -- The last pointer does not matter, because we still have to copy the list.

Front 2

For a persistent list, what is the time complexity of inserting something at the end of a list?

Back 2

O(n)

Front 3

Suppose we have a list A and wish to create a new list B that is identical, except the first element will be changed. If use a persistent list, what will be the space complexity?

Back 3

O(1) -- We need to create one cell to represent the changed element, but we can share the remaining elements with the original list.

Front 4

For a persistent list, what is the time complexity of deleting something from the beginning of a list?

Back 4

O(1)

Front 5

For a persistent list, what is the time complexity of deleting something from the end of a list, assuming we have a last pointer?

Back 5

O(n) -- The last pointer does not help because we still need to copy the list.

Front 6

For a persistent list, what is the time complexity of deleting something from the end of a list?

Back 6

O(n)

Front 7

Back 7

Front 8

Back 8

Front 9

Back 9

Front 10

Back 10

Front 11

Back 11

Front 12

Back 12

Front 13

Back 13

Front 14

Write a function in Clojure that will take a list and return the sum of all its elements. You may use the defrecord type we did in class, or Clojure's built-in lists.

Back 14

Front 15

Suppose we have a list A and wish to create a new list B that is identical, except the first element will be changed. If we use a mutable list, what will be the space complexity?

Back 15

O(n)--We need to create one cell to represent the changed element, but we also need to copy the original list. Otherwise, changes made to the original list will be visible in our copy.

Front 16

For a mutable list, what is the time complexity of inserting something at the beginning of a list?

Back 16

O(1)

Front 17

For a mutable list, what is the time complexity of inserting something at the end of a list, assuming we have a last pointer?

Back 17

O(1)

Front 18

For a mutable list, what is the time complexity of inserting something at the end of a list?

Back 18

O(n)

Front 19

For a mutable list, what is the time complexity of deleting something from the beginning of a list?

Back 19

O(n)

Front 20

For a mutable list, what is the time complexity of deleting something from the end of a list, assuming we have a last pointer?

Back 20

O(n)--The last pointer does not help because we have to "back it up" one step, and going backwards in a singly-linked list is O(n).

Front 21

For a mutable list, what is the time complexity of deleting something from the end of a list?

Back 21

O(n)

Front 22

Back 22

Front 23

In a doubly-linked list, what is the purpose of a sentinel?

Back 23

A sentinel takes the place of of null pointers, and allows the same code to handle both interior nodes and edge cases. This simplifies code.

Front 24

What is the advantage of doubly-linked lists over singly-linked list?

Back 24

A doubly-linked list allows the program to traverse the list backwards quickly.

Front 25

If you only have persistent data, but want to be able to traverse a list forwards and backwards quickly (like you can in a doubly-linked list), what can you do about it?

Back 25

You can use a list zipper to handle this functionality.

Front 26

Back 26

Front 27

Back 27

Front 28

Back 28

Front 29

Back 29

Front 30

Back 30

Front 31

Back 31

Front 32

Back 32

Front 33

Back 33

Front 34

Back 34

Front 35

Back 35

Front 36

What advantage does tail recursion confer to the programmer?

Back 36

Tail recursion allows the compiler to reuse the stack frame of a function when it makes its recursive call. This transforms the recursive function internally into an efficient loop.

Front 37

Back 37

Front 38

Back 38

Front 39

What are the three stack operations? Give their time complexities.

Back 39

The three operations are push, pop, and top. They all take O(1) time.

Front 40

Explain briefly how to implement a stack using arrays (vectors). How are push and pop implemented?

Back 40

You need a vector for the stack, and an integer for the top of stack pointer. This pointer will point to the first available entry in the stack.

Front 41

Explain briefly how to implement a stack using lists. How are push and pop implemented?

Back 41

You can implement a stack with a list by inserting at the front to implement push and deleting from the front to implement pop.

Front 42

Back 42

Front 43

Back 43

Front 44

Back 44

Front 45

Back 45

Front 46

Back 46

Front 47

Back 47

Front 48

Back 48

Front 49

Back 49

Front 50

Back 50

Front 51

Back 51

Front 52

Back 52

Front 53

Back 53

Front 54

Back 54

Front 55

Back 55

Front 56

Back 56

Front 57

Back 57

Front 58

Back 58

Front 59

Back 59

Front 60

Back 60