Discrete Math and Algorithms are hard.
Remember -- all of these algorithms were discovered (or refined for computers) over the last 70+ years.
No one person sat down and conjured them up in a few sessions like this class will. They are elementary or
fundamental, they are not simple or trivial.
If all of these problems are solved, why are we re-solving or re-analyzing them? Because if you don't learn on solved problems, you'll never be able to tackle unsolved ones. Also, the general problem solving process sharpens our process that we'll apply to programming -- think of isolating a single skill, like a tennis serve or basketball free throw.
- https://github.com/vkostyukov/scalacaster
- https://github.com/TheAlgorithms/Scala
- https://www.scala-algorithms.com/
- Advanced Functional Data Structures and Algorithms by Atul S. Khot and Raju Kumar Mishra
- Grokking Algorithms by Aditya Y. Bhargava
- Dive Into Algorithms by Bradford Tuckfield
- Algorithms by Jeff Erickson
- Algorithms Notes for Professionals
- Advanced Algorithms and Data Structures by Marcello La Rocca
- Data Structures & Algorithm Analysis by Clifford A. Shaffer and the OpenDSA project
- The Algorithm Design Manual by Steven Skiena
- Algorithms in a Nutshell by George T. Heineman, Gary Pollice, and Stanley Selkow
- TheAlgorithms and github
- Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein a/k/a CLR a/k/a "The Big White Book That Won't Fit on a Shelf"
- Daniel G. Graham -- Algorithms
- Algorithms by Robert Sedgewick and Kevin Wayne. Also available on Coursera in Part 1 and Part 2
- Coursera - Data Structures and Algorithms Specialization
in prereq order:
- Mathematics for Computer Science -- MIT 6.042J
- Intro to Algorithms -- MIT 6.006
- Design and Analysis of Algorithms (MIT 6.046J / 18.410J)
- Advanced Data Structures (MIT 6.851)
structure and semantics
- Bag (multiset)- non-unique; add and iterate
- Set (USet)- unique; add and iterate; unordered
- SSet (sorted set) - supports successor find
- Hash table (map, hash map, associative array, dictionary). A symbol table is usually implemented using a hash table, and is sometimes referred to synonymously. Effectively a set of tuples queryable by the 1st element in the tuples.
- Queue - FIFO
- Pushdown stack - LIFO
- Priority Queue - highest priority goes to top. usually implemented using heap.
- Array
- Vector
- List
- Non-empty List
- Chain - list-like, with constant time prepending and appending. See Cats Chain
- Binary tree
- Heap
- Fisher-Yates
- https://www.developer.com/tech/article.php/10923_616221_2/How-We-Learned-to-Cheat-at-Online-Poker-A-Study-in-Software-Security.htm
- Sattolo's algorithm https://danluu.com/sattolo/
- Bubble sort (sinking sort) - repeatedly pass through the list and compare adjacent elements, until the list is sorted
- Selection - repeatedly find the next lowest value in the remaining list and swap to head. slow, but, data movement is minimal
- Insertion - repeatedly swap the head of the unsorted partition with the next higher value, then move to the next and repeat. fast for already-sorted data. what most people use for sorting cards.
- Shell - h-sorted array -- insertion sort with h interleaved sorted sequences, gets items closer to their eventual location with each reduction of h . Ciura's gap sequence [701, 301, 132, 57, 23, 10, 4, 1]
- Mergesort - divide-and-conquer -- recursively sort and combine sub-lists
- Quicksort - recursively sort lists into bigger/smaller than pivot (why not called pivot sort) Tony Hoare
- scan from right and left to find two elements that are both out of order, then swap
- Introsort - quicksort, then heap sort for small sets
- Heapsort
- Timsort