Transcript Document
CS201 Tech-Talk One: Algorithms Michael Hsu CSULA What is an algorithm? A self-contained step-by-step set of operations to be performed, often an solution to a specific problem An effective method that can be expressed within a finite amount of space and time Expressed in a well-defined formal language Runtime/resource analysis Formal proofs/definitions/techniques covered in CS312, CS512 Input Source: http://en.wikipedia.org/wiki/Algorithm Algorithm Output Input Algorithm Output Sieve of Eratosthenes: Finding Prime Numbers A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself. Input: integer n, output: a list of prime numbers <=n The algorithm: 1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n). 2. Initially, let p equal 2, the first prime number. 3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ... ; the p itself should not be marked). 4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3. 5. When the algorithm terminates, all the numbers in the list that are not marked are prime. Source: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Sieve of Eratosthenes in Action Source: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Why Learn Algorithms? Don’t reinvent the wheel There are many existing algorithms that are formally proven to be efficient In some cases, using your own algorithm creates security risks Cryptography: Cryptographically secure pseudorandom number generator It is still good to think about the problem on your own, then do some research online and find an algorithm that solves the problem. Try to understand how it works. Practice implementing popular algorithms Popular code interview question I encourage you to use existing algorithms if applicable in the labs Just cite your resources in the comments Some Good Resources Rosetta Code: http://rosettacode.org/wiki/Rosetta_Code Implementations of popular algorithms in popular languages Example: Sieve of Eratosthenes: http://rosettacode.org/wiki/Sieve_of_Eratosthenes Introduction to Algorithms on MIT open courseware http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046jintroduction-to-algorithms-sma-5503-fall-2005/