Introduction to Algorithms Chapter 1 - The Role of Algorithms in Computing

Introduction

This chapter answers: what are algorithms? why is the study of algorithms worthwhile? What is the role of algorithms relative to other technologies?

This book also teaches techniques of algorithm design and analysis: developing algorithms on my own, showing they give the correct answer, and analysing its efficiency.

Algorithms

An algorithm is any well-defined computational procedure that some input and produces some output in a finite amount of time.

An algorithm can be a hardware design or a program but must provide a specific computational procedure to be followed. (e.g. hardware: FFT circuit, software: FFT algorithm)

Instance of a problem consists of the input needed to compute a solution to the problem (e.g. list of numbers to sort)

“Correct Algorithm” is that for every problem instance, it halts (finishes computing in finite time) and outputs the correct solution. It can be said to “solve” the computational problem.

Data Structure: way to show and organise data to facilitate access and modifications

NP-Complete Problems:

• No efficient algorithm found but also an efficient algorithm’s existence has not been disproven.
• If an efficient algorithm is found for one, an efficient algorithm found for all.
• The problems are slightly modified to problems that have an efficient algorithm
• These are only decision problems that is an output of “yes/no” (e.g. Travelling Salesperson Problem: whether an order of stops exist whose distance totals at most a given amount.)
• Arise often in real-world applications so first, prove it is NP-Complete then develop an efficient approximation algorithm

Algorithms as a Technology

Choose algorithms bases on resources such as time and space efficiently. Choosing a more efficient algorithm even with a faster computer and with larger coefficients can still make a massive difference in efficiency. \(\frac{2\cdot(10^7)^2 \text{instructions}}{10^{10} \text{instructions/sec}} = 20,000 \text{ seconds} \\ \frac{50\cdot10^7 \lg10^7 \text{instructions}}{10^{7} \text{instructions/sec}} = 1163 \text{ seconds}\)

Computer A (the top one) is much faster running at 10 billion instructions per second and has a much faster implementation of insertion sort with a coefficient of $2$ and with an order of growth of $n^2$. Computer B (the bottom one) is running 1000 times slower and has a more efficient compiler (being written in a high-level language) which gives it the coefficient of $50$ with an order of growth of $n \lg n$ but still is magnitudes of order faster. The difference is much more pronounced at larger values of $n$.

The book considers algorithms as a technology, like choosing the best computer hardware; you choose the best or most efficient algorithms. Some applications may not require algorithms at the application level, they are still found within the application. For example, hardware design, GUIs, and networking all use algorithms.

Machine learning can be thought of as inferring patterns from data without explicitly designing an algorithm. However, machine learning itself is a collection of algorithms and its use case is for problems where humans do not really understand the right algorithm to use.

Data science is an interdisciplinary field with the goal of extracting knowledge and insights from structured and unstructured data. It uses methods from statistics, computer science, and machine learning. The core techniques of data science overlap significantly with machine learning.

Applications, machine learning, and data science all rely on algorithms indirectly even when it may not be seen directly.