Loading...

Messages

Proposals

Stuck in your homework and missing deadline? Get urgent help in $10/Page with 24 hours deadline

Get Urgent Writing Help In Your Essays, Assignments, Homeworks, Dissertation, Thesis Or Coursework & Achieve A+ Grades.

Privacy Guaranteed - 100% Plagiarism Free Writing - Free Turnitin Report - Professional And Experienced Writers - 24/7 Online Support

Write pseudocode for strassen's algorithm

25/11/2021 Client: muhammad11 Deadline: 2 Day

ICSI403 Design and Analysis of Algorithms Student Name: _______________ Total converted points: /100 Total points: /155 Homework 1 Created by Qi Wang Instructions:

1. In this homework, you will practice the topics that are discussed in module I. You should study the relevant

materials before completing the homework.

2. All work is individual unless it is notified otherwise.

3. While working on the problems, you must show/explain your work for all problems to receive credit. Simply

stating the answers will result in 0 points awarded.

4. Writing is how knowledge can be retained. Here are the suggestions on how to complete the work:

1) You may print the work, complete it, and scan it with Microsoft Office Lens into a PDF file.

2) You may write with a stylus pen and save your work as a PDF file.

3) You may write on your own paper, and scan it with Microsoft Office Lens into a PDF file. If so, you must

clearly mark each question and write the solutions in order.

When scanning, you must adjust it so that it is not too dark or too bright or blurry to read. Any unreadable work

may be rejected with no credit. No matter how you complete it, you must submit the work with all pages or

solutions included in ONE PDF file on Blackboard. Absolutely NO hard copies or e-mail submissions or late work

will be accepted.

5. Two attempts will be allowed on Blackboard. Only the last attempt will be graded.

6. Work will be rejected with no credit if

a. The work is late.

b. The work is not submitted properly (Blurry, wrong files, not in required format, etc.). For example,

i. Multiple files (image files or PDF files) are submitted.

ii. The submitted PDF file can’t be opened.

iii. The submitted PDF file is too dark or bright or blurry to read.

iv. The submitted work is empty or wrong work.

v. Other issues.

c. The work is a copy or partial copy of others' work (such as work from another person or the Internet).

2

7. The points in each question are for grading only. The converted points rounded to the ones place will be

recorded for this work.

8. Your TA will grade, and then post the feedback and the grade for this homework on Blackboard if you have

submitted it properly and on time. If you have any questions regarding the feedback or the grade, please

reach out to the TA first. You may also contact the instructor for this matter.

3

1. Use the following as a model,

illustrate the operation of INSERTION-SORT on the array A = {31, 41,59, 26, 41,58}. Rewrite the INSERTION-SORT

procedure to sort into nonincreasing instead of nondecreasing order.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points each, 20

points in total.)

4

5

2. Binary Addition of Integers: Given two integers a and b, their binary expansions are shown below.

To compute the sum of a and b in binary form, add the corresponding pairs of bits with carries when they occur.

• First add their rightmost bits. This gives

o s0 is the rightmost bit in the binary expansion of a + b and

o c0 is the carry.

• Then add the next pair of bits and the carry.

o s1 is the next bit (from the right) in the binary expansion of a + b, and

o c1 is the carry.

• Continue this process, adding the corresponding bits in the two binary expansions and the carry, to

determine the next bit from the right in the binary expansion of a + b.

• At the last stage,

an−1 + bn−1 + cn−2 = cn−1 ・ 2 + sn−1

The leading bit of the sum is sn = cn−1. This procedure produces the binary expansion of the sum,

Write pseudocode for adding two integers in binary expansions formally. Store the two binary integers and

their sum in arrays. Illustrate your algorithm using this following two integers: a = (1110)2 and b = (1011)2.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points)

6

7

3. Express the following functions in terms of Θ- notation.

(n2 + 8)(n + 1) , (n log n + n2)(n3 + 2), and (n! + 2n)(n3 + log(n2 + 1)

You must show/explain how you arrived at the answers. Simply stating the answers will result in 0 points

awarded. (5 points each, 15 points in total.)

a. (n2 + 8)(n + 1)

b. (n log n + n2)(n3 + 2)

c. (n! + 2n)(n3 + log(n2 + 1))

8

9

4. We often use a loop invariant to prove that an algorithm gives the correct answer. To use a loop invariant to

prove correctness, we must show three things about it:

1) Initialization: It is true prior to the first iteration of the loop.

2) Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.

3) Termination: When the loop terminates, the invariant (usually along with the reason that the loop

terminated) gives us a useful property that helps show that the algorithm is correct.

