DSFinal

Question 1

What are the four rules for red-black trees?

Answer 1

1. each node is assigned a value of red or black
2. each child of a red node must be black
3. each node mas at most two children, making this a binary tree
4. the path to each leaf must contain the same number of black nodes.

Question 2

What is the difference between a stack and a queue?

Answer 2

A stack allows O(1) time to access, insert, or delete at the end of the container(the last thing you entered), while a queue allows O(1) time to access insert or delete at the front of the container(the first thing you entered).

Question 3

Why do we separate the class definition and declarations into multiple files? How is this useful?

Answer 3

You put the declaration in an h file. You then use the scope resolution operator to define the class methods in a cpp file that #includes the h file. This is useful as you can use these classes in multiple projects by simply including the h file. This allows for more reusability and easier distribution.

Question 4

What are the big three functions and why are the necessary?

Answer 4

I kind of thought there were six Constructor, Deconstructor, Copy Constructor, Move constructor, Copy Assignment operator, and Move Assignment operator.
They are important as it tells the computer how you're class will be built without having to waste large amounts of space that comes from normally copying objects. Normally the computer would make a temporary copy of the object when copying or moving so by defining your own copy and move you can avoid this.

Question 5

Define the run-time stack and run-time heap. Note the differences between the two.

Answer 5

The stack is a stack of data in ram that is provided to your program when it is run. it reads from the end and is a set length. It is where most of your varaibles are held including objects of a structs. The heap is where further information your program will need is held, it is located in ram where nothing has been allocated yet. it is where any variables created art run time is stored and where objects of a class are stored.

Question 6

Define inheritance and explain how it works.

Answer 6

Inheritance is a feature that allows one class to contain all the features of anouther. First you create a base class, then you can create a derived class which inherits from that base class that will have access to all public and protected data members and methods. If you create an object from the derived class it will contain an object of the base class allong with all the aditional fuctionality you added to the derived.

Question 7

What is a function template and how is it useful?

Answer 7

A function template is a blueprint for a function (not a function itself. No function is actually created when it is compiled, not until it is called with a specific data type). It allows you to create several similar functions that deals with different data types.

Question 8

What is an abstract data type and how is it different from a regular data type?

Answer 8

abstract data types are used in base classes that are never suposed to be used to create objects only to be used to have classes derived form them.

Question 9

What are the four types of rotations for AVL trees?

Answer 9

single left
single right
double left right
double right left

Question 10

Order the following functions by growth rate: N, N−−√, N1.5, N2, N log N, N log log N, N log2 N, N log(N2), 2/N, 2N, 2N/2, 37, N2 log N, N3. Indicate which functions grow at the same rate.

Answer 10

2/N, 37, , N, N log log N, N log N, N log(N2), N log2 N, N1.5, N2, N2 log N, N3, 2N/2, 2N.
N log N and N log (N2) grow at the same rate.

Question 11

An alternative to the deletion strategy we have given is to use lazy deletion. To delete an element, we merely mark it deleted (using an extra bit field). The number of deleted and nondeleted elements in the list is kept as part of the data structure. If there are as many deleted elements as nondeleted elements, we traverse the entire list, performing the standard deletion algorithm on all marked nodes.
a. List the advantages and disadvantages of lazy deletion.

Answer 11

The advantages are that it is simpler to code, and there is a possible saving if deleted keys are
subsequently reinserted (in the same place). The disadvantage is that it uses more space, because
each cell needs an extra bit (which is typically a byte), and unused cells are not freed.

Question 12

Suppose that a singly linked list is implemented with both a header and a tail node. Describe constant-time algorithms to

a. insert item x before position p (given by an iterator)
b. remove the item stored at position p (given by an iterator)

Answer 12

(a) Add a copy of the node in position p after position p; then change the value stored in position
p to x.

(b) Set p->data = p->next->data and set p->next = p->next->next. Then delete p->next. Note that the
tail node guarantees that there is always a next node.

Question 13

a. Give a precise expression for the minimum number of nodes in an AVL tree of height h.
b. What is the minimum number of nodes in an AVL tree of height 15?

Answer 13

(a) N(0) = 1, N(1) = 2, N(h) = N(h  1) + N(h  2) + 1.

(b) The heights are one less than the Fibonacci numbers.

Question 14

