Binary search tree and graph, C/C++ Programming

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.

Posted Date: 2/27/2013 7:03:38 AM | Location : United States






Your posts are moderated
Related Questions
Create Complex number using constructor: class complex                                 {                                                   private:

Smugglers are becoming very smart day by day. Now they have developed a new technique of sending their messages from one smuggler to another. In their new technology, they are send

Inheritance and Reuse Consider a car manufacturing company. When they require building a new car, they have two choices. They can start from the scratch, or they can change an


Aim: To implement a program to create, update & display account & admin record of person using display account & admin records of person using virtual base class.. Code:

Available, and the right kind of programs. My son wants to stop using ice. He has organised detox a number of times, and is always successful. It is the next stage, rehab, where

WHAT IS A C LANGUAGE? C IS A PROGRAMMING?

Explain the Defination and Declaration of Union? Generally in terms the composition of a union may be defined as be as union tag { member 1; member 2; member m; }; Wh

The probabilistic Hough transform uses random sampling instead of an accumulator array. In this approach the number of random samples r, is not specified in the OpenCV call, but is

Reference Types The symbol "&" is interpreted as an address operator as well as AND operator. This operator is also used to declare a "reference variable". A reference is refer