100daysofalgorithms

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.

Running unit tests.

Clone the project, then run :

python -m unittest discover algorithms/test -v

Topics to cover:

• 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 to Day log.

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