• Update ->4/5/17 I bought my first Knuth book today! It's on Combinatorics/Sorting/Searching. This is getting serious :)

Distracting_KATAS

This is a repo for all the katas that distract me while I'm trying to get work done. This is mainly because I like working on puzzles and am working on getting better at:

1. Algorithms
2. Data Structures
3. Mathematical Puzzles
4. Logic in solving Problems
5. Matrices and Linear Algebra (eigenvalues, eigenvectors, etc)
6. Regex (regular expressions) -> need to get better at this
7. Arithmetic Progression/ sequences in programming -> Design patterns
8. Dictionaries => key value pairs and matrices
9. Enums (specifically in Ruby, which I don't really know right now, or wait...in Python!)
10. Bitwise operations => Indempotency, Monotonicity, etc -> bin(n+(1 << 32))
11. Currying in other languages (eg. Javascript)
12. Datetime in Python (stripping/ parsing using RegEx)
13. Flattening nested lists using Lambdas

I also have a bad habit of not leaving \n after my code. Need to get better at including that on Github. I apologize for meaningless commits of \n, but it won't become a habit.

Making a list of concepts learning through katas:

1. Recursion with Memoization

2. Binary Expansion

3. Polybius squares

4. Hamming Distances

5. Swapping two Numbers without Temp: (where swap is function swap([ary]))

   ary[0] = ary[0] + ary[1]

   ary[1] = ary[0] - ary[1]

   ary[0] = ary[0] - ary[1]

6. Pascal's Triangle

7. Collatz Conjecture (3n + 1)

8. Isogeny -> Cryptography

9. Bresenham algorithm

10. Annulus Theorem -> => Area of Annulus-> (PI * L^2) / 4

11. Holomorphic Functions

12. Heron's Formula => Math.sqrt(p(p-a)(p-b)(p-c)) where a is length a, b is length b, c is length c and p is perimeter / 2

13. Monte Carlo Integration

14. Tetration -> Knuth's Up Arrow Notation vs Conway's Chained arrow notation (1->2->3->4 etc)

15. Zeckendorf's Theorem and Negafibonacci numbers

16. Fenwick trees

17. Logical disjunction/conjunction -> boolean mathematics XOR OR, etc

18. Inverse Gamma Function

19. Jaccard Similarity Coefficient

20. Chebyshev Polynomials -> de Moivre's formula

21. Runge's phenomenon

22. Levenshtein distance vs Hamming distance

23. Edit Distance -> Smith-Waterman algorithm, Needleman-Wunsch algorithm -> NLP applications -> sorting strings

24. Mobius Function -> number theory/ combinatorics

25. Trilinear Interpolation

26. Crypto -> Polygraphic Substitution, Transposition Ciphers, Pigpen Ciphers, Vigenere ciphers

27. Polybius Squares x1 y1 x2 y2 row and column to determine encryption of letter

28. Fisher -Yates shuffle, Sattolo's algorithm

29. Taylor Series --> Zeno's paradox

30. Voronoi (diagram) / Centroidal Voronoi tessellation -> Fortune's algorithm

31. Petersen Graphs/ Spanning Trees (Combinatorics/ Graph Theory)

32. Incremental Voronoi Insertion -> Farthest-first-traversal algorithm (greedy algos)

33. Bowyer-Watson Algorithm -> adds point to Delaunay triangulation -> used to obtain Voronoi diagram -> very interesting! -> think point clouds and terrain

34. RMST-> Rectilinear Minimum Spanning Tree -> weight of edge between a pair of pints is rect dist between 2 pts

35. Antipodal theorem -> Borsuk-Ulam theorem (reading S. Ulam's book)

36. Baire Category Theorem (BCT)

37. Alpha-Beta Pruning

38. Ergodic transformations -> "a mapping of a plane onto itself, in which the successive images of a point were dense in the whole plane." -Ulam

39. GAN-> Ian G. (AI wtb) generative adversarial network

40. Evolutionary algorithms (Ud#city)

41. Homomorphic Encryption and Differential Privacy (Ud#city)

42. Motivic Cohomology

43. Quantum bogosort :)

44. Pell numbers -> recursive

45. Langton's ant -> two-dimensional universal Turing machine

46. Topological Sort -> DAG (Directed Acrylic Graph)

47. Grothendieck topology

48. Manacher's algorithm

49. Gamma function

50. Simplicial set

51. Hadamard Matrix

52. Blum Blum Shub : pseudorandom number generator

53. Gyrovector spaces

54. Neville's Method of Polynomial Interpolation

55. Transitivity (graph theory)

56. Circuits, Cycles, Trees and Digraphs (graph theory)

57. Heyting Algebra (from PS community on FP)

58. Skeleton Category of Finite Sets (from PS community on FP)

59. Heyting Functors (from PS community on FP)

60. Cnoidal waves and the Korteweg-de Vries equation, Boussinesq approximation/ waves

61. Ultra filters..from E Kiehl's talk on "A Categorical View of Computational Effects."

62. Kolakoski Sequence/ clumps

63. Hinton diagrams

64. Outstanding explanation of DAGs, Directed Acrylic Graphs, using example of buying travelling (you need to get a visa to get a passport, you need foreign exchange to buy gifts, etc).

    • Richard Southwell also has a great intro to Mathematica that directly shows the relationship between Adjacency Matrices and something like Directed Graphs. See here.

65. McGregor Graphs. See Knuth video -> Sat Solvers, Van der Waerden's Problem etc

66. Implementing a Garbage Collector in C++ -> Boehm garbage collector, mark-sweep algorithm

67. Row Polymorphism vs Subtyping via PureScript

68. Grobner basis

69. System F vs System U and Graph Reduction

    • pertaining to Haskell compiler and lazy evaluation

70. Runge-Katta and Lipschitz Continuity, Adams Moulton

71. Prefix sum (see this Lambda World talk on Naperian Functors)

72. Tambara functors from Bartosz talk (which I usually have to watch about five times)

73. Bitonic Sort courtesy of Compiling to Categories