Cs 331 Exam 2

Front 1

Difference between sequence and list?

Back 1

Sequence is an abstraction of a list. It is not bound to a particular representation. It provides a first, rest, and a way to check if sequence is empty.

Anything that can tell you first and rest.

Front 2

Difference between list and sequence?

Back 2

List is a concrete representation of a sequence of elements. Each node of the list has a data and a next pointer. A sequence is anything that can tell you what is the first and rest.

Front 3

What happens if you call next or rest on a vector?

Back 3

You get a sequence of all but the first.

Front 4

Why does clojure convert concrete representations to sequences?

Back 4

To make built in clojure functions more flexible. Count and map can be called on anything that can be converted to a sequence. That way you don't have to worry about representations.

Front 5

What does (rest [1 2 3 4]) return?

Back 5

Sequence (2 3 4)

Front 6

Difference between sequence and iterator?

Back 6

Both are abstractions and model data having a first and rest.

Iterator is usually an object and is modifies by a next call.

Sequence is an immutable representation and a next will return a new sequence instead of modifying the original.

Front 7

Tree traversal: pre-order. Can you reconstruct?

Back 7

* + c d - f g
Can reconstruct if can distinguish leaves from nodes.

Front 8

Tree traversal: inorder. Can you reconstruct?

Back 8

c + d * f - g
Cannot reconstruct without parenthesis

Front 9

Tree traversal: postorder. Can you reconstruct?

Back 9

c d + f g - *
Can reconstruct if can distinguish leaves from nodes.

Front 10

Pre-order, postorder, inorder, and breath first for following:

Back 10

Front 11

Advantage and disadvantage of depth first search.

Back 11

* takes little memory
* will not work for infinite trees or backdoor

Front 12

Advantage and disadvantage of breadth first search

Back 12

*BFS will always return closest match to root
*will not be messed up by infinity
*takes up more memory

Front 13

If given pre-order traversal of a tree, what do we need to know to generate the tree?

Back 13

Which nodes are leaves and how many children branches we have.

Front 14

Inorder cannot generally be used to reconstruct a tree. Why?

Back 14

Depth information is destroyed. Don't know which parts will be parenthesized.

Front 15

Pre-order, inorder, postorder and breadth first

Back 15

Front 16

Back 16

Front 17

What is the principle of locality?

Back 17

If something is accessed, it will be accessed again in the near future or something close to it will be accessed in the near future.

Front 18

What is temporal locality?

Back 18

If something is accessed, it will likely be accessed in the near future.
Take advantage of it by copying it into a cache or moving it to a part of a data structure that has a faster access time.

Front 19

What is spatial locality?

Back 19

When something is accessed, things near it will likely be accessed in the future.
Take advantage by when something is accessed, make things near it be more easy to access.

Front 20

What is the move to front heuristic for ordering a list?

Back 20

When an element is accessed, it should immediately be relocated to the head of the list.

Front 21

What is the swap heuristic for ordering a list?

Back 21

Whenever an element is accessed, things to is moved one element closer to the front.

Front 22

Back 22

Front 23

Back 23

Front 24

Back 24

Front 25

Name tow algorithms that can provide useful data if interrupted

Back 25

Selection sort, heap sort, bubble sort

Front 26

Algorithms that work well if data given to them is already sorted.

Back 26

Insertion sort, bubble sort

Front 27

8 6 9 13 4 5 2
What will be the first 3 elements if you run selection sort on this array? Insertion sort?

Back 27

2 4 5 for selection
8 6 9 for insertion

Front 28

4 1 9 3 8 7 5
First 3 elements picked for insertion? Selection?

Back 28

4 1 9
1 3 4

Front 29

Special ability of selection sort?

Back 29

Can be interrupted before completion and still have a partially sorted array

Front 30

Special ability of insertion sort?

Back 30

Runs o(n) if data is already sorted.

Linear if data is sorted.

Front 31

Special ability of bubble sort

Back 31

Runs linear if data is sorted.

Front 32

Average time complexity of selection sort?

Back 32

O(n^2)

Front 33

Average time complexity of insertion sort?

Back 33

O(n^2)

Front 34

Average time complexity of insertion sort?

Back 34

O(n^2)

Front 35

6 1 9 11 7 3 4
First 3 selection sort and insertion sort

Back 35

1 3 4
6 1 9

Front 36

How does selection sort work? Specialty?

Back 36

Pick smallest in whole array, put in place. Pick second smallest in whole array, put in place. That's why it's special is it keeps data sorted even if interrupted.

Front 37

Insertion sort: how does it work? Special?

Back 37

From First element, find smallest, put in place. From first 2 elements, find smallest and put in place. Repeat. Special is it runs linear if data is sorted.

Front 38

Quicksort

Back 38

Low pointer looks for higher than pivot
High pointer looks for lower than pivot

Front 39

Which algorithm suffers in performance if the data is already sorted? How to fix?

Back 39

Quicksort. Fix with random pivot.

Front 40

Quicksort
53 42 69 31 77 33 94

Back 40

31 42 33 53 77 69 94

Front 41

Quicksort
4 2 7 9 5 1 3

Back 41

1 2 3 4 5 9 7

Front 42

Normal time complexity of quicksort?

Back 42

O(n logn)

Front 43

How to avoid worst case of quicksort?

