Show Menu

Alg420 Cheat Sheet by

algorithms

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

Download the Alg420 Cheat Sheet

2 Pages
//media.cheatography.com/storage/thumb/cheatyboi_alg420.750.jpg

PDF (recommended)

Alternative Downloads

Share This Cheat Sheet!

 

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