Chapter 1from Introduction to Algorithms by Cormen |
Document last modified: |
OVERVIEW
Some key topics covered in course
- Correctness - algorithm produces post conditions given pre conditions hold.
- Verification - proving formally or informally, that algorithm is correct.
- Analysis - determining the efficiency of an algorithm by formal methods or empirically (e.g. profiling).
- Algorithm methods - examine fundamental methods for algorithms, such as back-tracking, divide-and-conquer, search, etc.
Algorithm - any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output
Some celebrity algorithms
- PageRank (Google search engine)
- Euclid's (over 2000 years old)
- Graph coloring (for resource allocation such as registers by a compiler)
- Shortest path (network routing)
- RSA (public key encryption)
Why study algorithms?
- Computer programs would not exist without algorithms.
- Algorithms are important: encryption algorithms ensure Internet commerce security, the PageRank algorithm ranks Google search results.
- You must know that standard algorithms from different areas of computing exist OR re-invent.
- You must be able to design new, correct algorithms and analyze their efficiency.
- Anyone can design algorithms that are incorrect.
- Many can design algorithms that are useful but too inefficient to be practical.
- It is risky, at best, to design an algorithm without some determination of correctness and efficiency.
- When pre and post conditions hold, does the algorithm produce the correct result?
- What is the worst-case running time of the algorithm?
- Usefulness in developing analytical skills.
- Algorithm design techniques can serve as problem solving strategies useful whether a computer is involved.
Important definitions
- computational problem - a problem for which computation can be used as a tool for producing a solution to the problem
- instance of a problem - a particular problem from a class of problems, e.g., a particular set of numbers to be sorted where the class of problems is sorting
- correct algorithm - for every input instance the algorithm halts with the correct output.
- data structure - a way to store and organize data in order to facilitate access (e.g. linked list, array, ...).
- algorithm efficiency - typically has to do with performance (i.e., speed), but can also refer to an algorithm's use of storage and other resources
Useful thoughts
- Computational problems can solved by algorithms and data structures. Hoare's famous comment: Program = Algorithm + Data
- Computational problems are usually grouped into classes of problems (e.g. the searching problem, or sorting problem).
- Algorithms are devised to solve particular instances of a class of problems (e.g. mergesort is efficient for large data sets).
- Multiple different algorithms are often created that solve a problem (e.g. sort and search).
- Normally we want our algorithms to possess certain properties: correctness, time efficient, space efficient.
- Hard problems are problems for which there no known efficient algorithm (e.g. the known solution requires a run time exceeding the predicted life of the universe). These are known as NP-complete problems.
- Some problems have no algorithms for solving them, such as the path to happiness or who is the next American Idol.
- Even though algorithms have no tangible physical being, they are still valuable and are considered a technology.
- The XOR operation has, at least according to urban legend, been copyrighted and licenses for its use sold to major software developers.
- The public-key RSA algorithm (and developed by one of the text's authors, Rivest) used in Secure Socket Layer protocol .
- Google exists due to the PageRank algorithm (and some clever commercialization of Web advertising).
1.2 Algorithms as a technology
Efficiency
Linear search
- To search input of size n has a worst case run-time of c*n where c is the time to compare one input.
- If each compare of input requires 10-3 seconds (1 millisecond), searching 1,000,000 (106) inputs requires:
(10-3 seconds/compare) * 106 compares = 10-3 seconds * 106 = 103 seconds = 1000 seconds
Binary search
- To search input of size n has a worst case run-time of c*lg n + c where c is the time to compare one input.
- If each compare of input requires 10-3 seconds (1 millisecond), searching 220 (1,048,576) inputs requires about:
(10-3 seconds/compare) * lg 220 compares= 10-3 seconds * 20 = .001 seconds * 20 = .02 seconds
Comparison of some common complexity measures
n
n2
n3
2n
lg n
v n
n lg n
n!
1
1
1
2
0
1
0
1
2
4
8
4
1
1
2
2
3
9
27
8
2
2
5
6
4
16
64
16
2
2
8
24
5
25
125
32
2
2
12
120
6
36
216
64
3
2
16
720
7
49
343
128
3
3
20
5,040
8
64
512
256
3
3
24
40,320
9
81
729
512
3
3
29
362,880
10
100
1,000
1,024
3
3
33
3,628,800
11
121
1,331
2,048
3
3
38
39,916,800
12
144
1,728
4,096
4
3
43
479,001,600
13
169
2,197
8,192
4
4
48
6,227,020,800
14
196
2,744
16,384
4
4
53
87,178,291,200
15
225
3,375
32,768
4
4
59
1,307,674,368,000
16
256
4,096
65,536
4
4
64
20,922,789,888,000
17
289
4,913
131,072
4
4
69
355,687,428,096,000
18
324
5,832
262,144
4
4
75
6,402,373,705,728,000
19
361
6,859
524,288
4
4
81
121,645,100,408,832,000
20
400
8,000
1,048,576
4
4
86
2,432,902,008,176,640,000
21
441
9,261
2,097,152
4
5
92
51,090,942,171,709,400,000
22
484
10,648
4,194,304
4
5
98
1,124,000,727,777,610,000,000
23
529
12,167
8,388,608
5
5
104
25,852,016,738,885,000,000,000
24
576
13,824
16,777,216
5
5
110
620,448,401,733,239,000,000,000
25
625
15,625
33,554,432
5
5
116
15,511,210,043,331,000,000,000,000
26
676
17,576
67,108,864
5
5
122
403,291,461,126,606,000,000,000,000
27
729
19,683
134,217,728
5
5
128
10,888,869,450,418,400,000,000,000,000
28
784
21,952
268,435,456
5
5
135
304,888,344,611,714,000,000,000,000,000
29
841
24,389
536,870,912
5
5
141
8,841,761,993,739,700,000,000,000,000,000
30
900
27,000
1,073,741,824
5
5
147
265,252,859,812,191,000,000,000,000,000,000
Question 1.1
For a function f(n) determine the largest problem size n that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.
Note for functions with inverses, such as:
f(n) = v n = 1,000,000 ms, the inverse v n 2 = n = 1,000,0002 =(106)2 = 1012
f(n) = log2n = lg n = 1,000,000 ms, the inverse 2lg n = n = 21,000,000
f(n) t = 1 sec. = 106 ms t = 1 min. = 6*107 ms n 6*107 lg n 21,000,000 n! 9 from above table