Back 43

Random pointer

Front 44

Why does merge sort need extra space when sorting arrays? What happens if not provided?

Back 44

Without extra space, merge sort will be forced to use to shift elements, which will make it n^2

Front 45

Quicksort
23 32 29 41 17 33 24

Back 45

17 23 29 41 32 33 24
Pivot was bad

Front 46

expected time complexity inserting into hash table?

Back 46

O(1)

Front 47

Worst case time complexity for inserting into Hash?

Back 47

O(n)

Front 48

Hash causes collision. What happens if separate chaining?

Back 48

each slot becomes a linked list. Collisions go int he linked list.

Front 49

Hash causes collision. What happens if linear probing?

Back 49

algorithm adds one to the slot number until an empty slot is found.

Front 50

Hash causes collision. What happens if quadratic probing?

Back 50

adds squares to slot number

Front 51

Hash causes collision. What happens if double hashing?

Back 51

use separate hash and add multiples of offset

Front 52

Hash tables: what is primary clustering? what probing causes it?

Back 52

linear probing when collisions happen. Future insertions are likely to cause cluster to grow.

Front 53

Hash tables: secondary clustering? what causes it?

Back 53

quadratic sorting. Algorithm adds successive squares, and probing will have to revisit previous collisions

Front 54

linear probing:

x h(x)

a 2

b 4

c 0

d 2

e 2

f 3

Back 54

0 c

1

2 a

3 d

4 b

5 e

6 f

Front 55

quadric probing

x h(x)

a 2

b 4

c 0

d 2

e 2

f 3

Back 55

0 c

1

2 a

3 d

4 b

5 f

6 e

Front 56

double hashing

x h(x)

a 2

b 4

c 0

d 2

e 2

f 3

Back 56

0 c

1 e

2 a

3 f

4 b

5 d

6

Front 57

linear probing:

x h(x)

a 3

b 4

c 1

d 3

e 3

f 2

Back 57

0

1 c

2 f

3 a

4 b

5 d

6 e

Front 58

if deleting from hash table, we need to annotate position. Why?

Back 58

removing may cause gap in probing sequence, which would cause a failure in searching.

Front 59

what happens when deleting 2 elements from heap?

2 3 5 8 12 10

Back 59

5 8 12 10

Front 60

add element to heap

2 3 5 7 11 13

Back 60

1 3 2 7 11 13 5

Front 61

Heap operations and time complexities?

Back 61

add, delete O(log n)

first O(1)

Front 62

add 1 to heap

2 3 5 8 12 10

Back 62

1 3 2 8 12 10 5

Front 63

add 4 to heap

2 3 5 8 12 10

Back 63

2 3 4 8 12 10 5

Front 64

what is the differenc ebetween heap and priority queue?

Back 64

heap is an implementation of PQ

Front 65

what is an up tree?

Back 65

collection of nodes. Each node has a pointer set to its reprsentative. Uptrees support find and union, and both of these are very fast

Front 66

how does up tree compression algorithm work?

Back 66

whenever find is called, upon reterning it sets the current pointer to point to the result of the find returns

Front 67

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 67

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

Front 68

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

Back 68

O(n)

Front 69

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 69

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 70

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

Back 70

O(1)

Front 71

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 71

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

Front 72

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

Back 72

O(n)

Front 73

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/78/28/6887828_m.png

Back 73

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/78/46/6887846_m.png

Front 74

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/78/52/6887852_m.png

Back 74

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/78/58/6887858_m.png

Front 75

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/81/37/6888137_m.png

Back 75

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/81/43/6888143_m.png

Front 76

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/81/61/6888161_m.png

Back 76

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/81/64/6888164_m.png

Front 77

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/81/88/6888188_m.png

Back 77

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/81/94/6888194_m.png

Front 78

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/82/06/6888206_m.png

Back 78

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/82/12/6888212_m.png

Front 79

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/82/24/6888224_m.png

Back 79

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/82/27/6888227_m.png

Front 80

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 80

//fce-study.netdna-ssl.com/2/images/upload-flashcards/88/83/02/6888302_m.png

Front 81

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 81

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 82

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

Back 82

O(1)

Front 83

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 83

O(1)

Front 84

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

Back 84

O(n)

Front 85

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

Back 85

O(n)

Front 86

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 86

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 87

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

Back 87

O(n)

Front 88

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

Back 88

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 89

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

Back 89

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

Front 90

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 90

You can use a list zipper to handle this functionality.

Front 91

What advantage does tail recursion confer to the programmer?

Back 91

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 92

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

Back 92

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 93

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

Back 93

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 94

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 94

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

Front 95

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

Back 95

O(n)

Front 96

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 96

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 97

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

Back 97

O(1)

Front 98

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 98

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

Front 99

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

Back 99

O(n)

Front 100

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 100

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 101

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

Back 101

O(1)

Front 102

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 102

O(1)

Front 103

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

Back 103

O(n)

Front 104

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

Back 104

O(n)

Front 105

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 105

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 106

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

Back 106

O(n)

Front 107

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

Back 107

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 108

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

Back 108

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

Front 109

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 109

You can use a list zipper to handle this functionality.

Front 110

What advantage does tail recursion confer to the programmer?

Back 110

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 111

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

Back 111

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

Front 112

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

Back 112

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 113

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

Back 113

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