Important Note: No course works, which have been submitted via hard copies or emails, will be accepted
- a short essay below edited in a document (word, other)
- files with an exemplary code in Java or C++ for all three problem sets described below.
Essay: You will often be called upon to "give an algorithm" to solve a certain problem. Your write-up should take the form of a short essay. The body of the essay should provide the following:
1. A description of the algorithm in English.
2. A description of the algorithm in pseudo-code by using fundamental programming structures (loops for iteration, recursion, sequences, if-then-else statements).
3. A flow chart diagram (see initial lectures) to show more precisely how your algorithm works.
4. Any diagrams illustrating appropriate data structures, e.g., trees, graphs, at their creation, immediate and final stages.
5. An analysis of the running time of the algorithm in terms of a Big-O Notation.
Implementation/Exemplary code: For the attempted implementation, you may re-use any exemplary code in association with the related data structures as presented in the tutorials so far (see programming exercises). Full marks for the implementation will be allocated for a successfully running code.
Problem Set 1
If we insert a set of n items into a binary search tree using TREE-INSERT, the resulting tree may be horribly unbalanced. As we saw in class, however, we could expect randomly built binary search trees to be balanced. Therefore, if we want to build an expected balanced tree for a fixed set of items, we could randomly permute the items and then insert them in that order into the tree.
What if we do not have all the items at once? If we receive the items one at a time, can we still randomly build a balanced binary search tree out of them?
You will define and implement an algorithm that answers this question in the affirmative.
Each item x has a key key[x]. In addition, we assign priority[x], which is a random number chosen independently for each x. We assume that all priorities are distinct. The nodes of the underpinning binary tree are ordered so that (1) the keys obey the binary-search-tree property and (2) the priorities obey the min-heap order property. In other words,
- if v is a left child of u, then key[v] < key[u];
- if v is a right child of u, then key[v] > key[u]; and
- if v is a child of u, then priority(v) > priority(u).
Your algorithm should be working and tested (i.e., checked for correctness) in both, definition and implementation, with the following example:
- Input: We assume that you are given the initial set of items {A(10), B(7), E(23), G(4),
H(5), K(65), I(73)}, with the randomly assigned priorities to the elements given in parentheses
- The tree after inserting a node with key C and priority 25.
- The tree after inserting a node with key D and priority 9.
- The tree after inserting a node with key F and priority 2.
Problem Set 2
Professor Cloud has been consulting in the design of the most anticipated game of the year:
Takehome Fantasy XII. One of the levels in the game is a maze that players must navigate through multiple rooms from an entrance to an exit. Each room can be empty, contain a monster, or contain a life potion. As the player wanders through the maze, points are added or subtracted from her life points L. Drinking a life potion increases L, but battling a monster decreases L. If L drops to 0 or below, the player dies.
Important Note: No course works, which have been submitted via hard copies or emails, will be accepted
the maze can be represented as a digraph G = (V,E), where
vertices correspond to rooms and edges correspond to (one-way) corridors running from room to
room. A vertex-weight function f : V → represents the room contents:
- If f(v)=0, the room is empty.
- If f(v)> 0, the room contains a life potion. Every time the player enters the room, her
life points L increase by f(v).
- If f(v) < 0, the room contains a monster. Every time the player enters the room, her
life points L drop by |f(v)|, killing her if L becomes non-positive.
The entrance to the maze is a designated room s ∈ V, and the exit is another room t ∈ V.
Assume that a path exists from s to every vertex v ∈ V, and that a path exists from every
vertex v ∈ V to t. The player starts at the entrance s with L = L0 > 0 life points. For
simplicity, assume that the entrance is empty: f(s) = 0.
Professor Cloud has designed a program to put monsters and life potions randomly into the maze, but some mazes may be impossible to safely navigate from entrance to exit unless the player enters with a sufficient number L0 > 0 of life points. A path from s to t is safe if the player stays alive along the way, i.e., her life points never become non-positive. The maze is called r-admissible if there is a safe path through the maze when the player begins with L0 = r life points. For instance, the maze of our figure is call 1-admissible.
Help the professor by designing and implementing an efficient algorithm to determine the minimum value r for which a given maze is r-admissible, or determine that no such r exists.
Problem Set 3
GreedSox, a popular major-league baseball team, is interested in one thing: making money. They have hired you as a consultant to help boost their group ticket sales. They have noticed the following problem. When a group wants to see a ballgame, all members of the group need seats (in the bleacher section), or they go away. Since partial groups cannot be seated, the bleachers are often not full. There is still space available, but not enough space for the entire group. In this case, the group cannot be seated, losing money for the GreedSox.
The GreedSox want your recommendation on a new seating policy. Instead of seating people first-come/first-serve, the GreedSox decide to seat large groups first, followed by smaller groups, and finally singles (i.e., groups of 1).
You are given a set of groups, G[1...m]=[g1,g2,...,gm], where gi is a number representing the size of the group. Assume that the bleachers seat n people. Help GreedSox define and implement an algorithm with functions ADMIT(i) admitting group i, and REJECT(i) sending away group i, as well as with its associated data structure(s). The algorithm should optimise the seating of groups policy such that GreedSox maximise its income.
Note: These problem sets have been defined in consultation with Professors Erik D. Demaine and Charles E.