[Algorithms] Algorithms and Data Structure

What is algorithm?

Algorithm: well-defined computational procedure. it has input and output such as some values. it is composed of a sequence of computational steps.

Correctness: for every input instance, the algorithm halts with the correct output.

Correct algorithm solves the given computational problem.

 

What is data structure?

Data Structure: a way to store and organize data in order to facilitate access and modifications.

No single data structure works well for all purposes.

 

Various techniques of algorithm design and analysis

  • Order notation
  • Minimum spanning trees (MST)
  • Maximum flow in a network
  • Divide-and-conquer
  • Dynamic Programming (DP)
  • Amortized analysis

etc.

 

Hard problems

NP-complete: the subset of computational problems.
1) no efficient algorithm for this type of problem has ever been found, and nobody has ever proven that an efficient algorithm for one cannot exist. (In other words, no one knows whether or not efficient algorithm exist for NP-complete problem.)
2) this problem has remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. (!)
3) several NP-complete problems are similar to problems for which we know efficient algorithms.

E.g. Traveling-salesman problem
To deliver goods to several address, we want to know the shortest overall distance traveled by car. => This is NP-complete (no efficient algorithm exists! However under some assumptions, we can use approximate algorithms.)

 

Efficiency

  • Different algorithms devised to solve the same problem often differ dramatically in their efficiency. (=> Discuss Order notation)
  • Difference of efficiency can be much more significant than differences than differences due to hardware and software.

E.g. Time complexity
Two algorithms for sorting. if n items given as input, computational time of each algorithm are
1) Insertion sort: c_1 n^2
2) Merge sort: c_2 n{\rm log}n
where c_1, c_2 are constant.
Although insertion sort usually runs faster than merge sort for small input size, the input size c becomes large enough, merge sort’s advantage of {\rm log}n vs. n.

 

Algorithms are at the core of most technologies.
Skilled programmers with the knowledge of algorithms.