100% tevredenheidsgarantie Direct beschikbaar na betaling Zowel online als in PDF Je zit nergens aan vast
logo-home
Summary Algoritme en datastructuren Samenvating + Oefentoets €3,49
In winkelwagen

Samenvatting

Summary Algoritme en datastructuren Samenvating + Oefentoets

1 beoordeling
 192 keer bekeken  2 keer verkocht

Samenvatting van de hoorcollege slides met aanvullingen uit het boek, inclusief oefententamen met uitwerking

Laatste update van het document: 5 jaar geleden

Voorbeeld 4 van de 35  pagina's

  • Onbekend
  • 20 maart 2019
  • 21 maart 2019
  • 35
  • 2018/2019
  • Samenvatting
book image

Titel boek:

Auteur(s):

  • Uitgave:
  • ISBN:
  • Druk:
Alles voor dit studieboek (3)
Alle documenten voor dit vak (2)

1  beoordeling

review-writer-avatar

Door: bb5 • 1 jaar geleden

avatar-seller
marnickscholten
Hanzehogeschool Groningen



Algoritme en
datastructuren
Samenvatting




M. Scholten
11-3-2019

,Inhoud
Recursion ......................................................................................................................................................... 2
The big O notation........................................................................................................................................... 3
Sorting ............................................................................................................................................................. 7
Insertion sort ............................................................................................................................................... 7
Bubble sort .................................................................................................................................................. 8
Merge sort ................................................................................................................................................... 9
Quick sort .................................................................................................................................................. 10
Lists, Stacks & Queues ................................................................................................................................... 11
Lists ............................................................................................................................................................ 11
Stack .......................................................................................................................................................... 12
Queues ...................................................................................................................................................... 12
Binary Search Tree ........................................................................................................................................ 12
AVL Trees ....................................................................................................................................................... 13
Hashing .......................................................................................................................................................... 16
Set.............................................................................................................................................................. 16
Map ........................................................................................................................................................... 16
Hashing ...................................................................................................................................................... 17
Graphs ........................................................................................................................................................... 18
Basics ......................................................................................................................................................... 18
Graph Traversals........................................................................................................................................ 19
Backtracking .................................................................................................................................................. 20
Dynamic Programming .................................................................................................................................. 21
Dijkstra’s Algorithm ....................................................................................................................................... 22
A* Algorithm ................................................................................................................................................. 23
Prim’s Algorithm............................................................................................................................................ 24
Practice Exam ................................................................................................................................................ 25




1

,Recursion
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances
of the same problem. So, the tactic is to divide a problem into subproblems of the same type as the
original, solve all the subproblems and combine the results. Recursion is essentially repetition without a
loop.
All recursive methods have the following characteristics:
- One or more base cases are used to stop recursion (a base case is the simplest case)
- Every recursive call reduces the original problem, bringing it increasingly closer to a base case
until it becomes that case.
Let’s consider a simple problem of printing a message for n times. You can break the problem into two
subproblems: one is to print the message one time and the other is to print the message for n-1 times.
The second problem is the same as the original problem with a smaller size. The base case for the
problem is n==0. You can solve this problem using recursion as follows:
nPrintln(“Welcome”, 5);


public static void nPrintln(String message, int times) {
if (times >= 1) {
System.out.println(message);
nPrintln(message, times - 1);
} // The base case is times == 0
}
Recursion bears substantial overhead. Each time the program calls a method, the system must assign
space for all the method’s local variables and parameters. This can consume considerable memory and
requires extra time to manage the additional space.
Recursion is good for solving the problems that are inherently recursive




2

, The big O notation
Most algorithms transform input object into output object where the running time typically grows with
the input size. The average case time is difficult to determine, so we focus on the worst-case running
time. The worst-case running time is easier to analyze and is crucial to applications such as games, finance
and robotics
Experimental studies:
- Write a program implementing the algorithm
- Run the program with inputs of varying size and composition
- Use a method like System.currentTimeMillis() to get an accurate measure of the actual running
time
- Plot the results
Limitations of Experiments
- It is necessary to implement the algorithm, which may be difficult
- Results may not be indicative of the running time on other inputs which are not included in the
experiment
- To compare two algorithms, the same hardware and software environments must be used
Theoretical Analysis
- Uses a high-level description of the algorithm instead of an implementation (pseudo code)
- Characterizes running time as a function of the input size, n.
- Considers all possible inputs
- Allows us to evaluate the speed of an algorithm independent of the hardware/software
Pseudocode
- High-level description of an algorithm
- More structured than English prose, but less detailed than a program
- Preferred notation for describing algorithms
- Hides program design issues
- Example: find max element of an array:
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax  A[0]
for i  1 to n − 1 do
if A[i]  currentMax then
currentMax  A[i]
return currentMax




3

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 marnickscholten. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

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

Is Stuvia te vertrouwen?

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

Afgelopen 30 dagen zijn er 52510 samenvattingen verkocht

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

Start met verkopen
€3,49  2x  verkocht
  • (1)
In winkelwagen
Toegevoegd