Let’s take a look at the following Bubble sort algorithm.

1) Bubble sort is a sorting algorithm that works by repeatedly exchanging adjacent elements that are out of

order. Let A’ denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to

prove that it terminates and that A’[1] ≤ A’[2] ≤ … ≤ A’[n], where n = A.length. In order to show that

BUBBLESORT actually sorts, what else do we need to prove?

2) State precisely a loop invariant for the for loop inner, and prove that this loop invariant holds using the

above-mentioned structure of the loop invariant.

3) Using the termination condition of the loop invariant proved in part 2), state a loop invariant for the for

loop outer that will allow you to prove A’[1] ≤ A’[2] ≤ … ≤ A’[n], where n = A.length. Prove that this

loop invariant holds using the above-mentioned structure of the loop invariant.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (5 points

for #2), 5 points for each of the three parts (Initialization, Maintenance, and Termination) in #3). 20

points in total.)

outer: inner :

10

11

12

13

5. Suppose that a list contains integers that are in order of largest to smallest and an integer can appear repeatedly

in this list.

1) Devise an algorithm that locates all occurrences of an integer x in the list.

2) Estimate the number of comparisons used.

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points each, 20

points in total.)

14

15

6. Prove that n3 – 91n2 – 7n – 14 = 𝛺𝛺(n3). You must show/explain how you arrived at the constants, and clearly

specify the positive constants c and n0. Simply stating the answers will result in 0 points awarded. (10 points)

16

7. Prove that 27n2 + 18n = 𝛩𝛩(0.5n2 – 100). You must show/explain how you arrived at the constants, and clearly

specify the positive constants c1, c2, and n0. Simply stating the answers will result in 0 points awarded. (10 points)

17

8. Write pseudocode for Strassen’s algorithm and use Strassen’s algorithm to compute the matrix product of AB. You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points)

A = �2 1 3 2

�, B = �0 4 1 3

�.

18

19

9. (Substitution method) Show that the solution of T(n) = T(n – 1) + n is O(n2). You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points)

20

21

22

10. Use a recursion tree to determine a good asymptotic upper bound on the following recurrence. T(n) = 4T(n/2 + 2) + n Use the substitute method to verify your answer. You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points)

23

24

11. Use the master method to give tight asymptotic bounds for the following recurrences. 1) T(n) = 2T(n/4) + 1 2) T(n) = 2T(n/4) + √𝑛𝑛

You must show/explain your work. Simply stating the answers will result in 0 points awarded. (10 points each, 20 points in total.)

Homework is Completed By:

Writer Writer Name Amount Client Comments & Rating
Instant Homework Helper

ONLINE

Instant Homework Helper

$36

She helped me in last minute in a very reasonable price. She is a lifesaver, I got A+ grade in my homework, I will surely hire her again for my next assignments, Thumbs Up!

Order & Get This Solution Within 3 Hours in $25/Page

Custom Original Solution And Get A+ Grades

  • 100% Plagiarism Free
  • Proper APA/MLA/Harvard Referencing
  • Delivery in 3 Hours After Placing Order
  • Free Turnitin Report
  • Unlimited Revisions
  • Privacy Guaranteed

Order & Get This Solution Within 6 Hours in $20/Page

Custom Original Solution And Get A+ Grades

  • 100% Plagiarism Free
  • Proper APA/MLA/Harvard Referencing
  • Delivery in 6 Hours After Placing Order
  • Free Turnitin Report
  • Unlimited Revisions
  • Privacy Guaranteed

Order & Get This Solution Within 12 Hours in $15/Page

Custom Original Solution And Get A+ Grades

  • 100% Plagiarism Free
  • Proper APA/MLA/Harvard Referencing
  • Delivery in 12 Hours After Placing Order
  • Free Turnitin Report
  • Unlimited Revisions
  • Privacy Guaranteed

6 writers have sent their proposals to do this homework:

Quality Assignments
Engineering Help
Unique Academic Solutions
Quality Homework Helper
Accounting & Finance Mentor
Finance Homework Help
Writer Writer Name Offer Chat
Quality Assignments

ONLINE

Quality Assignments

I have done dissertations, thesis, reports related to these topics, and I cover all the CHAPTERS accordingly and provide proper updates on the project.

$24 Chat With Writer
Engineering Help

ONLINE

Engineering Help

Being a Ph.D. in the Business field, I have been doing academic writing for the past 7 years and have a good command over writing research papers, essay, dissertations and all kinds of academic writing and proofreading.

