Functional programming language for manipulating binary tree

Assignment Help Other Subject
Reference no: EM132498468

Question 1:

This question is concerned with a functional programming language for manipulating binary rooted trees.

The set BT consists of all binary rooted trees whose vertices are elements of the set N of natural numbers. The empty tree is denoted by Ø.

The following basic primitive functions for manipulating elements of BT are given:

ROOT : BT → N , where ROOT(t) = the root of the non-empty tree t
LEFT : BT → BT , where LEFT(t) = the left subtree of the non-empty tree t RIGHT : BT → BT , where RIGHT(t) = the right subtree of the non-empty tree t
MAKE : BT x N x BT → BT , where MAKE(t, n, s) = the tree with root n, left subtree t and right subtree s
MAX : N x N → N, where MAX(m, n) = the maximum of m and n

(a) Let s be the following element of BT:

1280_figure.jpg

Draw the trees
MAKE(Ø, 9, RIGHT(s)) (1 mark)
MAKE(RIGHT(LEFT(s)), ROOT(RIGHT(s)), LEFT(LEFT(s)))

(b) A function F : BT → N is defined as below. F(t) = 0 if t = Ø
F(t) = ROOT(t) if t ≠ Ø and LEFT(t) = RIGHT(t) = Ø
F(t) = F(LEFT(t)) + F(RIGHT(t)) otherwise
Evaluate F(s) where s is the tree in part (a).

Describe the general effect of F on any tree in BT.

(c) The function ROOTMAX : BT → BT replaces the root of an input tree t with the maximum of the roots of the left and right subtrees of t (provided that L(t) ≠ Ø and R(t) ≠ Ø). Give a description, in terms of the basic primitive functions above, of the function ROOTMAX.

Question 2:

The following algorithm, bubblesort, sorts a list of n integers into increasing order by successively comparing adjacent elements and interchanging them if they are in the wrong order.

Input x1, x2, x3, ..., xn;

begin

for i := 1 to (n - 1) do

for j := 1 to (n - i) do if xj>xj+1then

begin

temp:= xj;

xj:= xj+1;

xj+1 := temp ;

end

else{do-nothing};

end

Output x1, x2, x3, ..., xn;

(a) When n = 4, trace the values of i, j, x1, x2, x3 and x4 for the input values x1 = 3, x2 = 2, x3 = 7, x4 =1.

(b) A time complexity function T(n) can be found for bubblesort by counting the number of times the comparison xj > xj +1 is made for a general

positive input n. Show that T(n) is O (n2).

(c) Another sorting algorithm requires 3n log2 n comparisons to sort a list of n integers into ascending order. Is this algorithm more efficient than bubblesort? Briefly justify your answer.

Reference no: EM132498468

Questions Cloud

Identify five of main characters in this hiroshima account : Identify five of the main characters in this Hiroshima account. Give their name, occupation, and the effect that the bombing may have had on them.
What were some specific events in the united states : What were some specific events in the United States that were connect to the feminist movement?
Discuss concepts that is very relevant to your profession : In the past 8 weeks, you have learned many data science concepts / constructs. Please discuss 3 concepts that is very relevant to your profession.
Address specific political conflicts and attempts : In your answer, address specific political conflicts and attempts to solve them between 1846 and 1861.
Functional programming language for manipulating binary tree : Describe the general effect of F on any tree in BT and Give a description, in terms of the basic primitive functions above, of the function ROOTMAX
What you liked about the presentation overall : For Part 2, you will need to watch a majority of the PowerPoint projects from your classmates and then choose two (2) to respond to in the discussion board.
Why did the ussr blockade berlin : Why did the USSR blockade Berlin and what was the Berlin Airlift?
Discuss the relevance of technology to today companies : Discuss the relevance of technology to today's companies today. Must Excel charts created by the student and discussed in the paper.
Democratic principles in the colonies : What are 3 organizations before 1776 that had democratic principles in the colonies?

Reviews

Write a Review

Other Subject Questions & Answers

  Cross-cultural opportunities and conflicts in canada

Short Paper on Cross-cultural Opportunities and Conflicts in Canada.

  Sociology theory questions

Sociology are very fundamental in nature. Role strain and role constraint speak about the duties and responsibilities of the roles of people in society or in a group. A short theory about Darwin and Moths is also answered.

  A book review on unfaithful angels

This review will help the reader understand the social work profession through different concepts giving the glimpse of why the social work profession might have drifted away from its original purpose of serving the poor.

  Disorder paper: schizophrenia

Schizophrenia does not really have just one single cause. It is a possibility that this disorder could be inherited but not all doctors are sure.

  Individual assignment: two models handout and rubric

Individual Assignment : Two Models Handout and Rubric,    This paper will allow you to understand and evaluate two vastly different organizational models and to effectively communicate their differences.

  Developing strategic intent for toyota

The following report includes the description about the organization, its strategies, industry analysis in which it operates and its position in the industry.

  Gasoline powered passenger vehicles

In this study, we examine how gasoline price volatility and income of the consumers impacts consumer's demand for gasoline.

  An aspect of poverty in canada

Economics thesis undergrad 4th year paper to write. it should be about 22 pages in length, literature review, economic analysis and then data or cost benefit analysis.

  Ngn customer satisfaction qos indicator for 3g services

The paper aims to highlight the global trends in countries and regions where 3G has already been introduced and propose an implementation plan to the telecom operators of developing countries.

  Prepare a power point presentation

Prepare the power point presentation for the case: Santa Fe Independent School District

  Information literacy is important in this environment

Information literacy is critically important in this contemporary environment

  Associative property of multiplication

Write a definition for associative property of multiplication.

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