Cheatography
https://cheatography.com
Sieve of Erath// Java program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes
class SieveOfEratosthenes
{
void sieveOfEratosthenes(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
boolean prime[] = new boolean[n+1];
for(int i=0;i<n;i++)
prime[i] = true;
for(int p = 2; p*p <=n; p++)
{
// If prime[p] is not changed, then it is a prime
if(prime[p] == true)
{
// Update all multiples of p
for(int i = p*2; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers
for(int i = 2; i <= n; i++)
{
if(prime[i] == true)
System.out.print(i + " ");
}
}
|
3 Types of Decrease and ConquerDecrease by constant | Decrease by constant factor | variable-Size decrease | insertion sort | binary search and bisection method | Euclid's algoirthm | topolgical sorting | exponentiation by squaring | selection by partition | algorithms for generating permutations, subsets | multiplication a la russe | nim-like games |
| |
| | Brute-Force ProblemsProblem | Method | Complexity | TSP | Exhaustive | N! | KnapSack | Exhaustive | n*W |
Generate PermutationsExample n=3:
start: 1
12, 21
123, 132, 312
321, 231, 213
finish |
Euclidean AlgorithmExample:
GCD(270,192)
270/192 = 1 R 78
GCD(192, 78)
192/78 = 2 R 36
GCD(78,36)
78/36 = 2 R 6
GCD(36/6)
36/6 = 6 R0
since R = 0, 6 is GCD |
Brute Force Pros vs ConsPros | Cons | Wide applicability | Rarely Yields Efficient | Simple | Unacceptably Slow | Reasonable Algorithms | Not as constructive as others |
|
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets