Show Menu
Cheatography

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 Conquer

Decrease by constant
Decrease by constant factor
variab­le-Size decrease
insertion sort
binary search and bisection method
Euclid's algoirthm
topolgical sorting
expone­nti­ation by squaring
selection by partition
algorithms for generating permut­ations, subsets
multip­lic­ation a la russe
nim-like games
 

Summations

Comple­xities

DFS

BFS

 

Brute-­Force Problems

Problem
Method
Complexity
TSP
Exhaustive
N!
KnapSack
Exhaustive
n*W

Topolo­gical Sort

Order: 5,4,2,­3,1,0

Generate Permut­ations

Example n=3:
start: 1
12, 21
123, 132, 312
321, 231, 213
finish

Euclidean Algorithm

Example:
GCD(27­0,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 Cons

Pros
Cons
Wide applic­ability
Rarely Yields Efficient
Simple
Unacce­ptably Slow
Reasonable Algorithms
Not as constr­uctive as others

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          EECS 203 Final Exam Cheat Sheet Cheat Sheet