Textbook Assignment 3

docx

School

New Jersey Institute Of Technology *

*We aren’t endorsed by this school

Course

610

Subject

Computer Science

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by MasterLemur1918

Textbook Assignment 3 R10.4 Character Frequency Space 7 o 7 t 5 s 3 p 2 d 2 h 1 r 1 g 1 n 1 c 1 a 1 Huffman Tree as below: R11.1 a) T(n) = 2T(n/2) + log n a = 2 , b = 2 , f(n) = log n Now we use master’s theorem to compare ? to f(n) 𝑙𝑜? ? ? Here ? > f(n) the master theorem 1 used which is 𝑙𝑜? ? ? T(n) = θ( ? ) = 𝑙𝑜? ? ? θ ( ? 𝑙𝑜? 2 2 ) = θ (?) b) T(n) = 8T(n/2) + ? 2 a = 8 , b = 2 , f(n) = ? 2 Now we use master’s theorem to compare ? to f(n) 𝑙𝑜? ? ? Here ? > f(n) the master theorem 1 used which is 𝑙𝑜? ? ? T(n) = θ( ? ) = = 𝑙𝑜? ? ? θ ( ? 𝑙𝑜? 2 8 ) θ (? 3 ) c) T(n) = 16T(n/2) + (? 𝑙𝑜? ?) 4 a = 16 , b = 2 , f(n) = (? 𝑙𝑜? ?) , p = 4 4 Now we use master’s theorem to compare ? to f(n) 𝑙𝑜? ? ?

If a = ? , p > 0 then theorem 2 used which is ? T(n) = θ( ? n) = ( n) = ( n) 𝑙𝑜? ? ? 𝑙𝑜? ?+1 θ ? 𝑙𝑜? 2 16 𝑙𝑜? 4+1 θ ? 4 𝑙𝑜? 5 d) T(n) = 7T(n/3) + n a = 7 , b = 3 , f(n) =n Now we use master’s theorem to compare ? to f(n) 𝑙𝑜? ? ? Here ? > f(n) the master theorem 1 used which is 𝑙𝑜? ? ? T(n) = θ( ? ) = ) 𝑙𝑜? ? ? θ( ? 𝑙𝑜? 3 7 e) T(n) = 9T(n/3) + ? 3 𝑙𝑜?? a = 9 , b = 3 , f(n) = ? , p =1 , k=3 3 𝑙𝑜?? If a < ? , p > 0 then theorem 3 used which is ? T(n) = θ ( ? n) = n) = log n) ? 𝑙𝑜? ? θ ( ? 3 𝑙𝑜? 1 θ ( ? 3 R11.3 Here X11 = 3 , X12 = 2 , X21 = 4 , X22 = 8 Y11 = 1 , Y12 = 5 , Y21 = 9 , Y22 = 6 P = [X11 + X22] * [Y11 + Y22] = 77 Q = Y11 [X21 + X22] = 12 R = X11 [Y12 - Y22] = -3 S = X22 [Y21 - Y11] = 64 T = Y22 [X11 + X12] = 30 U = [X21 - X11] * [Y11 + Y12] = 6 V = [Y21 + Y22] * [X12 - X22] = -90 XY11 = P + Q - T + V = 21 XY12 = R + T = 27 XY21 = Q + S = 76 XY22 = P + R - Q + U = 68 By using Strassen’s matrix multiplication algorithm, find the below matrix. R12.9 Here, Sally's optimization problem can be characterized as a knapsack problem. In the knapsack problem, we have a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. The goal is to determine which items to pack into the knapsack in order to maximize the total value, subject to the constraint that the total weight does not exceed the capacity of the knapsack. In Sally's problem, The widgets correspond to the items,

The number of widgets requested by each bidder corresponds to the weight of the item, The amount of dollars offered by each bidder corresponds to the value of the item. The total number of widgets available corresponds to the capacity of the knapsack. If we use Sally's fractional knapsack problem , she is allowed to allocate fractions of widgets to each bidder. This means that she can allocate a fraction of a widget to a bidder, and the bidder is willing to pay for the fractional amount of widgets accordingly. On the other hand, if Sally is only allowed to allocate integer numbers of widgets to each bidder, then her problem is a 0-1 knapsack problem. In this case, she can only allocate a whole number of widgets to each bidder, and cannot allocate fractional widgets. R13.6 a) Graph b) Starting at vertex 1, a DFS traversal would visit the vertices in the following order: 1 , 2 , 3 , 4 , 6 , 7 , 8 , 5 c) Starting at vertex 1, a BFS traversal would visit the vertices in the following order: 1 , 2 , 3 , 4 , 6 , 5 , 7 , 8 R13.7 a) In this case, an adjacency list structure would be more appropriate since it only stores information about edges that exist, and not about edges that do not exist. With 20,000 edges, the adjacency list would only require about 160,000 bytes of memory, which is significantly less than the 100,000,000 bytes required for the adjacency matrix. b) In this case, an adjacency matrix structure would be more appropriate since it can handle dense graphs with many edges more efficiently than an adjacency list. An adjacency matrix requires memory proportional to the square of the number of vertices, which is much less than that would be required for the adjacency list. c) An adjacency matrix would be more appropriate in this case since it allows for constant-time access to any element in the matrix, whereas an adjacency list would require searching through a linked list for each vertex to determine if a given edge exists. R14.3 function dijkstra_tree(Graph G, Vertex source): dist[source] ← 0 for each Vertex v in G: if v ≠ source: dist[v] ← infinity parent[v] ← nil Q ← priority queue containing all vertices in G, using dist[] as key while Q is not empty: u ← vertex in Q with smallest dist[] remove u from Q

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

for each neighbor v of u: alt ← dist[u] + weight(u, v) if alt < dist[v]: dist[v] ← alt parent[v] ← u if v is in Q: decrease-key v in Q to dist[v] else: insert v into Q with priority dist[v] return parent[]

Related Documents

Screenshot 5.8.2 2.png

assignment3_MECHTRON_3X03.pdf

HomeWork1_ML_Assignment.pdf

McCurley-Shimer_Assignment #4.docx

MSIT 3150 - Quiz 5.docx

MSIT 3150-Assignment 3 .docx

McCurley-Shimer_Assignment #2.docx

Lab 5 - Stego.docx

McCurley-Shimer_Assignment #3.docx

McCurley-Shimer_Assignment #1.docx

McCurley-Shimer_Assignment #6.docx

Recommended textbooks for you

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

SEE MORE TEXTBOOKS

Recommended textbooks for you

Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage