Hello! I'm Daniel Sada. I've covered most of this algorithms in classes before, but I didn't implement them myself, and see what roadblocks I've got. I'm trying to do an algorithm or two a day or at least try to solve a problem a day. I'll be alternating between new algorithms and working in problems with those algorithms.
Clone the project, then run :
python -m unittest discover algorithms/test -v
- union-find
- binary search
- stacks
- queues
- insertion sort
- selection sort
- shellsort
- quicksort
- 3-way quicksort
- mergesort
- heapsort
- Graham scan
- binary heaps
- binary search trees
- kd-trees
- red−black trees
- depth-first search
- breadth-first search
- topological sort
- Kosaraju−Sharir
- Kruskal
- Prim
- Dijkistra
- Bellman−Ford
- Ford−Fulkerson
- LSD radix sort
- MSD radix sort
- 3-way radix quicksort
- multiway tries
- ternary search tries
- Knuth−Morris−Pratt
- Boyer-Moore
- Rabin−Karp
- regular expression matching
- run-length coding
- Huffman coding
- LZW compression
- Ford fulkerson flow graphs.
Machine Learning
- Linear Regression
- Training and Loss
- Gradient Descent
- Learning Rates and Batch vs Stochastic learning.
- Tensorflow implemented linear regression.
Syntax Matching
- Syntax matching for atomlike editors.
Day 1:
- Quick Find
- Quick Union
Day 2:
- Union Find
- Weighted Union Find
- Flattened Path Union Find
Day 3:
- (partial) (undirected) Graph API
Day 4:
- (finished) (undirected) Graph API
- Graph API tests.
- Depth-First search initialization
Day 5:
- Path between two nodes with backtracking.
- Breath-first search (not finished)
Day 6:
- Breath-first search
- Breath-first tests
Day 7:
- Connected components
Day 8:
- Bipartite Graph Problem
Day 9:
- Heap
- MinHeap
Day 10:
- Min Heap
Day 11:
- Min Heap
- Max Heap
- Heap Unit tests.
Day 12:
- Bipartite grahps
- Bipartite graph tests.
Day 13:
- Refactoring some components to use .V instead of .num_V(), more pythonic.
- Directed Graph API
- Started Topological Sort
Day 14:
- Finished topological sort. (tests pending)
- Finished undirected graph cycle detection.
- Added tests to connected components.
- Started directed cycle detection.
Day 15:
- Finished directed cycle detection
- Kosajaru-Sharir algoritms for strongly connected components
- Added tests for topological sort
- Added reversal of directed graphs
- A sample stack problem, as we are in python.
Day 16:
- Binary search problem for completion.
Day 17:
- Created Snippets for faster coding.
- Selection Sort
Day 18:
- insertion sort
- shellsort
Day 19:
- Weighted Graph and Edge API and
- Minimum Spanning Trees API.
Day 20:
- Kruskal's implementation for finding the Minimum Spanning Tree of a Weighted Graph.
Day 21:
- Mergesort implemented specifically for python.
Day 22:
- Sorting tests for shell sort, insertion sort, selection sort, etc. Standardize all sorts to have the same property .sorted
Day 23:
- Quicksort
Day 24:
- Dijkstra's Three way quicksort
Day 25:
- Added priority queue.er (Which is only a Max Heap that implements total ording)
- Implemented tupled ordering in max heap to make max heap usable for a priority queue.
- Added tests for max heaps with tuples and priority queues.
Day 26:
- Started working on Binary Search Trees and Symbol tables.
Day 27:
- Finished Binary Search Tree get and put implementations,
- Added some unit tests for bst
Day 28:
- Added ceiling, floor min and max to bst.
Day 29:
- Added python iterators
- Started rank
Day 30:
- Started working on hibbard's deletion for binary search trees
- adding some unit tests, debugging some bugs.
Day 31:
- Bugfixing, bst methods should take keys, not items.
- Added more unit tests.
Day 32 :
- Started to learn (and code) red black trees.
Day 33:
- Implemented rotate left, rotate right, move left move right and put for Red Black Trees
Day 34:
- Finished Red Black Tree Deletion,
- RBT Minimum,
- Balancing the tree.
Day 35:
- Linted the entire project, fixed all of the warnings in the files.
Day 36:
- Learned about kd trees.
- Added some more tests to BSTs
- level order traversal for BST.
Day 37:
- Added unit tests to my Red Black tree implementation.
- Bugfixing RBTs
- Discovered delete min was not implemented correctly
Day 38:
- Learned about 1D and 2D interval search with BSTs
- Implemented in some cases python len repr build_subclass etc, also add.
Day 39:
- More changes in imports.
- started prim's algorithm for MSTs
- Seeing whether a contains method is useful in a MST.
Day 40:
- Kept working on prim's algorithm for minimum spanning trees.
- I added some unit tests for prim.
- Dunder methods for Heap, PQ, Edge, etc.
Day 41:
- Finally finished Prim's algorithm.
- Added Heap unit tests, priority queue unit tests, fixed weighted graph.
- Added tests for weighted graphs.
Day 42:
- Read about Delaunay's Triangulation and Voronoi diagrams.
- Learned about how Prim & Kruskal's algorithms can be used for k-clustering and that it can be close to linear.
- Implemented Directed Weighted Graphs API.
Day 43:
- Started working on Dijkstra
- MinimumIndexedPriority queues.
Day 44:
- Continued implementing Dijkstra implemented with MinimumIndixedPriority queues
Day 45:
- Did Dijkstra unit test, still debugging.
Day 46:
- Finished Dijkstra implementation with Indexed Minimum Priority Queues
Day 47:
- Implemented Bellman-Ford for negative directed graphs without negative cycles.
Day 48:
- Added unit tests for Bellman-Ford.(& fixed a bug! :D)
- Started learning about the min-cut/max-flow problems. I was ecstatic that they are equivalent! It is amazing to see it.
Day 49:
- Finished learning about the Ford-Fulkerson.
- Started Least Significant Digit radix sort.
Day 50:
- Unit tests for String sorts
- Finished LSD radix sort.
Day 51:
- Coded and unit tested MSD radix sort
- Coded and unit tested three way radix sort.
Day 52:
- Learned R-Way Tries
- Ternary Search Tries.
- Started coding them.
Day 53:
- R-Way tries
- Ternary search trees.
- Unit tests for symbol tables
Day 54:
- Learned about Knuth-Morris-Pratt
- Learned about Boyer-Moore
- Created DFA on paper to understand it.
Day 55:
- Coded Knuth-Morris-Pratt
- Started Boyer-Moore
Day 56:
- Finished Boyer-Moore
- Updated logbook.
Day 57:
- Boyer-Moore Tests
- KMP and Boyer-Moore benchmarking start
Day 58:
- Boyer moore UT finished.
- Benchmarks: (I expected find to win as it is implemented in CPython) BoyerMoore took 0.655519962310791 secs. Find took 0.006417036056518555 secs. KnuthMP took 0.8751339912414551 secs
Day 59:
- Learned about Rabin-Karp hashtag substring search, and run time length encoding.
Day 60:
- Started BinaryStreams API and Unit tests. This gives way to Data Compression algorithms.
Day 61:
- Learned about Huffman Compression with Shannon-Fano codes (which has a 4.7 bits/char rating),
- Learned about Lempel-Ziv-Welch compression. (which has a 3.32 bits/char rating)
Day 62:
- BREAK
Day 63:
- Worked on learning Linear Programming, with Brewers problem for solving maximization of variables with constraints.
Day 64:
- Started implementing Simplex algorithm. Simplex let's you maximize profits, given a set of constraints.
Day 65:
- Finished simplex.
Day 66:
- Tensorflow start. Learning from Google's crash course of machine learning.
- Learned about linear regressions
- Stochastic gradient descent
Day 67:
- First Tensorflow program (linear)
Day 68:
- Mock interviews with Interviewing.io (stack problam and preorder traversal)
Day 69:
- Dynamic programming lessons. Reviewing past problems.
Day 70:
- Learned about Generalization, Validation, Training and Test sets for machine learning.
Day 71:
- Coding exercise on Jupyter notebook on Model Validation.
Day 72:
- Started to learn how to do syntax highlighting for @code working on porting @todotxt
Day 73:
- BREAK. Finals week.
Day 74:
- Finished Syntax highliting, got into a roadblock but learned what I wanted to learn.
Day 75:
- Worked on FordFulkerson algorithm for Max-Flow and Capacity (Max Flow, Min Cut)
Day 76:
- Worked on a flow network implementation for implementing the FordFulkerson algorithm.
Day 77:
- Experimented a bit with CORS headers, kept working on the Ford-Fulkerson Algorithm
Day 78:
- Micro service deployment architectures,
- I'm trying to enable CORS between all of them. Hell raised. I know CORS is for security, but whoa..
Day 79:
- Worked on a phong shader & a yaw and pitch camera based on Euler angles using quaternions. (private repo)
Day 80:
- Cleaned up project, pausing for internship.
Day 81:
- Renamed tests to be auto-discoverable, adding more tests to the suite, removing print statements from all the sides so we get a clean test pass.
Day 82:
- Ran coverage report for all the unit tests
python -m coverage run -m unittest discover algorithms/test -v
coverage report
coverage html
Initial values:
Name | Stmts | Miss | Cover |
---|---|---|---|
algorithms\bfs__init__.py | 1 | 0 | 100% |
algorithms\bfs\bfs.py | 32 | 9 | 72% |
algorithms\binarysearchtree__init__.py | 0 | 0 | 100% |
algorithms\binarysearchtree\bst.py | 148 | 33 | 78% |
algorithms\binarysearchtree\bstnode.py | 9 | 0 | 100% |
algorithms\binarysearchtree\rbtnode.py | 10 | 0 | 100% |
algorithms\binarysearchtree\redblacktree.py | 158 | 47 | 70% |
algorithms\dfs__init__.py | 4 | 0 | 100% |
algorithms\dfs\bipartitedfs.py | 41 | 4 | 90% |
algorithms\dfs\connected_components.py | 26 | 1 | 96% |
algorithms\dfs\dfs.py | 29 | 9 | 69% |
algorithms\dfs\topologicalsort.py | 22 | 1 | 95% |
algorithms\digraph__init__.py | 1 | 0 | 100% |
algorithms\digraph\digraph.py | 27 | 10 | 63% |
algorithms\heaps__init__.py | 3 | 0 | 100% |
algorithms\heaps\heap.py | 34 | 0 | 100% |
algorithms\heaps\maxheap.py | 53 | 8 | 85% |
algorithms\heaps\minheap.py | 39 | 4 | 90% |
algorithms\mst__init__.py | 0 | 0 | 100% |
algorithms\mst\prim.py | 37 | 0 | 100% |
algorithms\priorityqueue__init__.py | 2 | 0 | 100% |
algorithms\priorityqueue\indexminpq.py | 65 | 19 | 71% |
algorithms\priorityqueue\priorityqueue.py | 20 | 2 | 90% |
algorithms\shortestpaths__init__.py | 0 | 0 | 100% |
algorithms\shortestpaths\bellmanford.py | 41 | 8 | 80% |
algorithms\shortestpaths\dijkstra.py | 64 | 34 | 47% |
algorithms\sorts__init__.py | 0 | 0 | 100% |
algorithms\sorts\insertionsort.py | 20 | 0 | 100% |
algorithms\sorts\mergesort.py | 33 | 2 | 94% |
algorithms\sorts\quicksort.py | 27 | 0 | 100% |
algorithms\sorts\selectionsort.py | 21 | 1 | 95% |
algorithms\sorts\shellsort.py | 26 | 0 | 100% |
algorithms\stack__init__.py | 0 | 0 | 100% |
algorithms\stack\stack_parenthesis_check.py | 27 | 5 | 81% |
algorithms\stringsorts\LSDradixsort.py | 20 | 0 | 100% |
algorithms\stringsorts\MSDradixsort.py | 32 | 1 | 97% |
algorithms\stringsorts__init__.py | 0 | 0 | 100% |
algorithms\stringsorts\threewayradixsort.py | 20 | 1 | 95% |
algorithms\substrsearch__init__.py | 0 | 0 | 100% |
algorithms\substrsearch\boyermoore.py | 36 | 0 | 100% |
algorithms\substrsearch\kmp.py | 35 | 0 | 100% |
algorithms\test\test_astar.py | 18 | 1 | 94% |
algorithms\test\test_bfs.py | 26 | 1 | 96% |
algorithms\test\test_binarystream.py | 10 | 1 | 90% |
algorithms\test\test_bst.py | 67 | 1 | 99% |
algorithms\test\test_dfs.py | 75 | 1 | 99% |
algorithms\test\test_digraph.py | 12 | 1 | 92% |
algorithms\test\test_heap.py | 64 | 1 | 98% |
algorithms\test\test_mst.py | 30 | 1 | 97% |
algorithms\test\test_prioirtyqueue.py | 29 | 1 | 97% |
algorithms\test\test_redblack.py | 34 | 1 | 97% |
algorithms\test\test_shortestpath.py | 41 | 1 | 98% |
algorithms\test\test_sorting.py | 59 | 1 | 98% |
algorithms\test\test_stack.py | 16 | 0 | 100% |
algorithms\test\test_stringsort.py | 38 | 1 | 97% |
algorithms\test\test_substr.py | 35 | 1 | 97% |
algorithms\test\test_trie.py | 29 | 1 | 97% |
algorithms\test\test_wgraph.py | 27 | 1 | 96% |
algorithms\tries\rwaytries.py | 35 | 1 | 97% |
algorithms\tries\tstries.py | 44 | 1 | 98% |
algorithms\ugraph__init__.py | 1 | 0 | 100% |
algorithms\ugraph\ugraph.py | 22 | 1 | 95% |
algorithms\unionfind__init__.py | 1 | 0 | 100% |
algorithms\unionfind\pathflattenedunionfind.py | 24 | 0 | 100% |
algorithms\unionfind\quickfind.py | 16 | 0 | 100% |
algorithms\unionfind\quickunion.py | 18 | 0 | 100% |
algorithms\unionfind\weightedunionfind.py | 23 | 0 | 100% |
algorithms\weightedgraph__init__.py | 4 | 0 | 100% |
algorithms\weightedgraph\diedge.py | 14 | 1 | 93% |
algorithms\weightedgraph\diweightedgraph.py | 25 | 9 | 64% |
algorithms\weightedgraph\edge.py | 20 | 2 | 90% |
algorithms\weightedgraph\weightedgraph.py | 31 | 6 | 81% |
For the following days, I'll keep adding coverage up to 100%
- Improved BFS coverage to 92% from 72%
Day 83:
- Improved BFS coverage from 92% to 100%
- Improved BST coverage from 78% to 93% and fixed bugs caught by UTs
Day 84:
- Improved red black tree coverage from 70% to 79% there is a lot of work remaining to make them awesome.
Day 85:
- Added basic tests to Bellman-Ford.
- Started working on Ford-Fulkerson and examples of the min-flow max-cut theorem, code right now is partially done, and hopefully ready to be advanced.
Day 86:
- Implement matrix multiplication in preparation for fibbonaci "investigation"
- Tests for matrix multiplication
Day 87:
- Messing around with re-implementing BoyerMoore
- Try to implement it from scratch and memory.
Day 88:
- Implemented sliding window to find permutation
- Added inline UTs for sliding window
Day 89:
- Maximum Sum Subarray of Size K
- Added inline UTs
- Practice two pointer problems
Day 90:
- Subarrays with Product Less than a Target
Day 91:
- Started learning Intervals, implemented given a set of intervals, merge them.
Day 92:
- Find if given some intervals, a given person can attend all meetings.
- Add BFS and DFS Kata, to keep both fresh. - A kata usually is something you can practice repeatedly to get quick with implementing certain patterns.
Day 93:
- Started guidesheet with most common algorithms from Grokking.
- Started islands problem with DFS.
Day 94:
- Added islands for finding islands in a lake, a simple application of DFS with UTs
- Added a couple of linked-list exercises (reversal, middle) to keep memory fresh, with UTs.
Day 95:
- Implemented middle of a stream problem with two heaps, found out that maxheaps in python are just negative minheaps
- Started subsets exercises.
Day 96:
- Implemented subsets, and permutations the "easy" way.
- Investigated itertools for easy convenience to methods
Day 97:
- Explored some of the collection library in python, a bit of the oscure methods of deque, Counter, defaultdict and more. I already knew them, but getting more proficient with them