COMP.4040 Analysis of Algorithms Assignment

Assignment Help Computer Engineering

Reference no: EM133116101

COMP.4040 Analysis of Algorithms - University of Massachusetts Lowell

Question 1: Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? Justify.
(a)2, 252, 401, 398, 330, 344, 397, 363.
(b)924, 220, 911, 244, 898, 258, 362, 363.
(c)925, 202, 911, 240, 912, 245, 363.
(d)2, 399, 387, 219, 266, 382, 381, 278, 363.
(e)935, 278, 347, 621, 299, 392, 358, 363.

Question 2: The lowest common ancestor of two nodes v₁ and v₂ (denoted by LCA(v₁, v₂)) of a rooted tree that has both v₁ and v₂ as descendants.
(a) Write pseudocode that computes LCA (v₁, v₂) in a given BST T .
(b) What is the time-complexity of your algorithm? Give the time complexity as a function of n = |T | and of h, the height of T .

Question 3: Given a binary tree T give a simple algorithm to check whether T is a BST. Try to use functions already de ned in class. Argue correctness with one or two sentences. What is the time complexity?

Question 4: Show the BST obtained by successively inserting the keys 45, 38, 31, 41, 12, 39, 40, 42 into an initially empty BST. Then, show the resulting BST after deleting 38.

Question 5: Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty red-black tree.

Question 6: You are given a red-black tree, T, and some value v (not contained in T ). You must split T into two red-black trees, such that one contains all values less than v, and the other contains all values greater than v.

Try to get logarithmic time, but if you can get anything sub-linear, that's also good.

Reference no: EM133116101

Questions Cloud

Design software application : You have been requested to design a software application for a large toy company that provides an online product catalog for ordering all types of toys and game

Discuss the goal of family-owned public listed corporations : Discuss if the goal of family-owned public listed corporations is similar to those of corporations at large. How might agency conflicts arise in family-owned co

Explain the current annual cost of university : An investor plans to pay his son's university tuition fees for 4 years starting 18 years from now. The current annual cost of university is £9,200, and they exp

Identify your career objectives : The purpose of the reflection paper is to identify your career objectives, summarize how the MSIS program has helped you achieve those objectives

COMP.4040 Analysis of Algorithms Assignment : COMP.4040 Analysis of Algorithms Assignment Help and Solution, University of Massachusetts Lowell - Assessment Writing Service

Forensic investigation : How can it be used to question the conclusions drawn from a forensic investigation?

Why the market cap weighted index is more popular : Briefly explain why the market cap weighted index is more popular as a replication portfolio compared to an equally weighted index.

Exchange rate between myr and gbp : How Covid-19 pandemic affect the exchange rate between MYR and GBP.

Develop computer and internet security policy : You have been hired as the CSO (Chief Security Officer) for an organization. Your job is to develop a computer and internet security policy

User Account

All Pages