Course topics 8 and 9¶

Self-study¶

The topics for this week are (i) Graphs and Trees, (ii) Tree data structures and traversals and (iii) Invalidation in containers

The following links will take you to the video-lectures and the accompanying slides:

Graphs and Trees¶

Graphs and Trees: part 1.

Graphs and Trees: part 2.

Graphs and Trees: part 3.

slides for Graphs and Trees

Tree data structures and traversals¶

Tree data structures and traversals part 1.

Tree data structures and traversals: part 2.

slides for Tree data structures and traversals

Invalidation in containers¶

Invalidation in containers

slides for Invalidation

Trees¶

Question 1

With regard to a general rooted tree, which of the following are true? (Note: more than 1 statement may be true.)

A node can have at most 2 parents.

A node with no children is called a leaf.

A node with no parent is called a root.

If a node has more than 1 child, then none of the children can be leaves.

A node, whose parent has no other children, is called a lonesome node.

Question 2

Suppose we are considering the subtrees of node \(x\) in some rooted tree. Which of the following is true?

Each of the subtrees of \(x\) has \(x\) as its root.

The number of subtrees of \(x\) is one more than the number of children of \(x\).

The parent of \(x\) does not belong to any of the subtrees of \(x\).

Each child of \(x\) belongs to exactly two subtrees of \(x\).

Question 3

Suppose we are considering a rooted tree whose height is 4. Which of the following statements is always true?

The root has at least 4 children.

The tree has at most 4 leaves.

Starting from the root, we need to use at least 5 edges to get to the leaf that is farthest from the root.

The tree has at least 5 nodes.

Question 4

Let \(x\) be a node in a rooted tree. A descendant of node \(x\) is any node in any subtree of \(x\). Which of the following statements is always true?

A child of \(x\) has fewer descendants than \(x\).

The number of descendants of the root is the same as the number of nodes in the tree.

Each leaf is a descendant of all non-leaf nodes in the tree.

No two non-leaf nodes can have the same number of descendants.

Tree data structures and traversals¶

Question 1

Assume a node in a binary tree is stored using children pointers left_child and right_child. If the entire binary tree has 4 nodes, how many of these children pointers will be equal to nullptr?

it is impossible to know how many

Question 2

Which of the following best describes the difference between how a node is stored in a general rooted tree and how a node is stored in binary tree?

With regard to a pointer to node’s parent, in a binary tree we never need such a pointer, whereas in a general tree we sometimes need such a pointer.

With regard to pointers to a node’s children, in a binary tree we have two separate pointers, whereas in a general tree we need some container (e.g. a vector) to store these pointers.

With regards to a node’s key or identification number, in a binary tree such a key must be divisible by 2, whereas for a general tree it can be any positive integer.

With regards to the root node, in a binary tree the root must have exactly 2 children, whereas in a general tree the root can even have a negative number of children.

Question 3

Suppose we perform preorder and postorder traversals on an entire rooted tree having at least two nodes. Which of the following is true?

The numbers of nodes visited by the two different traversals are not equal.

The order in which the nodes are visited in the two traversals is different.

The first node visited in each traversal is a leaf.

Neither traversal needs to know what are the children of any node.

Question 4

Three tree traversals were presented, preorder, postorder and inorder. In what way does inorder differed from the other two traversals?

Only trees with no leaves can be traversed with inorder traversal. The other two can be used to traverse any tree.

A binary tree can only be traversed with inorder traversal. A binary tree cannot be traversed using either postorder or preorder.

An inorder traversal can only be done on trees having the following property: each node has exactly two children.

An inorder traversal can only be done on a binary tree. Preorder and postorder traversals can be done any tree.

Invalidation¶

Question 1

With regard to invalidation and different STL containers, which of the following statements is true? (More than 1 statement may be true.)

For all containers, using an invalidated iterator is not a problem because the STL-library always checks for invalidated iterators.

For some containers there are operations that can cause all iterators to be invalidated.

For a given container, there are well defined operations which will cause invalidated iterators.

There are some containers for which iterator invalidation can never occur.

Question 2

What can be said in general about invalidation and iterators, pointers and indices?

Invalidation is only a problem with iterators and pointers. An index of a vector or array cannot become invalidated.

