ICS 46 Spring 2022, Exercise Set 4

Getting started

First of all, be sure that you've read the Reinforcement Exercises page, which explains everything you'll need to know, generally, about how the reinforcement exercises will work this quarter. Make sure you read that page before you continue with this one.

Before you begin work on these reinforcement exercises, there's a chore that you'll need to complete on your ICS 46 VM to get it set up to proceed.

Refreshing your ICS 46 VM environment

Even if you previously downloaded your ICS 46 VM, you will probably need to refresh its environment before proceeding with these exercises. Log into your VM and issue the command ics46 version to see what version of the ICS 46 environment you currently have stored on your VM. Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you'll need to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with these exercises.

2022-04-26 07:03:49
Exercise Set 4 template added

If you're unable to get outgoing network access to work on the ICS 46 VM — something that afflicts a handful of students each quarter — then the ics46 refresh command won't work, but an alternative approach is to download the latest environment from the link below, then to upload the file on to your ICS 46 VM using SCP. (See the Project #0 write-up for more details on using SCP.) Once the file is on your VM, you can run the command ics46 refresh_local NAME_OF_ENVIRONMENT_FILE, replacing NAME_OF_ENVIRONMENT_FILE with the name of the file you uploaded; note that you'd need to be in the same directory where the file is when you run the command.

ics46-2022spring-environment.tar.gz

Creating your project directory on your ICS 46 VM

A project template has been created specifically for this set of exercises, containing a similar structure to the basic template you saw in Project #0. Among other things, it contains a version of the gather script that's different from the ones in the projects, so you'll absolutely need to use the set3 template for these exercises, as opposed to the basic one.

Decide on a name for your project directory, then issue the command ics46 start YOUR_CHOSEN_PROJECT_NAME set4 to create your new project directory using the set4 template. (For example, if you wanted to call your project directory set4, you would issue the command ics46 start set4 set4.)

Problem 1 (2 points)

Determining what your keys will be

First, make a temporary note of your UCInetID — that's what comes before @uci.edu in your UCI email address — somewhere. You won't need to submit it, but you're going to need it to determine what keys you'll use when solving this problem.

Next, make a note of the following numbers somewhere temporary:

53, 37, 63, 25, 97, 99, 51

After that, remove any duplicate letters or digits from your UCInetID, leaving only the first occurrence of any given letter or digit.

For example, if your UCInetID was thornton, three characters appear twice: t, o, and n, so we'll remove that duplication, leaving only thorn.
As another example, if your UCInetID was boototallygreat, there are a whole bunch of duplicate characters, but if we keep only the first occurrence of each one, we'd be left with botalygre.
Do likewise with your own UCInetID.

Then, apply the following translation to each unique letter or digit from your UCInetID, yielding a sequence of integers.

If it's a digit, multiply it by 2. For example, the digit 3 would turn into the value 6, while the digit 8 would turn into the value 16.
If it's a letter, figure out which letter of the alphabet it is. a is the first letter, so its value would be 0; b would have the value 1; and so on, with z having the value 25. Multiply that value by 2 and add 26. So, ultimately, a would be 0 * 2 + 26 = 26, while f would be 5 * 2 + 26 = 36.
If it's anything else (i.e., not a letter or digit), skip it. (I don't think UCInetIDs ever have anything in them that aren't letters or digits.)

You now have two sequences of integers:

53, 37, 63, 25, 97, 99, 51 — the hard-coded sequence given near the top of this problem.
The sequence of integers arising from translating your UCInetID. For example, if your UCInetID was thornton, that sequence would be 64, 40, 54, 60, 52.

Finally, intersperse these sequences, by taking the first value of the first sequence, followed by the first value of the second sequence, followed by the second value of the first sequence, and so on, alternating. When you run out of values in one of the sequences, continue taking values from the other sequence until it's also fully exhausted.

All in all, if your UCInetID is thornton, the entire interspersed sequence would be:

53, 64, 37, 40, 63, 54, 25, 60, 97, 52, 99, 51

That's the sequence of keys you'd use to solve this problem if your UCInetID was thornton. Of course, it's not — that's mine! — so you'll use the sequence that corresponds to your own UCInetID.

If that all seems overwhelming, here's the good news: In the set4 project template, the file exp/expmain.cpp contains a program that can calculate all of this for you. After you've created your project directory, issue these two commands from within your project directory:

./build exp
./run exp

Enter your UCInetID as input. Your output will be the sequence of keys that you'll use in this problem.

What's the problem?

Suppose you started with an empty binary search tree, then inserted the sequence of keys that you determined previously (in that order), one at a time.

Write a table that describes a few aspects of the binary search tree after each of the keys is inserted. The structure of your table should be as follows.

Key Inserted	Height of Tree	Path to Key
53	0	{53}
...	...	...

Each Height of Tree should specify the height of the binary search tree after the key was inserted.

Each Path to Key should specify the sequence of keys in the nodes on the path from the root of the tree to where the newly-inserted key ended up. For example, if the key 87 was added as the right child of the root and the root's key was 86, you would write {86, 87}.

Perhaps not surprisingly, there will be one row in your table for each key in the sequence you're meant to insert. Don't submit diagrams of the tree's contents or other explanation; we only want the table.

What to submit

Add one PDF file to your core directory with this name: problem1.pdf, which contains your table.

Problem 2 (2 points)

Determining what your keys will be

Use the same methodology in Problem 1 to determine what keys you should use to solve the problem. For example, if your UCInetID was thornton, you would use these keys (but, of course, that's my UCInetID, so you'll want to use the ones that correspond to yours!):

53, 64, 37, 40, 63, 54, 25, 60, 97, 52, 99, 51

What's the problem?

Suppose you started with an empty AVL tree, then inserted the sequence of keys that you determined previously (in that order), one at a time.

Write a table that describes a few aspects of the AVL tree after each of the keys is inserted. The structure of your table should be as follows.

Key Inserted	Height of Tree	Rotations Done	Path to Key
53	0	none	{53}
...	...	...	...

Each Height of Tree should specify the height of the AVL tree after the key was inserted and after any rotations are completed.

Each Rotations Done should specify which rotations were done, if any, and the key in the node in which they were rooted. For example, if an LL rotation was done rooted at a node containing the key 88, you would write LL(88). Write none if no rotations were done as a result of inserting the key.

Each Path to Key should specify the sequence of keys in the nodes on the path from the root of the tree to where the newly-inserted key ended up, again after any rotations were done. For example, if the key 89 was added as the right child of the root and the root's key was 88, you would write {88, 89}.

What to submit

Add one PDF file to your core directory with this name: problem2.pdf, which contains your table.

Problem 3 (2 points)

Suppose you started with an empty binary search tree. We've seen previously that inserting the keys 1, 2, 3, 4, 5, 6, 7 (in that order) would lead to a binary search tree whose shape we called degenerate.

Propose a second ordering of the same keys that would also lead to a degenerate-shaped binary search tree.
If possible, propose a third ordering of the same keys that would also lead to a degenerate-shaped binary search tree. If there are no more orderings other than the one we provided and the second one you proposed, briefly explain why there are no more.

What to submit

Add one PDF file to your core directory with this name: problem3.pdf, which contains your answer to these two questions.

Problem 4 (2 points)

Suppose you started with an empty binary search tree, then inserted a large, odd number of unique integer keys using the following algorithm.

Sort the keys into ascending order and store them in a std::vector.
Insert the middle key — the one with an equal number of keys less than and greater than it — into the tree first.
Then, in alternating fashion, insert the largest remaining key that's smaller than the middle key that hasn't already been inserted, then the smallest remaining key that's larger than the middle key that hasn't already been inserted. Continue until all of the keys have been inserted into the tree.

Let's assume that there are n keys that have been inserted in this fashion, and let's also assume that the keys (after sorting) are not entirely consecutive (i.e., each key is not 1 greater than the key preceding it). Answer the following questions about the resulting binary search tree.

What is an asymptotic notation that best describes the height of the resulting binary search tree? In a sentence or two, explain why.
What is an asymptotic notation that best describes the time required to insert another key into that binary search tree after it's been built, assuming the key was chosen completely at random and not subject to the arrangement described above? In a sentence or two, explain why.
Assuming that all you had was the binary search tree (i.e., you don't have the std::vector of keys anymore), propose an algorithm for printing the keys in descending order (i.e., largest to smallest). What is an asymptotic notation that best describes the time required to print them? What is an asymptotic notation that best describes the memory required to print them?

What to submit

Add one PDF file to your core directory with this name: problem4.pdf, which contains your answer to these two questions.

Problem 5 (2 points)

Consider the example skip list shown in the Skip Lists notes. (There are two diagrams shown, but both have the same contents.) We saw when we talked about skip lists that their performance characteristics were based largely on the fairness of the "coin flipping" that's done while keys are being inserted; if the coin is fair (i.e., it has a 50% chance of being heads or tails), then we'll see better performance than if it isn't.

Can you determine with a reasonable level of confidence, given only the diagram of the skip list in the Skip Lists notes, whether the coin used while generating that skip list was fair? If so, how would you do it (and do you think the coin was fair)? If not, what additional information would you need that you don't already have?

What to submit

Add one PDF file to your core directory with this name: problem5.pdf, which contains your answer to this question.

Deliverables

In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submited in the incorrect area.

Submit each file as-is, without putting it into a .tar.gz file or arranging it in any other way. (There is a gather script in the set4 template, but there's no need to use it.) If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for, we will not be offering you any credit on the submission. There are no exceptions to this rule.

Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally, and we won't be able to offer any credit on exercises that you forgot to submit.

Can I submit after the deadline?

Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 3% of your grade, so it's not a disaster if you miss one of them along the way.

Can I work on this outside of the VM?

Yes, but be aware that you must submit the files in the appropriate format, and that any C++ code you submit must compile and run on the ICS 46 VM.