1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...

Question

Question

1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...

1. Let A = {a₁, ..., a_n} and B = {b₁, ..., b_m} be two sets of numbers. Consider the problem of finding their intersection, i.e., the set C of all the numbers that are in both A and B.

a. Design a presorting based algorithm for solving this problem and determine its efficiency class.

2. Estimate how many searches will be needed to justify time spent on presorting an array of 10³ elements if sorting is done by mergesort and searching is done by binary search.

3. Solve the following system by Gaussian elimination:

x₁ + x₂ + x₃ = 2

2x₁ + x₂ + x₃ = 3

x₁ - x₂ + 3x₃ = 8

4. Solve the system of problem #3 by computing the inverse of its coefficient matrix and then multiplying it by the vector on the right-hand side.

5. For each of the following lists, construct an AVL tree by inserting their elements successively, starting with the empty tree.

a. 1, 2, 3, 4, 5, 6

b. 6, 5, 4, 3, 2, 1

c. 3, 6, 5, 1, 2, 4

6. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by the bottom-up algorithm.

7. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by successive key insertions (top-down algorithm).

8. Apply Horner's rule to evaluate the polynomial

p(x) = 3x⁴ - x³ + 2x + 5 at x = -2.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

DATE -List and then n Single sort hat list After the (ompares the peiYs 汗5 Consecutive elements.cxdd Common ualu es toClist c

31/ Given eavations aly 2. рез 8 3 co elic eint So auaented maty

2 3 AM=12 I 2. 2 O O L 2+ 久2 =-/ナ2

$IDATE 21-3-2 っe \ =$

-2 lerccedes the hight -so-first DCI otahiom of to mke it 2. 3 nset 2 2 make rotLCa) ho make hight bclanets e

DATE 2 2. 4 ㄐ 3 3 mak e rotation of C2) to spakeit aur inau AVL ree fem a is 2 3

6 5 5 4 balance-to-ee rnake -to-make-is 5 6 3 odlance A

DATE 5 3 2 4 2 3 2 6