Only iterator invalidation will cause a program to crash. Invalidated pointers or indices will only cause the program to slow down.

Invalidation of an iterator or a pointer or an index can only occur when using STL-functions.

Programs can be written using iterators and pointers and indices in which invalidation does not occur.

Question 3

What does invalidation cause when using an STL container?

The source code for the STL-container becomes corrupted.

Indirect references to some elements (pointers, iterators) become unusable.

All elements of the container are removed.

A user must change the C++ compiler he or she has been using.

Extra links on the topic:

Week07 - Glossary

Submit weekly exercises¶

Questions to be submitted this week

Topic 8 of the course¶

Self-study¶

The topics for this week are the following: (i) Amortized performance and std::vector (ii) Verifying asymptotic performance (iii) Tips for increasing actual performance and (iv) Randomization

The following links will take you to the video-lectures and the accompanying slides:

Amortized performance and std::vector¶

Amortized performance and std::vector

slides for Amortized performance and std::vector

Verifying asymptotic performance¶

Verifying asymptotic performance

slides for Verifying asymptotic performance

Tips for increasing actual performance¶

Tips for increasing actual performance

slides for Tips for increasing actual performance

C++ examples

Randomization¶

Randomization: part 1.

Randomization: part 2

Randomization: part 3

slides for Randomization

Amortized performance and std::vector¶

Question 1

Amortized efficiency means

the best possible runtime efficiency a sequence of operations can ever achieve

the runtime efficiency one hopes to obtain from a sequence of operations

the average runtime efficiency for a sequence of operations

the worst (slowest) runtime efficiency from a sequence of operations

Question 2

Suppose we use an STL vector \(v\) and all we do is add elements to the end of \(v\). Suppose also that the size of \(v\) is doubled in situations when \(v\) runs out of memory. Which of the following is true concerning the efficiency of adding a single element to \(v\)?

The big-O runtime efficiency is linear in the size of \(v\) but the amortized efficiency is constant time.

The big-O runtime efficiency is constant time but the amortized efficiency is linear in the size of \(v\).

Both the big-O runtime efficiency and the amortized efficiency are always constant time.

Both the big-O runtime efficiency and the amortized efficiency can be constant time if \(v\) is sorted.

Verifying asymptotic performance¶

Question 1

With regard to verifying an algorithm’s asymptotic efficiency, which of the following are true? (More than 1 statement may be true.)

An algorithm’s asymptotic runtime efficiency can be verified by measuring it’s actual execution time for one input data.

An algorithm’s asymptotic runtime efficiency can be verified by measuring it’s actual execution time for sets of input data whose sizes span several orders of magnitude.

For one specific input data, the actual execution time of an algorithm will vary because of the other operations the computer is doing.

The only way to test an algorithm’s runtime efficiency is by measuring the actual execution time of the algorithm.

Question 2

Suppose for algorithm \(X\) we have a large collection of input data cases where the size of the input data spans several orders of magnitude. Suppose we run \(X\) for all inputs cases and we measure the execution time (say in seconds). If we want to say something about asymptotic efficiency of \(X\), why should we do some statistical analysis of the measurements?

To impress others that we know how to scientifically determine the asymptotic efficiency of \(X\).

To improve the likelihood that we make a correct assessment regarding the asymptotic efficiency of \(X\).

There is no good reason, because just by observing the measurements, we can easily see what is the asymptotic efficiency of \(X\).

Tips for increasing actual performance¶

Question 1

Choose the methods that can be used to improve the actual performance of some program. (There may be more than 1 correct choice.)

If some algorithm is coded as a single function, divide it into several functions.

For a particular computational task, choose an algorithm that computes only that which is necessary.

Suppose one can either use an STL algorithm or write one’s own algorithm. One should always use the STL algorithm.

For a particular computational task which can be done using two different algorithms, choose the more efficient.

Instead of computing the same quantity numerous times, store the quantity in a variable and recompute it only when it changes.

Suppose one can either use an STL algorithm or write one’s own algorithm. One should always write one’s own algorithm.

Question 2

Suppose in C++ we have stored a collection of \(n\) numbers in a vector \(v\) and \(n\) is very large. For which of the following situations does it make sense to first sort all the elements of \(v\)?

