100% tevredenheidsgarantie Direct beschikbaar na betaling Zowel online als in PDF Je zit nergens aan vast
logo-home
Computational Thinking Assignment 3 €5,49   In winkelwagen

Case uitwerking

Computational Thinking Assignment 3

 7 keer bekeken  0 keer verkocht

Computational Thinking Assignment 3

Voorbeeld 2 van de 8  pagina's

  • 14 juni 2022
  • 8
  • 2019/2020
  • Case uitwerking
  • Bhulai
  • 9-10
Alle documenten voor dit vak (7)
avatar-seller
TR19
Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)


1. Comparison of keys


Keys 4 13 25 33 38 41 55 71 73 84 86 92 97
Index 0 1 2 3 4 5 6 7 8 9 10 11 12


We need to use binary search: worst case performance, because that will lead to the largest
possible number of key comparisons. In this list, we have 13 indices, because we need to start
counting the keys from k = 0. The formula we need to use is ⎡ log2(n + 1) ⎤.


⎡ log2(n + 1) ⎤ = log2 (13 + 1) = 3.80735492206 ≈ 4

Conclusion: when you look up a key with binary search, the largest possible number of key
comparisons in this list is 4.

2. Estimating performance
A.
Binary search
Average case of successful search: ~ log2 (n)
Average case of successful search in a sorted array of 100,000 elements:
~log2 (100,000) = 16.609640474436812 ≈ 16.6

Sequential/linear search
Average case of successful search: (n + 1) / 2
Average case of successful search in a sorted array of 100,000 elements:
(100,000 + 1) / 2 = 50000.5
As you can see the 1 in (n + 1) / 2 is neglectable, because it’s a really small number compared to
100,000. You will get: (100,000) / 2 = 50000.

An average successful search by binary search is .6 ≈ 3010 times faster than an
average successful search by sequential search.

B.
We have a sorted array of 100,000 elements. To draw a single graph for both
linear (= sequential) and binary search, we need to use the “Big O” notation. The big O notation is
used to classify algorithms. It is a function characterization according to rates of growth and it is
useful for analysing efficiency. In this case, we consider worst cases. The worst cases for the
binary and linear search algorithms are:
- Binary = O(log(n))
- Linear = O(n)

I drew a
single graph
in Python as
follows:

, Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)


This is the result I got, after I clicked “run”.




We can see that the number of operations (for 100,000 elements) with the binary search
algorithm, is a lot less than with linear search, if you consider worst case scenario’s. In this case, if
you want to find a key, it is better and way faster to use the binary search algorithm.


3. Binary search in flowchart

This in my flowchart for binary search, made in excel.

Voordelen van het kopen van samenvattingen bij Stuvia op een rij:

Verzekerd van kwaliteit door reviews

Verzekerd van kwaliteit door reviews

Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!

Snel en makkelijk kopen

Snel en makkelijk kopen

Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.

Focus op de essentie

Focus op de essentie

Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper TR19. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 62491 samenvattingen verkocht

Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen

Start met verkopen
€5,49
  • (0)
  Kopen