Cheatography

# Alg420 Cheat Sheet by cheatyboi

### 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

### 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

### 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