We wish to compute the median of the numbers in \(v\) once.

We wish to compute the sum of all the elements in \(v\).

We are given another vector \(u\) containing \(n\) numbers. For each number in \(u\) we want to search for it in \(v\).

We wish to compute the largest element in \(v\).

We wish to compute the sum of all those elements in \(v\) that are smaller than the median.

Question 3

Suppose in C++ we have a large collection of numbers stored in an unsorted vector \(v\) and we often add new elements to \(v\), but we never remove elements from \(v\). Suppose in addition we often need the largest element in \(v\). Of the following, which is the least efficient way of calculating the largest element?

Each time we want the largest element we use std::max_element(v.begin(), v.end()).

Each time we want the largest element we first sort \(v\) using `` std::sort(v.begin(), v.end())`` and then we get the largest element using v.back().

We maintain a separate variable \(vMax\), which contains the current largest element in \(v\). Each time a new element \(x\) is added to \(v\), we update \(vMax\) using vMax = std::max(vMax,x).

We maintain a separate variable \(vMax\). Each time we want the largest element we first execute vMax = v.front() and then we use a for-loop to go through all the elements of \(v\) one-by-one and update \(vMax\) when necessary.

Randomization¶

Question 1

What is a valid reason for using randomization in some algorithm?

To ensure that the function that generates random numbers is working properly.

To try to decrease the probability that a worst case occurs when using the algorithm.

To improve the asymptotic runtime efficiencies of the worst cases of the algorithm.

To change the behaviour of the algorithm so that we can never be sure what it will produce.

Question 2

When randomization is added to Quicksort to avoid Quicksort’s worst case behaviour, how is it typically added?

We use randomization to temporarily remove some elements from the subarray being sorted. These elements are later inserted back into the subarray.

Randomization is used to decide whether the first subarray we sort is to left of the pivot or to the right of the pivot.

We first compute the minimum and maximum elements in the subarray being sorted. We then randomly choose some number between the minimum and maximum to use as the pivot.

Before starting partitioning, we randomly choose some element from the subarray being sorted and use it as the pivot.

Question 3

Suppose we have a vector \(v\) having \(n\) elements and we randomly shuffle all \(n\) elements. What can be said about this shuffling operation?

The shuffle operation can be done with a runtime efficiency that is linear in \(n\).

After this shuffle we can be absolutely sure that the elements of \(v\) are not in increasing order.

It is always wise to perform this shuffling operation before searching for some particular number in \(v\).

After this operation the smallest element in \(v\) will always be to the left of the largest element in \(v\).

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

Trees and graphs

Tree data structures

Tree traversals

Invalidation

Amortized efficiency

Verifying asymptotic efficiency

Tips for increasing efficiency

Randomization

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

There is no shortage of opinions on how to improve the efficiency of C++ code. Here is one link and a warning. Some of information is quite technical. -A long discussion in stackoverflow:

Week08 - Glossary

Homework to be returned for these topics¶

Questions to be submitted this week

Course 9 topics¶

Self-study¶

The topics for this week are (i) The heap data structure, (ii) Implementing a heap as an array

The following links will take you to the video-lectures and the accompanying slides:

The heap data structure¶

The heap data structure (part 1)

The heap data structure (part 2)

The heap data structure (part 3)

slides

Implementing a heap as an array¶

Implementing a heap as an array (part 1)

Implementing a heap as an array (part 2)

Implementing a heap as an array (part 3)

slides

Heap and heap operations¶

Question 1

In a max-heap having at least two nodes

the key of a leaf can be greater than the key of the root

it may be that the subtree of some node is not itself a max-heap

one can never be sure where the largest key will be in the binary tree

some leaf will have the smallest key in the binary tree

Question 2

A heap is a binary tree. Which of the following properties does a heap’s binary tree possess? (More than 1 property may be valid.)

For a fixed number of nodes, the height of a the binary tree is as small as possible.

All leaves are at the same depth.

There is at most one node that has exactly one child.

The number of leaves at a even depth must be even and the number of leaves at an odd depth must be odd.

At the lowest depth, each leaf must be the only child of its parent.

Question 3

