S
  1. study help
  2. subject categories
  3. computer science
  4. algorithms
  5. august 2018
  6. 06

Algorithms Questions and Answers August 06, 2018

Expert-verified solutions to help you succeed

Q:Question:(a) Draw all non-isomorphic rooted trees (i.e. trees with their unique roots) having three vertices.

Q:Question:Question 9: In which order are the vertices of the ordered rooted tree in Exercise 7 visited using a postorder traversal? 7.A:Answer:See a step by step answer

Q:Question:Use the unroot tree to illustrate all possible rooted trees Unroot Tree

Q:Question:Answer these questions about the rooted tree illustrated below.A:Answer:1. An internal vertex is a vertex that is not a le...

Q:Question:sketch and unlabeled rooted tree with planar code: 101010101010

Q:Question:Please solve it a) Draw the rooted tree which is given with prefix form of (??+B-D F+A C). b) Draw the rooted tree which is given with postfix form of (E D-A+B C-F ??+).

Q:Question:Consider the rooted tree T. What is the height of the tree?

Q:Question:In which order are the vertices of the ordered rooted tree shown below visited using an postorder traversal? abdecfg dfgebca dbfegac debfgca abcdefg abdfgec dbeafcgA:Answer:See a step by step answer

Q:Question:QUESTION 7 Is the rooted tree in Exercise 4 a full \( m \)-ary tree for some positive integer \( m \) ?What is the level of each vertex of the rooted tree in Exercise 4 ?

Q:Question:Answer these questions about the rooted tree illustrated below.A:Answer:1. Which vertex is root ? Answer : a Explanation :...

Q:Question:Determine the order in which a preorder traversal visits the vertices of the given ordered rooted tree Determine the order in which a postorder traversal visits the vertices of the given ordered rooted treeA:Answer:Thank you.please give thumbs up. If you have any q...

Q:Question:9. Determine the order in which a post-order traversal visits the vertices of the ordered rooted tree given below:A:Answer:See a step by step answer

Q:Question:these questions about the rooted tree illustrated. a) Which vertex is the root? b) Which vertices are internal? c) Which vertices are leaves? d) Which vertices are children of \( j \) ? e) Which vertex is the parent of \( h \) ? f) Which vertices are siblings of \( o \) ? g) Which vertices are ancestors of \( m \) ? h) Which vertices

Q:Question:Discrete Math (1) Draw all the nonisomorphic rooted trees with four vertices (using isomorphism for directed graphs). Root your trees at the top.A:Answer:See a step by step answer

Q:Question:Answer these questions about the rooted tree illustrated below.A:Answer:?Answer : (1) Root of a graph is the vertes that h...

Q:Question:8. Performs preorder, inorder and postorder traversals based on the rooted tree below: (6 Marks)A:Answer:See a step by step answer

Q:Question:How many non-isomorphic rooted trees are there with 3 vertices? Using isomorphism for directed graphs.A:Answer:See a step by step answer

Q:Question:Answer these questions about the rooted tree illustrated below.A:Answer:Given tree is i)internal vertices area,b,c,d,e,...

Q:Question:Node 1 is the root. Node 20 is the goal. Path costs are showed in the above binary tree. Find the path from 1 to 20 with the following: 1. Breath-first search 2. Uniform-cost search 3. Depth-first search 4. Depth-limit search 5. Iterative deepening depth-first search

Q:Question:please explain and show steps 9. (15 points) Apply depth-first search to the graph below to obtain a depth-first search numbering of the vertices, (if there is a choice of vertices, choose the vertex that appears first in alphabetical onder). Start at F.

Q:Question:For the graph shown in Fig. 3, starting at vertex 'a' and resolving ties by the vertex alphabetical order, traverse the graph by depth-first search and construct the corresponding depth-first search tree. Give the order in which the vertices were reached for the first time (pushed onto the traversal stack) and the order in which the

Q:Question:3. Consider the following graph Show how depth-first search works on the above graph. Assume that the for loop of lines 5-7 of the DFS procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification

Q:Question:Consider a state space with branching factor 10 . If a depth-first search to depth limited to 5 levels takes one minute to complete, approximately how long will depth-first search to depth limited to 6 levels take to complete? 1.2 minutes 6 minutes 10 minutes 60 minutesA:Answer:Hi dear Ans is 10 Because- The run time of BFS is ...

Q:Question:Given the following graph, starting vertex A, use the depth-first search algorithm to obtain a depth-first search numbering of the vertices. If there is a choice of vertices, choose the vertex that appears first in alphabetical order.

