ALGORITHMS - Why are they important?

Algorithm: is a set of rules [like a recipe] to solve a computational problem.

Practical Applications:

1. Routing in communication networks uses shortest path algorithms.
2. Encryption [All passwords ever used need to be stored in a safe format on some database].
3. Computational biology [This is new to me!] uses such techniques to measure genome similarities...
4. Search Engines - to calculate the relevance of web pages with respect to a search query.
5. Machine Learning - to study patterns in user likes & dislikes, in economic markets...etc. Ooh, there's lots of money to be made for a Computer Scientist in these areas :D 

WARNING: Working with Algorithms can get really frustrating especially when things don't work the way you hoped they would. But, don't give up. [At least, this is what I keep telling myself!]

Two Mantras:
1. Always question if there's a better solution [So you're never allowed to be content with your solutions].
2. Always Be Coding

Running Time: of an algorithm is the number of lines of code that is executed. Think of it as the number of times you might have to step through the code with a debugger; a very tedious process might I add.

Guiding Principles in Analysis of Algorithms [3]:

I. Types of Analyses:

1. Worst-Case Analysis: No assumptions about the source of the input, what it looks like; all we cared about it is the input length.
2. Average-case Analysis: You analyse the average running time under some assumption of the relative frequencies of different inputs.
3. Benchmarks: Here one agrees upon certain parameters of the input suitable for practical settings say the input size will never grow beyond length 20, for example.

The last 2 requires domain knowledge. Hence worst case is more appropriate for general-purpose routines. 

II.
Do not obsess over constant factors and lower-order terms - by doing this we lose very little predictive power of how fast an algorithm is. These constants depend on the processor architecture, programming language, compiler optimizations/programmer...etc.

III. Asymptotic Analysis: Focus on running time for large input sizes [asymptotic means a variable, say, that approaches a limit, usually infinity]. It deals with the rate of growth of an algorithm's performance.

Fast Algorithm == worst-case running time grows slowly with input size.