Skip to content

Latest commit

 

History

History
236 lines (228 loc) · 11.3 KB

README.md

File metadata and controls

236 lines (228 loc) · 11.3 KB
Raw

Java Algorithms Implementation


contributions welcome

1. GCD & LCM 

1.1 Basics of GCD and LCM
1.2 GCD [ Euclid’s Algorithm ] [ O log10(n), n = max(a, b) ]
1.3 LCM [ O log10(n), n = max(a, b) ]
1.4 Extended Euclid’s Algorithm

2. Sorting

2.1 Basics
2.2 Bubble Sort [ O (n2) ] 
2.3 Key-indexed sorting [ O (n + k) ]
2.4 Insertion Sort [ O (n2) ]
2.5 Selection Sort [ O (n2) ]
2.6 Object Sort [ O (n log n) ]

3. Searching

3.1 Basics
3.2 Binary Search [ O (log n) ]
3.3 Binary Search [ First occurrence ] [ O (log n) ]
3.4 Binary Search [ Last occurrence ] [ O (log n) ]
3.5 Lower Bound [ O (log n) ] And Upper Bound [ O (log n) ] 
3.6 Uses of upper and lower bounds 
3.7 Linear Search [ O (n) ]

4. String

4.1 Basics
4.2 Brute Force [ O (n – m + 1) m ]
4.3 Knuth Morris Pratt  (KMP) 
4.4 Rabin - Karp 
4.5 Aho - Corasick
4.6 Boyer – Moore
4.7 Suffix Tree
4.8 Determine Subsequence [ Sliding Window ] [  O (n) ]
4.9 Determine Anagrams O (n)

5. Number Generation

5.1 Generation of  Fibonacci Numbers [ O(n) ] [ DP ]
5.2 Generation of  Fibonacci Numbers [ log(n) ] 
5.3 Factorial [ O(n) ] [ DP ]     
5.4 Generation of  Derangement or Subfactorial or Rencontres numbers [ O (n) ] [ DP ]
5.5 Generation of  Prime Numbers by The Sieve of Eratosthenes  [ O (n log log n) ]
5.6 Generation of Catalan number [ O (n) ] [ DP ]

6. Fibonacci Series

6.1 Brick Wall Patterns [ O(n) ] [ DP ]
6.2 Determine the number of n-bit sequences that contain no adjacent 1’s [ O(n) ] [ DP ]
6.3 Bee [ Modified version of Fibonacci sequence ] [ O(n) ] [ DP ]

7. Combinatorics

7.1 nCr 
7.2 nPr  
7.3 Kth Permutation
7.4 Determine how many digits in n factorials using log
7.5 Determine how many digits in nCr using log
7.6 Determine how many digits in a number [ O log (n) ]
7.7 Determine how many times digit d occurs from 1 to n
7.8 Digit Occurrence Count in a number
7.9 Josephus Ring Survivor [ O (n) ]
7.10 Number of ways

8. Dynamic Programming

8.1 Coin Change problem [ CC ]
8.2 Knapsack problem [ 0/1 ] 
8.3 Longest Common Subsequence [ LCS ]  [ O (mn) ]
8.4 Longest Increasing Subsequence [ LIS] 
8.5 Longest Decreasing Subsequence [ LDS ] 
8.6 Edit Distance
8.7 Using 1,2,3 how many numbers you can make such that the sum of their digits is equal to the given number 
8.8 Cumulative Sum 
8.9 Matrix Chain Multiplication [ MCM ]

9. Greedy

9.1 Coin Change problem [ US Coin ] 
9.2 Knapsack problem [ Fractional ] 
9.3 Huffman Coding

10. Algorithm

10.1 Leap year check
10.2 Digital Root [ O (1) ]
10.3 Last Digit by Mod
10.4 Minimums Cuts
10.5 Map [ O (n) ] 
10.6 Clock Algebra
10.7 Traverse
10.8 Bitwise operation’s 
10.9 Parentheses Balance check using Stack
10.10 Given number 1 to N, how many steps need to make them zero by subtract a positive number in every step [ O log2(n) ]
10.11 Hangman Judge [ O (n  + k ) ]
10.12 Compute b^p and (b^p) % m [ O log(p) ]
10.13 Merge [ O (n + m) ]
10.14 How many squares are there in a n by n square grid  [ O (n) ]
10.15 Maximum contiguous subsequence sum [ 1D, 2D ]
10.16 McNuggets

