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

Need android app development, Project Description: I am seeking a develo...

Project Description: I am seeking a developer who can start an app from scratch and get it delivered to me as soon as possible. It is a little android based app. A background on

Why are all header files not declared in every c program, Why are all heade...

Why are all header files not declared in every C program? - Declaring all header files in each program would result in increase in overall file size and load of the program. It

factorial series, 1)      Factorial (for this question just provide an a...

1)      Factorial (for this question just provide an answer for each part)  1.1  Debug the following program to calculate N! #include using namespace std; main()

Define the keywords of c language, Define the Keywords of c language? C...

Define the Keywords of c language? C keeps a small set of keywords for its personal use. These keywords can't be used as identifiers in the program. Here is the list of keyword

Minimum shelf, At a shop of marbles, packs of marbles are prepared. Packets...

At a shop of marbles, packs of marbles are prepared. Packets are named A, B, C, D, E …….. All packets are kept in a VERTICAL SHELF in random order. Any numbers of packets with thes

What are the types of control structures in programming, What are the vario...

What are the various types of control structures in programming? - Primarily there are 3 types of control structures in programming: Sequence, Selection and Repetition. - Se

Odd even program, Write a program called OddEven that will prompt the user ...

Write a program called OddEven that will prompt the user for an integer and print/display a message indicating whether it is even or odd. Continue prompting for numbers from the us

Car rental project, I need a project on car rental system using c programmi...

I need a project on car rental system using c programming only of college level

Minimumshelf, Write a program that finds the minimum total number of shelve...

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

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