Q:Question:Node 1 is the root. Node 20 is the goal. Path costs are showed in the above binary tree. Find the path from 1 to 20 with the following: 1. Breath-first search 2. Uniform-cost search 3. Depth-first search 4. Depth-limit search 5. Iterative deepening depth-first searchA:Answer:Considering that Node 1 is the ROOT NODE and Node ...

Q:Question:the Employee class from problem 1 and answer questions below. Only submit the main function for this problem. i. Create an Employee object using the constructor with parameter. Ii. Declare an Employee pointer and make it point to the Employee object created in part (i). ili. Use the pointer to call the print() method of the object. iv.

Q:Question:problem. Your code will be tested. 1. Create an Employee object using the constructor with parameter. 2. Declare an Employee pointer and make it point to the Employee object you created in the previous part. 3. Use the pointer to call the print() method of the object. 4. Dynamically create an Employee object and make the pointer point

Q:Question:Create an Employee object using the constructor with parameters. [2pts] Declare an Employee pointer and make it point to the Employee object created in part (i). [2pts] Use the pointer in (ii) to call the print() funcion of the object. [2pts] Dynamically create an Employee object using the constructor with parameters and make the

Q:Question:Individual exercise* Consider the following graph: 1. Perform a breadth-first search (BFS) traversal on the graph. Use vertex 0 as the root node. 2. Perform a breadth-first search (BFS) traversal on the graph. Use vertex 7 as the root node.A:Answer:In Breadth First Search, all the neighbors of a cu...

Q:Question:Write a three-page paper to discuss the applications of Stack and Queue using your own words.A:Answer:Stack: It is linear data structure. It follows the...

Q:Question:Complete the tables below to articulate the given operations on the Stack and Queue ADTs Operation Stack Queue Adding an item Removing an item Number of elements Looking at the top element Checking for an empty structureA:Answer:See a step by step answer

Q:Question:two parameters: an array-based unbounded queue of integers as its first parameter and an array-based bounded stack of integers as its second parameter. The method should find the largest odd integers from all corresponding values in the stack and queue and save them into an object of type ArrayUnsortedList and return this object from

Q:Question:Write a main function to Reverse the elements of queue "queueA" only using stack and queue operations. Assume all stack and queue methods are provided. The queue must be unchanged. You MUST use ONLY STACK and QUEUE member functions.A:Answer:Answer: 3) Here is the Complete Program that is in...

Q:Question:1. Swap two adjacent list elements by adjusting only the links (and not the data) using a. Singly linked lists b. Doubly linked lists Show this by using the lists given. There is no coding involved. You must describe in detail, using pseudo code, the steps to swap the adjacent elements.

Q:Question:Explain with examples linked lists and arrays with their advantages and disadvantages. When do you favor one over another?A:Answer:See a step by step answer