Since a binary search tree with N nodes has N + 1 nullptr pointers, half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a nullptr left child, we make its left child link to its inorder predecessor, and if a node has a nullptr right child, we make its right child link to its inorder successor. This is known as a threaded tree and the extra links are calledthreads.

a. How can we distinguish threads from real children pointers?
b. What is the advantage of using threaded trees?

Answer 14

(a) You need an extra bit for each thread.
(c) You can do tree traversals somewhat easier and without recursion. The disadvantage is that it
reeks of old-style hacking.

Question 15

Can both insert and findMin be implemented in constant time?

Answer 15

Yes. When an element is inserted, we compare it to the current minimum and change the minimum if the new element is smaller. deleteMin operations are expensive in this scheme.

Question 16

A large number of deletions in a separate chaining hash table can cause the table to be fairly empty, which wastes space. In this case, we can rehash to a table half as large. Assume that we rehash to a larger table when there are twice as many elements as the table size. How empty should the table be before we rehash to a smaller table?

Answer 16

We must be careful not to rehash too often. Let p be the threshold (fraction of table size) at which we rehash to a smaller table. Then if the new table has size N, it contains 2pN elements. This table will require rehashing after either 2N  2pN insertions or pN deletions. Balancing these costs suggests that a good choice is p = 2/3. For instance, suppose we have a table of size 300. If we rehash at 200 elements, then the new table size is N = 150, and we can do either 100 insertions or 100 deletions until a new rehash is required.
If we know that insertions are more frequent than deletions, then we might choose p to be somewhat larger. If p is too close to 1.0, however, then a sequence of a small number of deletions followed by insertions can cause frequent rehashing. In the worst case, if p = 1.0, then alternating deletions and insertions both require rehashing.

Question 17

What are the advantages and disadvantages of the various collision resolution strategies?

Answer 17

Separate chaining hashing requires the use of links, which costs some memory, and the standard
method of implementing calls on memory allocation routines, which typically are expensive. Linear
probing is easily implemented, but performance degrades severely as the load factor increases because
of primary clustering. Quadratic probing is only slightly more difficult to implement and gives
good performance in practice. An insertion can fail if the table is half empty, but this is not likely.
Even if it were, such an insertion would be so expensive that it wouldn’t matter and would almost
certainly point up a weakness in the hash function. Double hashing eliminates primary and secondary
clustering, but the computation of a second hash function can be costly

Question 18

Describe a procedure that avoids initializing a hash table (at the expense of memory).

Answer 18

To each hash table slot, we can add an extra data member that we’ll call whereOnStack, and we can
keep an extra stack. When an insertion is first performed into a slot, we push the address (or number)
of the slot onto the stack and set the whereOnStack data member to refer to the top of the stack. When
we access a hash table slot, we check that whereOnStack refers to a valid part of the stack and that
the entry in the (middle of the) stack that is referred to by the whereOnStack data member has that
hash table slot as an address.

Question 19

A nonstandard C++ extension adds syntax that allows a switch statement to work with the string type (instead of the primitive integer types). Explain how hash tables can be used by the compiler to implement this language addition.

Answer 19

The compiler could hash each string in the switch statement to a table which holds the starting memory location for the code to be executed for the appropriate string.

Question 20

Show that if the symbols are sorted by frequency, Huffman’s algorithm can be implemented in linear time.

Answer 20

Maintain two queues, Q1 and Q2. Q1 will store single-node trees in sorted order, and Q2 will store multinode trees in sorted order. Place the initial single-node trees on Q1, enqueueing the smallest weight tree first. Initially, Q2 is empty. Examine the first two entries of each of Q1 and Q2, and dequeue the two smallest. (This requires an easily implemented extension to the ADT.) Merge the tree and place the result at the end of Q2. Continue this step until Q1 is empty and only one tree is left in Q2.

Question 21

Why is it important that Strassen’s algorithm does not use commutativity in the multiplication of 2 × 2 matrices?

Answer 21

Matrix multiplication is not commutative, so the algorithm couldn’t be used recursively on matrices if commutativity was used.

Question 22

Show the optimal binary search tree for the following words, where the frequency of occurrence is in parentheses: a (0.18), and (0.19),I (0.23), it (0.21), or (0.19).

Answer 22

The optimal binary search tree is the same one that would be obtained by a greedy strategy: I is at the root and has children and and it; a and or are leaves; the total cost is 2.14.