Summary
Summary Algoritme en datastructuren Samenvating + Oefentoets
- Course
- Institution
- Book
Samenvatting van de hoorcollege slides met aanvullingen uit het boek, inclusief oefententamen met uitwerking
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
Polymorphism in java
1 review
By: bb5 • 1 year ago
Seller
Followmarnickscholten
Reviews received
Content preview
Hanzehogeschool GroningenAlgoritme 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller marnickscholten. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.77. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67866 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now