2. 2 (3 3 6 6) 弋 4o et balanced 32-et 3 (6

PAGE No. DATE 2. balanced AVL ee asfelloos 32 2 Ls 6 venlist heap fen algorithm -. CIS--fo ( 1 o aos given list bi bo ttom V 6 5 3 7 4 Iy ) 8 7 5 3 6 St aiven heap top-docen cugorithm 3 6 3573 6 4 here new element insered in hean S_ S hous n b (一) underlined Palt nomic is Solve

Add a comment

Answer 2

Similar Homework Help Questions

Design and Analysis of Algorithms 1. For each of the following lists, construct an AVL tree...

Design and Analysis of Algorithms 1. For each of the following lists, construct an AVL tree by inserting their elements successively, starting with the empty tree. 3, 2, 1, 4, 5, 6, 7 2. Construct a 2-3 tree for the list W, E, L, C, O, M, E, Y, O, U. Use the alphabetical order of the letters and insert them successively starting with the empty tree.
Not asking for code. For each of the following lists, construct both an AVL tree and...

Not asking for code. For each of the following lists, construct both an AVL tree and a 2-3 tree by inserting their elements successively, starting with the empty tree. 1, 2, 3, 4, 5, 6 6, 3, 2, 1, 4, 5
6. Draw a diagram of the double RL-rotation in its general form. A partial solution is...

6. Draw a diagram of the double RL-rotation in its general form. A partial solution is given. Fill in the missing parts inside the box. (pt) For the following list of numbers, construct an AVI tree by inserting their elements successively, starting with the empty tree. 1.2.3.4.5.6. The insertions of the first 4 numbers are given. Draw diagrams to show the rest of the process. Note that you need to indicate the balance factor of each node, diagrams before and...

Solve the linear program using the simplex algorithm method maximize Z = 5x1 + x2 +...

Solve the linear program using the simplex algorithm method maximize Z = 5x1 + x2 + 3x3 + 4x4 subject to: x1 – 2 x2 + 4 x3 + 3x4 s 20 –4x1 + 6 x2 + 5 X3 – 4x4 = 40 2x1 – 3 x2 + 3 x3 + 8x4 5 50 X1, X2, X3 , X4 20
Trees and Heaps 1. Show that the maximum number of nodes in a binary tree of...

Trees and Heaps 1. Show that the maximum number of nodes in a binary tree of height h is 2h+1 − 1. 2. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree. 3. What is the minimum number of nodes in an AVL tree of height 15? 4. Show the result of inserting 14, 12, 18, 20, 27, 16,...
Data structures Exercises: For the following binary tree (Index-Value): 0 1 2 3 4 5 6...

Data structures Exercises: For the following binary tree (Index-Value): 0 1 2 3 4 5 6 7 8 9 A C E G B P D X F H Give the pre-order traversal. Give the post-order traversal. Give the in-order traversal. Determine the height of the tree. Using these values: 8 6 4 3 5 9 2 1 6 Build a binary search tree. Build an AVL Tree. Build a 2-3 Tree. Build a min-heap. Build a max-heap. Apply a...

Draw an AVL tree (initially empty) at each step when inserting the following numbers in order:...

Draw an AVL tree (initially empty) at each step when inserting the following numbers in order: 1; 2; 5; 4; 6; 3; 10; 9; 7; 8 Now, draw the above AVL tree at each step when deleting the following numbers in order (assuming that the substitution on deleting a node is done by replacing it with the minimum in the right subtree): 4; 5; 6
2x1 − x2 − 3x3 − 2x4 = 1 x1 − x2 − 4x3 − 2x4...

2x1 − x2 − 3x3 − 2x4 = 1 x1 − x2 − 4x3 − 2x4 = 5 3x1 − x2 − x3 − 3x4 = −2 x1 + 2x3 − x4 = −4
C. 7. True/False Questions. (2 points each) a. Applying Horner's Rule, an n-degree polynomial can be...

C. 7. True/False Questions. (2 points each) a. Applying Horner's Rule, an n-degree polynomial can be evaluated at a given point using only n multiplications and n additions. b. Quick Sort and Merge Sort are comparison-based sorting algorithms. Heap Sort and Distribution Counting Sort are not comparison-based sorting algorithms. An AVL tree applies four types of rotations: RIGHT, LEFT, RIGHT-LEFT, and LEFT-RIGHT. d. When an AVL tree's left sub-tree is left-heavy, a LEFT rotation is needed. e. When an AVL...

Determine whether the system is consistent 1) x1 + x2 + x3 = 7 X1 -...

Determine whether the system is consistent 1) x1 + x2 + x3 = 7 X1 - X2 + 2x3 = 7 5x1 + x2 + x3 = 11 A) No B) Yes Determine whether the matrix is in echelon form, reduced echelon form, or neither. [ 1 2 5 -7] 2) 0 1 -4 9 100 1 2 A) Reduced echelon form B) Echelon form C) Neither [1 0 -3 -51 300 1-3 4 0 0 0 0 LOO 0...

1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...

Homework Answers

Add Answer to:
1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...

Post as a guest

Earn Coins

Design and Analysis of Algorithms 1. For each of the following lists, construct an AVL tree...

Not asking for code. For each of the following lists, construct both an AVL tree and...

6. Draw a diagram of the double RL-rotation in its general form. A partial solution is...

Solve the linear program using the simplex algorithm method maximize Z = 5x1 + x2 +...

Trees and Heaps 1. Show that the maximum number of nodes in a binary tree of...

Data structures Exercises: For the following binary tree (Index-Value): 0 1 2 3 4 5 6...

Draw an AVL tree (initially empty) at each step when inserting the following numbers in order:...

2x1 − x2 − 3x3 − 2x4 = 1 x1 − x2 − 4x3 − 2x4...

C. 7. True/False Questions. (2 points each) a. Applying Horner's Rule, an n-degree polynomial can be...

Determine whether the system is consistent 1) x1 + x2 + x3 = 7 X1 -...

1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...

Homework Answers

Add Answer to: 1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...

Post as a guest

Earn Coins

Add Answer to:
1. Let A = {a1, ..., an} and B = {b1, ..., bm} be two sets...