11. Number Theory

11.1 Chinese Remainder Theorem
11.2 Number of Divisors [ O sqrt(n) ]
11.3 Sum of Divisors [ O sqrt(n) ]
11.4 Prime divisors
11.5 Base Conversion [ 2 to 9 ]
11.6 Base Conversion [ any base to any base ] [ O (n) ]
11.7 Determine if the number valid or not providing the base [ O (n) ]
11.8 Arabic Numerals to Roman Numerals and Roman Numerals to Arabic  Numerals
11.9 Primility test  
11.10 Big Number Divisibility Check	 
11.11 Pascal’s triangle
11.12 Bézout's identity
11.13 Lagrange's four-square theorem

12. Numerical Methods

12.1 Root Finding Methods
12.2 Big Integer Square Root [ Newton-Raphson Method ] 
12.3 Interpolation and Extrapolation with Equal Intervals [ Newton’s Formula ] [ poly(n) ]
12.4 Interpolation and Extrapolation with Unequal Intervals [ Newton & Lagrange Formula ] 
12.5 Factorial [ Stirling's approximation ]
12.6 Descartes' rule of signs

13. Basics of Numbers

13.1 Factorial 
13.2 Derangement or Subfactorial or Rencontres numbers
13.3 Fibonacci sequence
13.4 Prime numbers
13.5 Permutations
13.6 Combinations 
13.7 Catalan number
13.8 Odd numbers 
13.9 Perfect Square numbers
13.10 Triangular Number
13.11 Co-prime
13.12 Rational Number

14. Java

14.1 Math.random
14.2 Big Integer 
14.3 Big Decimal 
14.4 String
14.5 StringBuffer
14.6 StringTokenizer
14.7 Character
14.8 Tree Set 
14.9 Hash Set
14.10 Tree Map
14.11 Hash Table
14.12 Arrays
14.13 Vector
14.14 ArrayList
14.15 Array Deque
14.16 Stack
14.17 Queue
14.18 Priority Queue
14.19 Linked List
14.20 Data Structure Tradeoffs
14.21 Collections
14.22 Calendar and Gregorian Calendar
14.23 Matcher and Pattern [ Regular Expression ]
14.24 Bit operators
14.25 Base Conversion
14.26 Working with \n and \r
14.27 Sample I/O (Nafi)
14.28 Faster I/O 
14.29 printf
14.30 Mathematical Library Functions 
14.31 Java Primitive Data Types
14.32 Others

15. Computational Geometry

15.1 Basics
15.2 Triangle
15.3 Circle
15.4 Rectangle
15.5 Square
15.6 Trapezium
15.7 Parallelogram
15.8 Sphere 
15.9 Polygon
15.10 Cylinder
15.11 Cone
15.12 Line
15.13 Basic Formula of Geometry
15.14 Closest pair on 2D [ O (n log n) ]
15.15 Convex Hull

16. Math

16.1 Value Comparisons
16.2 Quadratic equation
16.3 Series
16.4 Modular arithmetic theorem 
16.5 Logarithms 
16.6 Trigonometry
16.7 Basics of Division, Multiplication, Addition and Subtraction
16.8 Basics of Fraction
16.9 Basics of Root
16.10 Even & Odd number
16.11 Set Theory
16.12 Zero

17. Physics

17.1 Temperature Conversion 
17.2 Equations of uniformly accelerated linear motion

18. ASCII Table

19. Miscellaneous

My Articles

  1. How to Determine a Prime Number Efficiently
  2. An Introduction to Linear Search
  3. An Introduction to Binary Search
  4. Sorting Algorithm: Bubble Sort
  5. Sorting Algorithm: Selection Sort

Bug Reports and Feature Requests

Please create an issue with as much information you can. Thank you.

Author

Mahbub Zaman (https://mahbub.ninja)

License

MIT License