Q:Question:write an algorithm that appends two link lists togetherA:Answer:SourcrCode in C++ : /* Java program to merge two s...

Q:Question:Write a main function to Reverse the elements of queue "queueA" only using stack and queue operations. Assume all stack and queue methods are provided. The queue must be unchanged. You MUST use ONLY STACK and QUEUE member functions.A:Answer:3. Program #include #include us...

Q:Question:C++ question: Swap two adjacent list elements by adjusting only the links (and not the data) using a. Singly linked lists b. Doubly linked lists Show this by using the lists given. There is no coding involved. You must describe in detail, using pseudo code, the steps to swap the adjacent elements.A:Answer:Answer: (a) // head points to

Q:Question:2.) Traverse the graph by breadth-first search and construct the corresponding breadth-first search tree. Start the traversal at vertex a and resolve ties by the vertex alphabetical order. * make sure to show how the queue changesA:Answer:Source Vertex = a. So now in the queue the adjacen...

Q:Question:Please Explain how to merge two sorted linked lists? Write an algorithm to merge two sorted linked lists? Input: Head of following linked lists 1->2->3->4->NULL 1->2->5->6->7->8->NULL Output: Linked lists should be merged to, 1->2->3->4->5->6->7->8->NULLA:Answer:An algorithm is a step-by-step procedure that give...

Q:Question:I. Huffman Code ( 20 points) What is an optimal Huffman code for the following set of frequencies of characters?

Q:Question:What are the differences between Huffman coding and Adaptive Huffman coding ?A:Answer:Differences between Huffman Coding and Adaptive Hu...

Q:Question:1. A file contains the following characters with the frequencies as shown in the table. If Huffman coding is used for data compression, determine- i. Huffman code for each character ii. Average code word length iii. Length of Huffman encoded message (in bits)A:Answer:See a step by step answer

Q:Question:I. Huffman Code (20 points) What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers? (15 points) a: 1 b: 1 c: 2 d: 3 e:: f:: b: 13 h: 21 Generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers. (5 points)A:Answer:See a step by step answer

Q:Question:? Solve an Exercise ? mergeSort4 0 Language/Type: ? Java merge sort sorting Related Links: Wikipedia: merge sort Trace the complete execution of the merge sort algorithm when called on the array below, similarly to the example trace of merge sort shown in the lecture slides. Show the sub-arrays that are created by the algorithm and show

Q:Question:Problem ???? ? 3 Use the merge sort algorithm to sort the list L=[3,2,5,6,7,1,4]. /r/n Problem ???? 3 Use the merge sort algorithm to sort the list L=[3,2,5,6,7,1,4].

Q:Question:Problem 4 [20 Points]: For the following set of letters and weights: (1) [4 Points]: Build the Huffman coding tree; (2) [4 Points]: Determine the Huffman codes; (3) [4 Points]: What is the expected length in bits of a message containing \( n \) characters for this frequency distribution? (4) [4 points] If a Huffman coding table is given

Q:Question:3. (25 points) Show the intermediate results of each pass of the following sorting algorithms on the initial list of numbers: \( 120,205,348,6,37,295,16,41,430 \). (a) Quick sort with median-of-three method to choose the pivot. (b) Recursive merge sort (c) Natural merge sort (d) Heap sort using max heap (e) Radix sortA:Answer:See a step

Q:Question:a) A file contains the following characters as shown below. If Huffman Coding is used for data compression, AASSOAI?EEEASSAAESSEESEEIIYSIEEEIUISSPIIAAIIOOEEYYUSSEUEEST Determine the following, 1) Obiain the Huflman's tree for the etaracters [4 Kiarks] ii) Huffman Code for each character [4 Marks] iii) Average code length [3 Marks] iv)

Q:Question:entropy of the source. 2. What is the minimum required average code word length to represent this source for error-free reconstruction? 3. Design a Huffman code for the source and compare the average length of the Huffman code with the entropy of the source. 4. Design a Huffman code for the second extension of the source (take two

Q:Question:3. (20\%) Sort the following array using the merge sort technique (Show both divide and Merge steps)A:Answer:See a step by step answer

Q:Question:huffman coding Construct the Huffman tree for the following letters and frequencies, then find the Huffman codes for these letters. Letter = A B C D E F G Frequency = 45621324556

Q:Question:entropy of the source. 2. What is the minimum required average code word length to represent this source for error-free reconstruction? 3. Design a Huffman code for the source and compare the average length of the Huffman code with the entropy of the source. 4. Design a Huffman code for the second extension of the source (take two

Q:Question:Please try to solve "(b)" of the following question In a rod cutting problem, given a table of prices p_i, you are required to determine the maximum revenue r_n obtainable by cutting up a given rod of length n and selling the pieces. The following is a price matrix in one such situation. a) How can brute force approach be used to solve

Q:Question:module. You have learned merge sort in data structures which sorts an array in nlogn time, it is a divide and conquer technique. We can enhance the performance of merge sort using the multithreading. First of all, you have to check the processor cores of your system, let??s suppose your system processor has 4 cores. Now you have to

Q:Question:Using the Huffman coding algorithm the below tree is produced. List the Huffman coding for \( b, c, d, e \) and \( f \) (10 poir

Q:Question:3. (Chapter 2) Suppose we are comparing the implementations of insertion sort and merge sort on the same machine (You don't need to know the algorithm to do this problem!). For inputs of size n, insertion sort runs in 8 n^? 2, while merge sort runs in 64 n ngn steps. For which values of ???? does insertion sort beat merge

Q:Question:1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8 n^2 steps, while merge sort runs in 64 n n steps. For which values of n does insertion sort beat merge sort?A:Answer:See a step by step answer

Q:Question:correct output Dynamic Programming: Rod Cutting Description In this assignment you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem (chapter 15.1). In the Rod Cutting problem, you are given an integer n ? 1, along with a sequence of positive prices, p_1, p_2, ?, p_n, where p_i is the market price of a

Q:Question:Suppose the numbers \( 7,12,3,6,21,56,2,15,9,5 \) are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. i. Draw the binary search tree after all nodes are inserted. ii. Derive preorder, postorder and inorder sequences.A:Answer:See a step by step answer

Q:Question:^i(2^i+2^j)^2 (i) ?_i=0^n?_j=0^i(2^j+i)^2 (I) ?_i=1^n?_j=1^nln (i j)Problem 8.27. Define size and height (see Exercise 8.10) for rooted ternery trees (R T T) and rooted trees (R T). (a) Prove: For any rooted ternary tree (RTT) T, size (T) ?(3^height (T)+1-1) / 3. Find such a bound for the size of a rooted tree (RT) in terms of its

Q:Question:In which order are the vertices of the ordered rooted tree shown below visited using an preorder traversal? badcfeg abcdefg bdfgeca bfgdeca abdfgec bafdgce abcdfgeA:Answer:See a step by step answer

Q:Question:The purpose of traversal algorithms of rooted tree is toA:Answer:Ans:- Definition A tree traversal algorithm is a m...

Q:Question:2.5. In which order are the vertices of the ????_1 rooted tree (root =P ) visited using a preorder and a postorder traversal? In which order are the vertices of the ????_2 rooted tree ( root =A) visited using a inorder traversal? Note: Please ignore the arrows that appear in the tree T_1.

Q:Question:Consider the rooted tree T. Name the descendants of M.

Q:Question:4. Draw the rooted tree with the code 00011001000011101111 .

Q:Question:9. (4points Define: i). rooted tree ii). simple graphA:Answer:A rooted tree is a tree in which one vertex has be...

Q:Question:How many nonisomorphic rooted trees are there with six vertices.A:Answer:The number of nonisomorphic trees of order , 2, .....

Q:Question:What is the postfix notation to the following prefix expression: -*33*42 Draw the ordered rooted tree to the following postfix expression: 521- -314++*A:Answer:See a step by step answer

Q:Question:(1) (8 points) Draw all the nonisomorphic rooted trees with four vertices (using isomorphism for directed graphs). Root your trees at the top.A:Answer:See a step by step answer

Q:Question:sketch the unlabeled rooted tree with planar code: 1011011001001100

Q:Question:2. Consider the rooted tree of Fig. (a). Draw a figure showing its representation in the ??first-child/next-sibling? form. Consider the rooted tree of Fig. 1(b) represented in the ??first-child/nextsibling? form. Draw a figure showing the equivalent rooted tree. (9) HE H HEELHETHE TEET ETT root

Q:Question:10 Determine the order of pre-order, in-order and post-order of the given rooted tree in QuestionA:Answer:See a step by step answer

Q:Question:A- [2 POINTS] Iteration method, then express the result in asymptotic notation \( \Theta \). \[ T(n)=n+4 T(n / 4) \]A:Answer:See a step by step answer

Q:Question:problem. Create an Employee object using the constructor with parameters. [2pts] Declare an Employee pointer and make it point to the Employee object created in part (i). [2pts] Use the pointer to call the print() method of the object. [2pts] Dynamically create an Employee object using the constructor with parameters and make the

Q:Question:1(20) Given the input {53,32,23,22,72,82}, and a hash function h(X)=X 10, show the resulting: a). Separate chaining hash table. b). Open addressing hash table using linear probing c). Open addressing hash table using quadratic probing d). Open addressing hash table with second hash function h_2(x)=7-(x 7) a) b) c)A:Answer:See a step by

Q:Question:Dynamic Programming: Rod Cutting Description In this assignment you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem (chapter 15.1). In the Rod Cutting problem, you are given an integer n ? 1, along with a sequence of positive prices, p_1, p_2, ?, p_n, where p_i is the market price of a rod of length i.

Q:Question:0a) Describe a dynamic programming algorithm for the rod cutting problem. b) Simulate the algorithm of part a for the prices data of < 2 4 8 9 11 13 >. Organize your work in a table.A:Answer:a. Problem statement Given a rod of length n, and ...

Q:Question:resolution strategies. Clearly show calculations and indicate cases where a number cannot be inserted in the table. Separate chaining hash table Hash table using linear probing Hash table using quadratic probing Hash table with double hashing. Use the second hash functionA:Answer:See a step by step answer

Q:Question:71, 23, 73, 99, 44, 79, 89 in a hash table of size 10 using the hash function Show the hash tables after insertions using the following collision resolution strategies. Clearly show calculations and indicate cases where a number cannot be inserted in the table. Separate chaining hash table Hash table using linear probing Hash table

Q:Question:You won't need to use pseudo-codes or any kind of codes as well as you don't have to write any algorithms In a rod cutting problem, given a table of prices \( p_{i} \), the objective is to determine the maximum revenue \( r_{n} \) obtainable by cutting up the given rod (of length \( n \) ) and selling the pieces. The rod cutting problem

Q:Question:In a rod cutting problem, given a table of prices \( p_{i} \), the objective is to determine the maximum revenue \( r_{n} \) obtainable by cutting up the given rod (of length \( n \) ) and selling the pieces. The rod cutting problem exhibits optimal substructure property. The following table shows the price table for one particular

Q:Question:Describe the difference between stack and queue to non-technology person, including real-world example.

Q:Question:Given input { 4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h (x ) = x mod 10, show the resulting: a. Separate chaining hash table. b. Hash table using linear probing. c. Hash table using quadratic probing. d. Hash table with second hash function h2 (x ) = 7 ? (x mod 7). Also show the result of rehashing the hash tables

Q:Question:two parameters: an array-based unbounded queue of integers as its first parameter and an array-based bounded stack of integers as its second parameter. The method should find the smallest even integers from all corresponding values in the stack and queue and save them into an object of type ArrayUnsortedList and return this object from

Q:Question:slightly different from what others have posted.** Given input 4371, 1323, 6173, 4199, 4344, 9679 and 1986 and a has function h(x)= x mod 10, show the results for: Separate chaining hash table Hash table using linear probing Hash table using quadratic probing Hash table with second function h2(x)=7?(x mod 7)A:Answer:See a step by step

Q:Question:4199, 4344, 9679, 1989} and a hash function h(x) = x mod 10, show the resulting: a. Separate Chaining hash table (note: to make insertion easy to show, just add new element at the end of linked list) b. Hash Table using Linear Probing c. Hash table using Quadratic Probing d. Hash table using Double Hashing where second hash function is

Q:Question:2.1 You have learned about the similarities and dissimilarities of the Queue and Stack ADTs. Operation Stack Queue Adding an item Removing an item Number of elements Looking at the top element Checking for an empty structure Complete the tables below to articulate the given operations on the Stack and Queue ADTsA:Answer:See a step by

Q:Question:pls writing the two procedures using C++. Swap two adjacent elements by adjusting only the links (and not the data) using a. singly linked lists b. doubly linked listsA:Answer:#include #include #include

Q:Question:(C++) Swap two adjacent elements by adjusting only the links (and not the data) using: a. singly linked lists b. doubly linked listsA:Answer:a) void swap_SL(iterators &itr) { Node* c = itr.cu...

Q:Question:suppose S is a list of n bits, that is 0's and 1's. How long will it take to sort S stably with the bucket sort algorithm?A:Answer:See a step by step answer

Q:Question:Help with Parallel Merge Sort C++ using c++11 threads I need to explain the following: What is Parallel Merge Sort and how it differs from regular merge sort what is the recurrence relation of parallel merge sort proof the running time of parallel merge sort.A:Answer:PROGRAM: #include #include ...

Q:Question:3. (4pts) Design pseudo code generic enough so that it can answer order statistics for any kth largest element from an n-element array. For e.g. k=n / 2 gives the median and k=1 gives the max. (You may like to invoke some algorithms from lectures.)A:Answer:C++ CODE: #include using namespace...

Q:Question:Show how to sort n integers in the range 0 to n^3-1 in O(n) time. Explain why the worst-case running time for bucket sort is ?(n^2). What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O( nlogn ).

Q:Question:1Explain why the worst-case running time for bucket sort is ?(n^2 ) 2What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O(n lg n)? *** Im am having trouble w the second partA:Answer:SOLUTION- In this we can replace Insertion Sort by...

Q:Question:2. Draw all non-isomorphic unordered rooted trees with exactly five vertices.A:Answer:See a step by step answer

Q:Question:The rooted Fibonacci trees Tn are defined recursively in the following way. T1 and T2 are both the rooted trees consisting of a single vertex, and for n = 3, 4, ..., the rooted tree Tn is constructed from a root with Tn-1 as its left subtree and Tn-2 as its right subtree. 1. How many vertices, leaves, and internal vertices does the

Q:Question:(In C++) Swap two adjacent elements by adjusting only the links (and not the data) using : a. singly linked lists b. doubly linked listsA:Answer:a) Singly Linked List /* A linked list node */ str...

Q:Question:the task of sorting n=1000,32 bit binary keys. You have decided to use radix sort (which uses counting sort as a stable sorting algorithm subroutine) for this problem but you are unsure whether to use counting sort on each bit separately or whether to use counting sort on groups of bits to minimize the total running time. You want to

Q:Question:the task of sorting n=1000,32 bit binary keys. You have decided to use radix sort (which uses counting sort as a stable sorting algorithm subroutine) for this problem but you are unsure whether to use counting sort on each bit separately or whether to use counting sort on groups of bits to minimize the total running time. You want to

Showing 100 - 200 of 335
  • 2 / 4