The Role of Algorithms in Computing

Introduction to Algorithms

Introduction

• Chapter 1 : an overview of algorithms. 
• Chapter 2 : first algorithm, which solve the problem of sorting a sequence of n numbers. The insertion sort which uses an incremental approach, and merge sort which uses a recursive technique known as "divide-and-conquer." we develop a useful notation to running times.
• Chapter 3 : precisely defines this notation, which we call asymptotic notation. It starts by defining several asymptotic notations, which we use for bounding algorithm running times from above and/or below.
• Chapter 4 : delves further into the divide-and-conquer method introduced in Chapter 2. methods for solving recurrences, which are useful for describing the running times of recursive algorithms. One powerful technique is the "master method," which we often use to solve recurrences that arise from divide-and-conquer algorithms.
• Chapter 5 :  introduces probabilistic analysis and randomized algorithms.
• Appendices A-D : contain other mathematical material that you will find helpful as you read this book.

1 The Role of Algorithms in Computing
1.1 Algorithms

- Page 26
Informally, an algorithm is 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. An algorithm is thus a sequence of computational steps that transform the input into the output.

- Page 27
 An algorithm is said to be correct if, for every input instance, it halts with the correct output.

- Human Genome Project
- Internet (Chapter 24), search engine (Chapter 11 and 32)
- Encryption (Chpater 31) based on numerical algorithms and number theory
- place well in order to maximize profit. work scheduling. (Chapter 29)
- find route on the map by using graph (Part VI and Appendix B, Chapter 24)
- Find longest common subsequences (Chapter 15, dynamic programming)
- topological sorting (Chapter 22)
- convex hull (Chapter 33)
- Fast Fourier Transform

Data structures

Technique
finding medians and order statistics in Chpater 9
computing minimum spanning trees in Chpater 23
determining a maximum flow in a network in Chapter 26
divide-and-conquer in Chapter 4
dynamic programming in Chapter 15
amortized analysis in Chapter 17
NP-complete (Chapter 34)
Parallelism (Chapter 27)

1.2 Algorithms as a techonology
The importance of efficient algorithms.