Algorithm and Data Structure

A (general) algorithm is a procedure accepting arguments of any data type that satisfies certain properties (invariant, concept). A data structure, or abstract data type, is an invariant-defined set of data types which is studied for the analysis of algorithms. The design, implementation and use of general algorithms is called generic programming.

Algorithm

Algorithm analysis

• Huffman coding
• Binary search
• KMP string searching (Knuth–Morris–Pratt)
• Critical path method

Sorting algorithms

• Merge sort
• Heapsort
• Quicksort
• Topological sorting

Graph algorithms

• Prim's algorithm
• Kruskal's algorithm
• Dijkstra's algorithm
• Floyd–Warshall algorithm

Data structure

1. Set: a collection of unique values.
2. List (linked list): every element has a key and a reference, with linear structure and insertion or removal from anywhere during iteration.
   • Stack (FILO): a container with insert/push and delete/pop operation at one end (top).
   • Queue (FIFO, buffer): a container with insert/enqueue at one end (back) and delete/dequeue at another (front).
3. Tree (hierarchy): every element/node has one parent except the root, and may have one value/key.
   • Heap (priority queue): The key of a parent node is always no greater/less than those of its children.
4. Graph: mapping within a set which can represent connection, directed link, and weight.
5. Associative array (map, dictionary): a collection of key-value pairs, where keys are unique.
   • hash table: a hash function separates each key into a separate bucket of an array.
   • search tree: ordered, optimized for search.
6. Multimap: a collection of keys potentially associted with multiple values.

Trees

• Binary search tree (BST)
• AVL tree (Adelson-Velskii and Landis')

---

🏷 Category=Computation