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

Assignment Help:

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.


Related Discussions:- Binary search tree and graph

Last ant on rod, You are given a collection of words, say as in a dictionar...

You are given a collection of words, say as in a dictionary. You can represent it in the following compressed form: the first word will be followed by a sequence of a pair of numbe

Parking garage, A parking garage charges a $2.00 minimum fee to park for up...

A parking garage charges a $2.00 minimum fee to park for up to three hours and an additional $0.50 per hour for each hour or part thereof over three hours. The maximum charge for a

Develop a motion sensor in altera control, Develop a Motion sensor in Alter...

Develop a Motion sensor in Altera control Project Description: I want a project written in c using Altera eclipse development tool, that controls a motion sensor ( SRF05 ) fr

Define constructors-extract and insert operators, For your class to work pr...

For your class to work properly, you'll need to define appropriate constructors, extract and insert operators, and of course arithmetic operators. (If you wanted to use it as a gen

Algorithms, create algorithm for doubly link list using c data structure

create algorithm for doubly link list using c data structure

Minimum shelves, write a c++ program, that finds the minimum total number o...

write a c++ program, that finds the minimum total number of shelves, including the initial one, required for this loading process.

We want database development, Presently we are using several spreadsheets t...

Presently we are using several spreadsheets to give weekly activity and income reports. Much of the information is being frequently re-keyed into several spreadsheets - we are look

Nested if else, input marks of c and c++ if c grater than equal to 50 grate...

input marks of c and c++ if c grater than equal to 50 grater than 50 you are pass if c greater than equal to 50 c++ less than 50 than supplementry c++ if c less then 50 and c++ gra

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd