- Questions & Answers
- Accounting
- Computer Science
- Automata or Computationing
- Computer Architecture
- Computer Graphics and Multimedia Applications
- Computer Network Security
- Data Structures
- Database Management System
- Design and Analysis of Algorithms
- Information Technology
- Linux Environment
- Networking
- Operating System
- Software Engineering
- Big Data
- Android
- iOS
- Matlab

- Economics
- Engineering
- Finance
- Thesis
- Management
- Science/Math
- Statistics
- Writing
- Dissertations
- Essays
- Programming
- Healthcare
- Law

- Log in | Sign up

advance algorithm analysis

CP5602 Assignment SPXX, JCUB/S Due by XXXX, 202X (no later than 5:00pm) Aim: This assignment is designed to help you improve your critical thinking and problem solving skills. It also helps you to be prepared for the final examination (i.e., strongly recommended to do this assignment). Requirements, Method of Submission, and Marking Criteria: Include your name on the first page. Answer all questions in a single document. Each question should begin on a new page. Show all your work. Providing an answer without explanation in which how did you acheive it, is not acceptable. If you use pen-and-paper you may submit a scan of your worksheet. Upload your solution to the Assignment Box, located in the subject’s site. 1. Consider recurence T (n) = 2T (n/2) + n. (a) Use the recursion tree to give tight Big-Oh asymptotic bound for this recurence. [1 mark] (b) Use the substitution method to support your computed bound in item (a). [1 mark] 2. Use the master method to give tight asymptotic bounds for the following recurrences (if the master method cannot be applied give your argument): (a) T (n) = 8T (n/2) + n2. [1 mark] (b) T (n) = 4T (n/2) + n3 lg n. [1 mark] 3. Let A = 〈10, 6, 27, 21, 44, 16, 6, 32, 49〉 be an array associated with a complete binary tree (i.e. 10 is the root, with 6 as its left child and 27 as its right child, and so forth). (a) Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array. [1 mark] (b) Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the resulting heap of item (a). [1 mark] 1 4. Using Figure 7.1 as a model (i.e., choosing the last element as pivot), illustrate the operation of PARTITION (used in Quick-sort algorithm) on the array A〈13, 35, 9, 25, 12, 8, 37, 14, 33, 2, 16, 17〉. [1 mark] 5. Consider inserting the keys 31, 22, 32, 10, 25, 44, 14, 18, 9 into a hash table of length m = 11 using open addressing with the auxiliary hash function h′(k) = k. Illustrate the result of inserting these keys up to the point that algorithm fails. (a) using linear probing, [1 mark] (b) using quadratic probing with c1 = 1 and c2 = 3, and [1 mark] (c) using double hashing with h1(k) = k and h2(k) = 1 + (k mod (m− 1)). [1 mark] 6. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (7, 10, 5, 18, 20, 15, 10). That is: matrix dimension ———– ————— A1 7× 10 A2 10× 5 A3 5× 18 A4 18× 20 A5 20× 15 A6 15× 10 [2 marks] 7. Determine an LCS (Longest Common Subsequence) of sequences X = (A,L,G,O,R, I, T,H,M) and Y = (L,O,G,A,R, I, T,H,M). [2 marks] 8. What is an optimal Huffman code for the following set of frequencies? a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21, i:34. [1 marks] 9. Show the results of inserting the keys 18, 55, 50, 34, 8, 36, 23, 60, 67, 70, 40, 53, 42, 48, 2, 5, 73, 77, 12, 80, 16 in order into an empty B-tree with minimum degree 2. Draw only the configurations of the tree just before some node must split, and also draw the final configuration. [1 marks] 10. Consider a directed graph G in Figure 1. Using vertex p as the source, and assuming that all nodes are required to be discovered in alphabetic order; 2 Figure 1: Directed graph G. (a) Show the d and π values that result from running breadth-first search on graph G, [1 mark] (b) Show how depth-first search (DFS) works on the graph G. [1 mark] (d) Determine the strongly connected components of graph G (use DFS on the transpose graph of G). [1 mark] 11. Find all integers x that have remainders 1, 2, 3 when divided by 11, 12, 13 respectively. [1 mark] 3

CP5602 Assignment SPXX, JCUB/S Due by XXXX, 202X (no later than 5:00pm) Aim: This assignment is designed to help you improve your critical thinking and problem solving skills. It also helps you to be prepared for the final examination (i.e., strongly recommended to do this assignment). Requirements, Method of Submission, and Marking Criteria: Include your name on the first page. Answer all questions in a single document. Each question should begin on a new page. Show all your work. Providing an answer without explanation in which how did you acheive it, is not acceptable. If you use pen-and-paper you may submit a scan of your worksheet. Upload your solution to the Assignment Box, located in the subject’s site. 1. Consider recurence T (n) = 2T (n/2) + n. (a) Use the recursion tree to give tight Big-Oh asymptotic bound for this recurence. [1 mark] (b) Use the substitution method to support your computed bound in item (a). [1 mark] 2. Use the master method to give tight asymptotic bounds for the following recurrences (if the master method cannot be applied give your argument): (a) T (n) = 8T (n/2) + n2. [1 mark] (b) T (n) = 4T (n/2) + n3 lg n. [1 mark] 3. Let A = 〈10, 6, 27, 21, 44, 16, 6, 32, 49〉 be an array associated with a complete binary tree (i.e. 10 is the root, with 6 as its left child and 27 as its right child, and so forth). (a) Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array. [1 mark] (b) Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the resulting heap of item (a). [1 mark] 1 4. Using Figure 7.1 as a model (i.e., choosing the last element as pivot), illustrate the operation of PARTITION (used in Quick-sort algorithm) on the array A〈13, 35, 9, 25, 12, 8, 37, 14, 33, 2, 16, 17〉. [1 mark] 5. Consider inserting the keys 31, 22, 32, 10, 25, 44, 14, 18, 9 into a hash table of length m = 11 using open addressing with the auxiliary hash function h′(k) = k. Illustrate the result of inserting these keys up to the point that algorithm fails. (a) using linear probing, [1 mark] (b) using quadratic probing with c1 = 1 and c2 = 3, and [1 mark] (c) using double hashing with h1(k) = k and h2(k) = 1 + (k mod (m− 1)). [1 mark] 6. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (7, 10, 5, 18, 20, 15, 10). That is: matrix dimension ———– ————— A1 7× 10 A2 10× 5 A3 5× 18 A4 18× 20 A5 20× 15 A6 15× 10 [2 marks] 7. Determine an LCS (Longest Common Subsequence) of sequences X = (A,L,G,O,R, I, T,H,M) and Y = (L,O,G,A,R, I, T,H,M). [2 marks] 8. What is an optimal Huffman code for the following set of frequencies? a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21, i:34. [1 marks] 9. Show the results of inserting the keys 18, 55, 50, 34, 8, 36, 23, 60, 67, 70, 40, 53, 42, 48, 2, 5, 73, 77, 12, 80, 16 in order into an empty B-tree with minimum degree 2. Draw only the configurations of the tree just before some node must split, and also draw the final configuration. [1 marks] 10. Consider a directed graph G in Figure 1. Using vertex p as the source, and assuming that all nodes are required to be discovered in alphabetic order; 2 Figure 1: Directed graph G. (a) Show the d and π values that result from running breadth-first search on graph G, [1 mark] (b) Show how depth-first search (DFS) works on the graph G. [1 mark] (d) Determine the strongly connected components of graph G (use DFS on the transpose graph of G). [1 mark] 11. Find all integers x that have remainders 1, 2, 3 when divided by 11, 12, 13 respectively. [1 mark] 3

Sep 25, 2022

SOLUTION.PDF## Get Answer To This Question

- Using a Word document or drawing tool of your choice, provide answers to the following questions and diagram the results of the operations in Part 1. For Part 2 and Part 3, take screenshots of the...Dec 08, 2022
- Write a code to implement the heap sort algorithm in JAVA or Python. Test your program with different sets of data and take screenshots. Copy and paste your code and screenshots into a Word document....SolvedDec 05, 2022
- Algorithm 1: Bellman-Ford(G, c, t)/* graph G, edges costs c¢, destination ¢1 S « length-n array /* keeps track of first edge on path2 M + (n) x (n) array;/* set border cases3 M[0,] «0;4 S[t]...SolvedDec 02, 2022
- PROG8430 – Data Analysis, Modeling and Algorithms Assignment 5 Classification DUE BEFORE 10 pm, DECEMBER 9, 2022 1. Submission Guidelines All assignments must be submitted via the...Dec 02, 2022
- Each King or Queen is shown with his or her preferences, in order (top down). The objective of the assignment is to develop a solution based on the Gale-Shapley Algorithm.You will provide output...SolvedDec 01, 2022
- l;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtl;yjrydhtrhrdtNov 30, 2022
- Need to design a C++ program simulating a supermarket. 2 customers, 5 products each. Calculate the total amount due for each customer, according to the products they purchases. The products and their...Nov 30, 2022
- SAD assignment 1CI4305 COURSEWORK 1App Design Prototype Project (Part 1)Introduction2Your team3Evidence Of Your Team Engagement4Coursework 1 Requirements, Deadlines, Weighting...SolvedNov 29, 2022
- OverviewThe intent of this program is to give you experience writing classes and begin to start developing algorithms to solve problems.Learning ObjectivesBe able to write a class complete with...SolvedNov 28, 2022
- Yes i just need 10 graphs with commentsSolvedNov 26, 2022

Copy and Paste Your Assignment Here

Copyright © 2022. All rights reserved.