Which of the following happens when we add a new node to a max-heap?

We initially add the new node as a leaf. If the new node’s key is less than the key of the root, the new node will always remain a leaf.

We replace the existing root with the new node. We then reinsert the old root as a leaf anywhere in the tree and we are done.

We initially add the new node as a leaf. For as long as the new node’s key is larger than the key of its parent, we allow the new node to move up in the binary tree.

If the key of the new node is greater than that of the root, then we simply replace the root with the new node and discard the old root.

Question 4

In which of the following situations would we need to use the Heapify algorithm in a max-heap?

when a node has only one child and we need it to have 2 children

when the root has a child whose key is larger than the root’s key

when the key of a leaf is smaller than the key of its parent

when keys of all the nodes are the same

Question 5

Regarding the Buildheap algorithm, which of the following are true? (More than 1 statement may be true.)

To work properly Buildheap needs to know what are the non-leaf nodes of the input binary tree.

Buildheap processes the nodes of binary tree using in a preorder ordering.

Buildheap starts by forming small heaps. It then progressively forms larger heaps until eventually it has formed one heap from the entire input binary tree.

Buildheap will only work properly if its input is a heap.

Question 6

What does the Heap-Extract-Max algorithm compute?

It obtains the largest key from the heap and it adds a new leaf whose key is equal to the largest key.

For some positive integer \(k\), the algorithm forms a new max-heap having the \(k\) largest keys from the input heap. (The input \(k\) is at most the number of nodes in the input heap.)

It removes from the input max-heap all nodes whose keys are less than the largest key in the heap.

From the input max-heap, it obtains the largest key. It then removes the root and re-forms the remaining nodes into a new max-heap.

Question 7

Consider the following four algorithms: Buildheap, Heap-Extract-Max, Heapify and Heap-Insert. Assume that the heap used as input to each algorithm has \(n\) nodes. Of these four algorithms, which have runtime efficiencies that are logarithmic in \(n\)?

Buildheap and Heap-Insert

Buildheap, Heap-Extract-Max, and Heap-Insert

Heap-Extract-Max, Heapify and Heap-Insert

Buildheap, Heap-Extract-Max and Heapify

A Heap as an array¶

Question 1

Suppose a binary tree max-heap is stored in an array \(A\). Suppose \(A[i]\) corresponds to node \(x\). Which of the following are true? (More than one statement may be true.)

If \(x\) is the root, then \(i\) is the the first position in \(A\).

Suppose \(x\) is not the root. There does not exist a function having constant runtime efficiency with which we can compute the position in \(A\) of the parent of \(x\).

If \(x\) has two children, then there exist functions having constant runtime efficiency with which we can compute the positions in \(A\) of the children of \(x\).

If the max-heap has \(n\) nodes, the position of the rightmost leaf in \(A\) can be anything between \(1\) and \(n\).

If the max-heap has \(n\) nodes, then \(A[n]\) is the smallest key occuring in the heap.

If \(x\) is a leaf, then there are only two possibilities for element \(A[i+1]\). Either \(A[i+1]\) corresponds to another leaf or \(A[i+1]\) does not correspond to any node because \(x\) is the rightmost leaf in the heap.

Question 2

Of the following, what are the advantages of Heapsort as an algorithm for sorting numbers? (More than one statement may be true.)

No extra storage space is needed to sort the elements in the heap.

When using Heapsort one need not know the actual number of elements in the heap.

It has the same big-O asymptotic runtime efficiency as other fast sorting algorithms such as Mergesort.

When using Heapsort it is possible to test in constant time if the heap is already completely sorted or not.

When using Heapsort, one never need multiply by 2 or divide by 2 which makes Heapsort run very fast.

Question 1

Formulate a central question for the course, which this week’s videos will cover give the answer.

Question 2

Which video topic should be discussed in particular in a discussion session?

Heap as a binary tree

Heap operations and their run efficiencies

Heap as an array

Heapsort

Question 3

Was there anything particularly difficult about the content of the videos? What about interesting? Something you’d like to learn more about?

Extra links on the topic:

Typically a priority queue is implemented as a binary tree heap. An alternative data structure that can be used for a priority queue is a binomial tree heap

Week09 - Glossary