$39 Chat With Writer
Unique Academic Solutions

ONLINE

Unique Academic Solutions

I have done dissertations, thesis, reports related to these topics, and I cover all the CHAPTERS accordingly and provide proper updates on the project.

$22 Chat With Writer
Quality Homework Helper

ONLINE

Quality Homework Helper

Being a Ph.D. in the Business field, I have been doing academic writing for the past 7 years and have a good command over writing research papers, essay, dissertations and all kinds of academic writing and proofreading.

$15 Chat With Writer
Accounting & Finance Mentor

ONLINE

Accounting & Finance Mentor

As an experienced writer, I have extensive experience in business writing, report writing, business profile writing, writing business reports and business plans for my clients.

$17 Chat With Writer
Finance Homework Help

ONLINE

Finance Homework Help

I have read your project details and I can provide you QUALITY WORK within your given timeline and budget.

$15 Chat With Writer

Let our expert academic writers to help you in achieving a+ grades in your homework, assignment, quiz or exam.

Similar Homework Questions

Article describing a new product in development - Magacyada allah 99 qoraal - Operating revenue per adjusted discharge - For don m banned line by line analysis - 40897 laredo trail cherry valley ca - Tata starbucks case study analysis - Best practices in healthcare facilities capital planning - Marketing data analysis - Complete combustion chemical equation - How to do cash flows on financial calculator - Community Policing and Crime Reduction - PHILOSOPHY - I need guest post on your site - Game show network cox - Portfolio - Nottingham human computer interaction - Quantum ahima org 8080 topaz main - Marie curie jobs cornwall - Apollo shoes case study solution - Leddy and pepper's professional nursing pdf - Mind mapping lecture notes - Computer Information Systems Project 1 - What do colors mean in wireshark - Nh3 h3po4 balanced equation - Ionic formula for potassium chloride - Discussion - Soc 120 week 2 assignment waste reduction - Food inc discussion guide answers - Ciliospinal centre of budge - Webcast bkwsu eu uk - Why do you want to study at IBS and what are your career goals? - Social work skills for process recordings - Ib psychology essay questions - Cell division mitosis and meiosis lab answers - Bantian huawei base longgang district shenzhen 518129 china - People are often unreasonable illogical and self centered - A night in june by william wordsworth summary - Emotional intelligence in labor and delivery case study - 5590 serenity terrace pleasanton ca - Endocrinology - The grass arena dvd - Why did mrs danvers burn down manderley - Victor victoria nonverbal cues - The power of effective questioning - + 91^*^9414601882 bEst vAshikArAn ExPErt IN HYDERABAD - Homework business law - Advanced pathophysiology - Wk 4, IOP/470: DR 2 - Merlin gerin multi 9 - DISCUSSION RESPONSE(NUR630) - Risks in cloud computing - Monsters and the moral imagination - The following are audit procedures from different transaction cycles - Marist college ashgrove sony camp - 747-8 max takeoff weight - Gypsum house construction cost - Downpatrick to belfast bus - Search ebscohost ezproxy montclair 2048 - Sodium bicarbonate and hydrochloric acid chemical change - Number of lululemon stores 2017 - Bsbpmg522a undertake project work answers - Javafx tetris - Uts autumn 2021 results - Discussion on e-bussiness - Poli 142k ucsd - Vision max cinema formerly cinema 95 - Dynamic processes support operational activities - Bcat short form scoring - Maria teresa matus y demis reyes - Door in the face persuasion - Hamworthy park junior school - Go to the website: https://epic.org/privacy/litigation/ which focuses on civil rights issues and privacy. Pick a case. - Erik erikson psychosocial theory - Duty of care definition child care - Assessing Clients With Addictive Disorders - Glasses for cone dystrophy - Accurate 2520 load data - 3 phase reversing drum switch wiring diagram - Cos-fors-week-2 - Global marketing pearson 9th edition pdf - Soft edge rectangle picture style powerpoint - Dr phoon chiu yong - Discussion - Dyna s wiring diagram - Job description of community health nurse ppt - How old is paolo nutini - Stimulus generalisation operant conditioning - Captains of industry or robber barons document based questions - Time management powerpoint slides - The economic entity assumption states that economic events - Uq activate internet session - Asme section viii division 2 - Lululemon athletica inc case study - If the radius of platinum is 0.139 nm, what is the pd of the (100) plane for platinum in m-2? - Star topology advantages and disadvantages ppt - 551 oceana drive howrah - 10gbase t auto negotiation - Disucssion - Tim hortons management structure - Hamlet win win dingbat