# Introduction: Algorithms

## What is an algorithm?

An algorithm is a set of steps for accomplishing a task. For example, a recipe for baking a cake is an algorithm - because a recipe is a series of steps for transforming the input to the desired output.

In code, even a simple function \(`doubleNumbers(array)`\) can be considered an algorithm. On this page, we highlight some of the more useful and commonly known algorithms.

Before you dive in, check out this 5-minute [video](https://www.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/v/what-are-algorithms) which gives a nice introduction to algorithms.

## Use cases of algorithms

* Reduce traffic jam
* Find your best match in speed-dating event
* Improve operational efficiency in PSA port
* The secret behind blockchain

Algorithms are everywhere in our lives! Checkout [this podcast](https://www.contriber.com/examples-of-algorithms-in-everyday-life/)

## Examples

### Searching on arrays

Well known searching algorithms on arrays

* Binary Search

### Searching on a graph

* Breadth-First Search
* Depth-First Search
* Shortest Path Search
* Travelling Salesman Problem

### Sorting an array

Common Sorting Algorithms

* [Selection Sort](https://www.geeksforgeeks.org/selection-sort/)
* [Insertion Sort](https://www.geeksforgeeks.org/insertion-sort/)
* [Bubble Sort](https://www.geeksforgeeks.org/bubble-sort/)
* [Merge Sort](https://www.geeksforgeeks.org/merge-sort/)
* [Quick Sort](https://www.geeksforgeeks.org/quick-sort/)

[https://codility.com/media/train/4-Sorting.pdf](https://codility.com/media/train/4-Sorting.pdf)

#### Visualization of Algorithms

* [https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
* [https://www.toptal.com/developers/sorting-algorithms](https://www.toptal.com/developers/sorting-algorithms)
* [http://sorting.at/](http://sorting.at/)
* [http://pythontutor.com/javascript.html\#mode=edit](http://pythontutor.com/javascript.html#mode=edit)
* [http://algo-visualizer.jasonpark.me/](http://algo-visualizer.jasonpark.me/)
* [https://visualgo.net/en](https://visualgo.net/en)

## Complexity of an algorithm

[https://codility.com/media/train/1-TimeComplexity.pdf](https://codility.com/media/train/1-TimeComplexity.pdf)

### Asymptotic notation

The most well-known one is `Big-O notation`:

> In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

It describes upper bound of time/space complexity of an algorithm.

There are similar notations:

* big-Omega, for lower bound
* big-Theta, for both lower bound and upper bound

Short Explanation: [https://stackoverflow.com/questions/10376740/what-exactly-does-big-Ө-notation-represent](https://stackoverflow.com/questions/10376740/what-exactly-does-big-Ө-notation-represent)

Long Explanation: [https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation](https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation)

More Explanation:

* [http://discrete.gr/complexity/](http://discrete.gr/complexity/)

[Big-O cheatsheet of common algorithms](http://bigocheatsheet.com/)

## Exercises

### Sorting

* Take a set of 10 numbers in random and write code to sort these numbers using selection sort. Write another program to sort this list of 10 numbers using merge sort. If that's too easy for you, implement [quick sort](http://www.sorting-algorithms.com/quick-sort)

Sample list of numbers \(7, 5, 34, 565, 232, 9, 0, 342, 31, 1411\)

### Searching

* Create a binary search tree and given any list of 10 numbers and an input. The program should be able to tell if the number exists in the original list given. Number list \(7, 5, 34, 565, 232, 9, 0, 342, 31, 1411\) First input 232, Second input 99
* Implement breath first search, depth first search on a binary tree. Hint: you can implement breath first search using a queue, and implement depth first search using a stack.

More Exercises

* [https://app.codility.com/programmers/lessons/1-iterations/](https://app.codility.com/programmers/lessons/1-iterations/)
* [https://github.com/Vintharas/AlgorithmsAndDataStructuresInJavaScript](https://github.com/Vintharas/AlgorithmsAndDataStructuresInJavaScript)

## jumpstart-2 algos learning roadmap

* What are algorithms
* Recursion
  * `countdown(n)`
  * `recursiveSum(n)`
  * `factorial(n)`
  * `isPalindrome(str)`
* binary search \(vs. simple search\)
  * `binarySearch(sortedArr, target)`
  * intro to big O notation - O\(n\) and O\(log n\)
* Sorting
  * selection sort \([video](https://www.youtube.com/watch?v=alh3Jme9LZs&list=PLtkAfVCgA693fNJCZkdFqs0awgynxmcAa&index=21)\)

## Resources

### Tutorials

* [How you can change the world by learning Data Structures and Algorithms](https://adrianmejia.com/blog/2018/04/04/how-you-can-change-the-world-learning-data-structures-algorithms-free-online-course-tutorial/)
* [An intuitive introduction to algorithmic efficiency](https://www.youtube.com/watch?v=u2iHB2vv3iE)

### Books

* [Grokking Algorithms](https://www.safaribooksonline.com/library/view/grokking-algorithms-an/9781617292231/)
  * [Borrow it from Singapore National Library](http://catalogue.nlb.gov.sg/cgi-bin/spydus.exe/ENQ/EXPNOS/BIBENQ?BRN=202639138)
* [Once Upon an Algorithm: How Stories Explain Computing \(MIT Press\)](https://www.amazon.com/dp/0262036630/ref=sspa_dk_detail_1?psc=1&pd_rd_i=0262036630&pd_rd_wg=D357m&pd_rd_r=EJG8XZTGAQ0GWKGQD2RR&pd_rd_w=gRut9)
* [Algorithms Illuminated: Part 1: The Basics](https://www.amazon.com/Algorithms-Illuminated-Part-1-Basics/dp/0999282905/ref=pd_sim_14_3?_encoding=UTF8&pd_rd_i=0999282905&pd_rd_r=0HDQ0MZRR3JNBDSP2BXD&pd_rd_w=dAcRb&pd_rd_wg=vqrpV&psc=1&refRID=0HDQ0MZRR3JNBDSP2BXD)
* [Real-World Algorithms: A Beginner's Guide \(MIT Press\)](https://www.amazon.com/Real-World-Algorithms-Beginners-Guide-Press/dp/0262035707/ref=pd_sim_14_5?_encoding=UTF8&pd_rd_i=0262035707&pd_rd_r=0HDQ0MZRR3JNBDSP2BXD&pd_rd_w=dAcRb&pd_rd_wg=vqrpV&psc=1&refRID=0HDQ0MZRR3JNBDSP2BXD)
* [The algorithm design manual](https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202)
* [Algorithms, by Jeff Erickson](http://jeffe.cs.illinois.edu/teaching/algorithms/)
* [Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne](https://algs4.cs.princeton.edu/home/)

### Courses

[https://www.khanacademy.org/computing/computer-science/algorithms](https://www.khanacademy.org/computing/computer-science/algorithms) [https://www.manning.com/livevideo/algorithms-in-motion](https://www.manning.com/livevideo/algorithms-in-motion)

