Summary
Summary Data Structures & Algorithms
- Course
- Institution
Summary of everything you need to know for the DSA exam!
[Show more]
Seller
Follow
femkestokkink
Reviews received
Content preview
Data Structures and AlgorithmsInsertion Sort:
Input: sequence of n numbers
: Output: sorted permutation of the input
•
Efficient algorithm for sorting a small
number of elements
•
Algorithm sorts the input numbers in
place: it rearranges the numbers within
the array A, with at most a constant
number of them stored outside the array
at any time.
Best case performance: execute the while loop the least as possible. The array is already sorted
so the comparison test always fails. For the best case time complexity T(n) is in Θ(n)
Worst case performance: execute the while loop as many times as possible. The array is sorted
in a reversed way, so the comparison test always succeeds. T(n) = an + bn + c so T(n) is in Θ(n )
2 2
Insertion sort can be stable: the order of equal elements is respected. If the comparison would be
>= instead of > then it is not stable anymore.
Rate of growth:
Theta notation says something about the rate of growth, so we want this to be as low as
possible. To find Θ, we want to drop the lower order terms and we want to drop constants.
② asymptotic tight bound (=) 3M€ -042) 3N # ② (M) 3 € -04 )
0 asymptotic upper bound (<=) 3M€ 0cm) Îdoes not
3N C- OCN increase
r asymptotic lower bound (>=)
Useful properties big-O
na € Ocnb ) for AEB
109dm) E (nb) for alt a. b) 0
na 0lb ) for
"
c- an a> 0 ,
b > 1
for
109A ( n ) E
109ns (n ) alt a.
b > 0
IJ
,Merge sort
How do we sort?
Stop condition: if the sequence contains less than 2 elements; otherwise:
⑥
Split the sequence into 2 parts of (almost) equal length
•
Sort the two subsequences using merge sort (recursion)
•
Merge the two sorted sublists
How do we merge?
Loop: as long as both sequences are non-empty
•
Compare the first elements of both sequences
•
Remove the smallest and move it to the end of the output sequence
Last: if one of the sequences is empty, add the other to the tail of the output sequence
: Worst-case time complexity via tree analysis:
Height is log(n) for n the length of the input array (example has height log2(8) = 3)
Number of levels is log(n) + 1 (example has 3 + 1 = 4 levels)
Number of leaves is n (example has 8 leaves
T(n) = c x n x log(n) + d x n
Time complexity of merge sort is in Θ (nlog(n))
Shape of the input is unimportant. Best case = worst case time complexity
Divide is Θ(1), conquer is recursive, combine is Θ(n), so:
Time complexity via recurrence equations:
First assume n = 2
Then: 1- ( )
base
n
case
d=
it
{
Ê
if
2T ( E
=
I
) +
so
en
i =
if
109 (n)
na
n> 1
ËË
Substitute this 1-( n) n 1- ( i )
109 (n) c. n c.
Nog (n ) + d- n
=
: = .
+ .
Hence T is in ②(
mogen) )
The worst-case time complexity is better than for insertion sort, but this algorithm is
not in-place, whereas insertion sort is in-place (drawback)
, Trees:
Set of nodes with a parent-child relation
-
There is a unique distinguished node root (top node)
: Every non-root has a unique parent
A node may have successors / children
-
A node without successors is a leaf (lowest ones)
: A node with successors is internal
The depth of a node is the length of the path to the root.
: The height of a node is the maximum length of a path to the leaf.
The height of a tree is the height of the root or the maximal depth.
: A level or layer of a tree consists of all nodes of the same depth.
\
The number of levels of a tree is the height of the tree + 1
Binary tree:
- Every node has zero, one or two successors.
- Binary tree is complete if all levels are completely filled.
Binary tree is almost complete if all levels are completely filled, except possibly the lowest one
: which is filled left-to-right.
If a binary tree is complete, it is also almost complete, and therefore also normal binary.
Consider an almost binary tree of height h:
I If the lowest level contains 1 element, then number of elements n = 2^h
If the lowest level is full, then the number of elements is n = 2^(h+1) - 1
I So h = Ilog(n)I . So round down
I
X . P
if xp = nil ,
it is root
Divide and conquer paradigm: - quick sort
Divide: divide the problem into smaller sub problems - merge sort
: Conquer: solve the sub problems using recursion
-
Combine: combine the solutions to the sub problems to a solution of the original problem
Max-heap:
Max-heap is a data structure used for sorting: if we walk down the tree, the keys decrease.
: Condition on the shape: an almost complete tree.
-
Every node is labeled with a key.
s
Max-heap property on the keys: on every path from the root to a leaf, the keys are non-increasing,
that means H[parent(i)] >= H[i].
'
Hence, the max key is the root.
116 \ [ 16.14.10 11.7.9]
14 10
,
.
A min-heap would have keys that increase walking downwards. I I I
11 7
9
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 femkestokkink. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.41. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53068 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now