Back to School

Collection of algorithms & data structures across a multitude of languages.

Functional Paradigms

• map: Apply a function to each element in an iterable.
• reduce: Accumulate a list into a scalar.
• flatten: Join arbitrarily nested arrays into a single array. Think of getting the leaves from a tree.
• collapse: Like flatten, but with a reduction at each level to one final.
• level: Like flatten, but handles scalars mixed in amongst the lists.
• merge: Given n lists, emit lists of size n, with one value from each passed list.
• min: For each item, emit the smallest value seen up to that item's index.
• max: Inverse of min.
• sample: Emit values according to a selector function.

Data Structures

Abstract Data Types

Courtesy of NIST

• Bag: An unordered collection of values that may have duplicates.
• Dictionary: An abstract data type storing items, accessed by a key.
• Priority Queue: Fast access to the min/max value.
• Queue (FIFO)
• Set: Unordered collection of unique values.
• Stack (LIFO)

The Catalog

• Core
  • Linked List
  • Dynamic (resizable) Array
  • Ring Buffer
  • Hash Set
  • Hash Map w/ chaining
  • Binary Heap
  • Binary Search Tree
  • Prefix tree/Trie
• Supplementary
  • LRU Cache
  • Union-Find
  • B-Tree
  • Suffix tree
  • Bloom Filter

Algorithms

• Graph
  • BFS
    • BFS thru matrix
  • DFS w/ cycle detection
    • DFS thru matrix
  • Topological Sort using Tarjan's Algorithm
  • Dijkstra's Algorithm (w/o decrease-key)
• Binary Search
• Randomized Quick Sort
• Mergesort
• Longest Common Subsequence
• Knapsack

Thoughts

Given SIMD, could you have a map that acts on vectors in parallel? Not only that, but could you compile the map to use different sized vector operations depending on the architecture?

Project Idea: Automatic Big-O calculator. Execute the function under different combinations of parameters, benchmarking time. From this graph, deduce the best fit for the data.

Project: Make the graph of ADTs to the methods they implement. Nodes: methods, ADTs. Edges: Has (ADT->method), Using (method->method). The Wikipedia entries on specific ADTs would be helpful. https://en.wikipedia.org/wiki/Set_(abstract_data_type)