⛓ Algorithm & Data-Structures
- Sorting Algorithms
- Linked Lists
- Hashing Algorithms
This page gives you a brief overiew of the most important topics in Algortihm and Datastrucure Basics. Links for further research will also be included
Depending on the underlying Data, there are various Algorithms that can be used to arrange them in an ordered way, going from Basic 1 by 1 Sorting to advanced complex procedures. Popular examples with worst case are as follows:
- Insertion Sort - Puts a new value at the end of an already sorted Array and swaps with its imediate neighbour until in the correct position = O(n²)
- Selection Sort - Scans the entire Array for the smallest value and appends it to an empty Array = O(n²)
- Bubble Sort - Swaps 2 neighbours so they are sorted within themselves = O(n²)
- Quicksort - Chooses a (random) element in the Array as a pivot, all that are smaller or equal go into a left sub array, all that are bigger into a right subarray, happens recursively until sorted = O (n²)
- Mergesort - Splits the whole Array into 2 Parts, which are recursivley split again, until only 1 Element remains per Array, then Sort while merging them = O(n log n)
Other useful links for Sorting
- YouTube Playlist - A playlist that covers the basics of simple but/and effective Sorting Algorithms
- Sorting in C# - Every wondered what Array.Sort actually does in the background, this is the right page for you (also with code samples)
- Runtime Complexity - A Quick overview of how long you can expect your algorithm to be running. Useful when you wondere whether that 100 item List Sort should really be taking around 15 minutes to complete.
The Big-O-Notation and Landau Symbols
This chapther hopefully takes out the "O No" of the "Big O Notation", lets get started. Basically it is a way of quickly stating how long an algorithm will run (in the worst case). This is hardware independent and just shows whether an algorithm behaves with very large numbers, and if it is a good idea to use it.
- Brief overview - This page breaks down the basics of what the Big-O-Notation intends to do, also check out [the Big-O-Cheatsheet]((https://www.bigocheatsheet.com/). This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science.
- Video Explanation - A 5 minute guide on how to use the big O Notation to calculate the worst case complexity of an algorithm.
- Best/Worst/Average Runtime - A short overview of the different runtimes that can be calculated.
- O,Ω,Θ = ??? - There is more to the Landausymbols than just the big O. Theta and Omega, the most important ones besides O, are covered in this brief read.
There are many different ways to store data efficently, the following part will demonstrate the DOs and DONTs of Datastructures.
A Linked List can be imagined as a thread with beads on it. In order to reach the end of it, you need to go over all beads (= nodes) between the start (= head) and the end (= tail). Traversing takes a long time, but inserting and deleting is very quick.
A tree can be depicted as a tree (shocking i know). Trees have one Root, and can have many branches (but often times only 2) leading to their children. Those can again have branches to other nodes.
An AVL tree is a special form of tree. Sometimes a normal tree can be very onsided and resembles a Linked list more than a proper tree structure. In order to prevent that, AVL trees were created. They are always as balanced as possible, in order to reduce search time.
- Linked List - Geeks for Geeks explains the concept of a linked list with examples in JAVA (which is quite simmilar to C# so it should be easy to translate)
- I am Groot? - For all those ever wondering whether they are a tree or not, this website covers all the features and terminologies about trees (I am Groot!).
unbalanced - AVL Trees take normal Trees on another level in terms of searchtime and Tree height. Learn it all here!
Pathfinding Algorithms are very important in many different situation, ranging from Google Maps routes to HTTP Packets hopping the Internet
- Dijkstra vs. Prim - This video sums up the 2 ideas of the Dijkstra Algorithm and the Prim Algorithm with visual explanation.
- Travelling Salesman Problem - This is a well known Pathfinding Problem. At a small scale it seems easily duable, but due to its nature, it was actually quite hard to find an efficent programmatic solution for larger samplesizes.
Websites for the interested
- The know it all - This website is a collection of all of the above topics, so if you need further info just search through the sidebar and you will surely find what you need.
- Bug? No, Ant! Langton's Ant is a 0 Player game, just like Conaway's Game of Life but less well known. You define a set of Rules (Left/Right/Continue/Turn) for an "Ant" and let it run based on those rules. Complex patterns emerge with minimal programming, which is quite interesting to me.