CMPT 706 Algorithms for Big Data Homework Assignment 2 (Algorithm代写,北美程序代写,加拿大程序代写,Simon Fraser University代写,CMPT706代写)

Algorithm代写 北美程序代写 加拿大程序代写 Simon Fraser University代写 CMPT706代写

In this question you need to check if N = 1729 is prime.

联系我们
微信: biyeprodaixie 欢迎联系咨询

本次CS代写的主要涉及如下领域: Algorithm代写,北美程序代写,加拿大程序代写,Simon Fraser University代写,CMPT706代写

CMPT 706 Algorithms for Big Data

HomeworkAssignment 2

Instructor:IgorShinkar Duedate:February10, 2020

Submityoursolutions,printedorwritteninreadablehandwriting,totheassignmentb oxesinCSIL.

Question 1 (20p oints) InthisquestionyouneedtocheckifN= 1729isprime.

(a) ConsidertheFermat'stestfortestingwhetherN= 1729isprime.Whatwil lthetestoutputfora= 9?

(b)ConsidertheMil ler-RabintestfortestingwhetherN= 1729isprime.Whatwil litoutputfora= 9?

(c)ConsidertheMil ler-RabintestfortestingwhetherN= 1729isprime.Whatwil litoutputfora= 25?

Is 1729 aprimenumber?

Question 2 (20p oints) ConsidertheMergeSortalgorithmwesawinclasswherethemergingisdonein
lineartimeusinganadditionalarray.

(a) Whatistheminimalnumberofcomparisonsthatthemergepartperformsonanytwosubarraysoflength n/ 2 each? (b)WhatistheminimalnumberofcomparisonsthattheMergeSortalgorithmperformsonanyarraysof length16?Showanexampleofanarrayachievingtheminimalnumberofcomparisons.

Question 3 (20p oints) ConsidertheMergeSortalgorithmwesawinclasswherethemergingisdonein
lineartimeusinganadditionalarray.

(a) Whatisthemaximalnumberofcomparisonsthatthemergepartperformsonanytwosubarraysoflength n/ 2 each?

(b)WhatisthemaximalnumberofcomparisonsthattheMergeSortalgorithmperformsonanyarraysof
length16?Showanexampleofanarrayachievingthemaximalnumberofcomparisons.

Question 4 (20p oints) SupposethatyourinputisanarrayAoflengthnsuchthateachentryinthe
arrayisanumberbetween 1 and100.DesignanalgorithmthatgivensuchanarraysortsitintimeO(n).

Question 5 (20p oints) Supposeyouarechoosingbetweenthefol lowingthreealgorithms:

1.AlgorithmAsolvesproblemsofsizenbydividingthemintofoursubproblemsofhalfthesize,recursively
solvingeachsubproblem,andthencombiningthesolutionsinlineartime.

2.AlgorithmBsolvesproblemsofsizenbyrecursivelysolvingtwosubproblemsofsizen− 1 ,andthen
combiningthesolutionsinconstanttime.

3.AlgorithmCsolvesproblemsofsizenbydividingthemintoeightsubproblemsofsizen/ 3 ,recursively
solvingeachsubproblem,andthencombiningthesolutionsinO(n^2 )time.

Usebig-Onotationtoexpresstherunningtimesofeachofthesesalgorithms. Whichofthemwouldyou
choose?

2-