Week 6 - Part1: Sorting Algorithms, Bubble Sort, Selection Sort

--
## Sorting Algorithms

--
**Problem** given a collection of **n** elements, it is required to sort the elements in ascending order.

--
* **Example** the following arbitrary array:

| 1 | 9 | 4 | 7 | 3 |

--
* After applying sorting in ascending order will result as:

| 1 | 3 | 4 | 7 | 9 |

---
### Bubble Sort

--
#### Visualized Bubble Sort 1

---
#### Visualized Bubble Sort 2

<img src="/gallery/Bubble-sort-example-300px.gif">
> Credits: [CC BY-SA 3.0](https://commons.wikimedia.org/w/index.php?title=User:Swfung8&action=edit&redlink=1)

---
#### Implementation

```c++
#include <algorithm>
// A function to implement bubble sort
void bubbleSort( int *array, int size )
{
    for ( int i = 0; i < size-1; i++ )
    {
        for ( int j = 0; j < size-1; j++ )
        {
            if ( array[j] > arr[j+1])
                std::swap( array[j] , array[j+1] );
        }
    }
}
```

---
#### Complexity Analysis

```c++
#include <algorithm>
// A function to implement bubble sort
void bubbleSort( int *array, int size )
{
    for ( int i = 0; i < size-1; i++ ) // T1 = n * T2
    {
        for ( int j = 0; j < size-1; j++ ) T2 = n * T3
        {
            if ( array[j] > arr[j+1] ) // T3 = 1
                std::swap( array[j] , array[j+1] );
        }
    }
}
```

--
$ T(n) = T_1 = n \times T_2 = n \times n = n^2 $

--
$ O(T(n)) = O(n^2) $

---
### Selection Sort

--
<img src="/gallery/selectionsort.gif">
> credits: [GNU license](https://en.wikipedia.org/wiki/Joestape89)

---
#### Implementation

--
```c++
#include <algorithm>
void selectionSort( int *array , int size )
{
    // One by one move boundary of unsorted subarray
    for (int i = 0; i < size -1; i++)
    {
        // Find the minimum element in unsorted array
        int min_idx = i;

for (int j = i+1; j < size ; j++)
        {
            if ( array[j] < array[min_idx] )
                min_idx = j;
        }

// Swap the found minimum element with the first element
        std::swap( array[min_idx] ,  array[i] );
    }
}
```

---
#### Complexity Analysis

```c++
#include <algorithm>
void selectionSort( int *array , int size )
{
    // One by one move boundary of unsorted subarray
    for (int i = 0; i < size -1; i++) // T1 = n * ( T2 + T3 + T4 )
    {
        // Find the minimum element in unsorted array
        int min_idx = i; // T2 = 1

for (int j = i+1; j < size ; j++) // T3 = O(n)
        {
            if ( array[j] < array[min_idx] )
                min_idx = j;
        }

// Swap the found minimum element with the first element
        std::swap( array[min_idx] ,  array[i] ); // T4 = 1
    }
}
```

--
$ T(n) = T_1 = n \times (T_2 + T_3 + T_4) = n \times( O(n) + 2 ) $

--
$ O(T(n)) = O(n^2)$

---
### Why Sorting Algorithms

--
Thoughts about the importance of sorting algorithm.

---
<span class='quora-content-embed' data-name='What-are-the-uses-of-different-sorting-algorithms-like-bubble-selection-insertion-shell-merge-heap-quick-tree-radix-counting-and-bucket-sort-in-real-life-scenarios/answer/Arundhati-Kanungo'>Read <a class='quora-content-link' data-width='560' data-height='260' href='https://www.quora.com/What-are-the-uses-of-different-sorting-algorithms-like-bubble-selection-insertion-shell-merge-heap-quick-tree-radix-counting-and-bucket-sort-in-real-life-scenarios/answer/Arundhati-Kanungo' data-type='answer' data-id='24461889' data-key='a102aaed07458fee9dd204c2ae2b57fc' load-full-answer='False' data-embed='egnuzjm'><a href='https://www.quora.com/Arundhati-Kanungo'>Arundhati Kanungo</a>'s <a href='/What-are-the-uses-of-different-sorting-algorithms-like-bubble-selection-insertion-shell-merge-heap-quick-tree-radix-counting-and-bucket-sort-in-real-life-scenarios#ans24461889'>answer</a> to <a href='/What-are-the-uses-of-different-sorting-algorithms-like-bubble-selection-insertion-shell-merge-heap-quick-tree-radix-counting-and-bucket-sort-in-real-life-scenarios' ref='canonical'><span class="rendered_qtext">What are the uses of different sorting algorithms like bubble, selection, insertion, shell, merge, heap, quick, tree, radix, counting and bucket sort in real-life scenarios?</span></a></a> on <a href='https://www.quora.com'>Quora</a><script type="text/javascript" src="https://www.quora.com/widgets/content"></script></span>

---
#### Searching

--
<img src="/gallery/binary-and-linear-search-animations.gif">

---
#### Closest Pair

##### Application 1: Gene Expression Clustering

[{Gene expression profiling}](https://en.wikipedia.org/wiki/Gene_expression_profiling)

---
#### Cont'd

* [{How does gene expression clustering work?}](https://www.nature.com/articles/nbt1205-1499)

---
##### Application 2: Tree of Life (Evolutionary Bioinformatics)

--
[{Interactive Tree of Life (iTOL)}](https://itol.embl.de/itol.cgi)

---
## Resources: Textbooks and MOOCs

* References are not meant to teach C++.
* Use references to revise particular conecpts.
* Learn by practicing, and only practicing.

---
### Data Structures and Algorithms (Theory)

--
#### Reference 1: Algorithms, *by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani*

--
<img src="/gallery/algobook.png" style="width:60%">

--
Intuitive, informal language

--
* [{Amazon}](https://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402)
* [{Goodreads}](https://www.goodreads.com/book/show/138563.Algorithms)

---
##### Chapter 10: Quantum algorithms?

---
#### Reference 2: Introduction to Algorithms, *by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein*

--
<img src="/gallery/cormen.png" style="width:60%">

* [{Amazon}](https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844)
* [{Goodreads}](https://www.goodreads.com/book/show/108986.Introduction_to_Algorithms)
* [{PDF}](http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf)

---
### C++

--
#### Reference 1: C++ Primer, *by Stanley B. Lippman, Josée Lajoie, Barbara E. Moo*

--
<img src="/gallery/lippman.png" style="width:60%">

--
* [{Amazon}](https://www.amazon.com/Primer-5th-Edition-Stanley-Lippman/dp/0321714113)
* [{Goodreads}](https://www.goodreads.com/book/show/768080.C_Primer)

---
## Summer's TODO-list

--
### Online Courses

--
#### Specialization 1:[Bioinformatics Algorithms Specialization](https://www.coursera.org/specializations/bioinformatics)

--
<img src="/gallery/UCSanDiego-Coursera-wide.png">

--
1. Finding Hidden Messages in DNA (Bioinformatics I)
2. Genome Sequencing (Bioinformatics II)
3. Comparing Genes, Proteins, and Genomes (Bioinformatics III)
4. Molecular Evolution (Bioinformatics IV)
5. Genomic Data Science and Clustering (Bioinformatics V)
6. Finding Mutations in DNA and Proteins (Bioinformatics VI)
7. Bioinformatics Capstone: Big Data in Biology

---
**Introductory Video**

---
##### Accompanied Competitive Bioinformatics Challenges

--
[Rosalind.info](http://rosalind.info/problems/locations/)

--
[Some C++ Implementations of Bioinformatics Algorithms](https://github.com/A-Alaa/rosalind-cpp)

---
#### Specialization 2: [Data Structures and Algorithms](https://www.coursera.org/specializations/data-structures-algorithms)

--
<img src="/gallery/UCSanDiego-Coursera-wide.png">

---
### Report: Big-Oh Notation

--
#### Requirements

--
1. **Use your own words**.
2. Markdown Syntax.
3. Graphs, equations, code snippets, reasoning.
4. Pull request to upload your report on the website.

--
**Deadline 5 April (After Midterms Week)**

---
### The Final Project

--
#### 1. Decide your Topic of Interest

--
Read on the web an interesting topic of your choice. For example, you may read about applications in the following domains:

--
* Supervised Classification Systems

--
* Unsupervised Classification Systems

--
* Computer Vision

--
* Bioinformatics and Molecular Biology

--
* Discuss the topic of interest with your TA. 
* how to set a plan and proceed in your project.

---
#### 2. Determine the Extra Features you Like to Integrate

--
Also, discuss with your teammates whether you would need an extra feature/technique to learn that should be integrated into your application in order to be more interesting. If you think your project will be distributed accross multiple files and applications, you may ask your TA about using *Build Systems* like *CMake*. Also, if you are interested to develop a simple Graphical User Interface (GUI) for your project, consult your TA to organize extra sessions for teaching:

--
* **Qt**,
* more on **OOP**,
* **QObjects**,
* Qt's **Singal and Slots**,
* **Qt Designer**

---
#### 3. Iterative Plans with Your TA

--
Each group is **recommended** to organize weekly meeting with the TA to discuss issues and the recent progress of the project.

---
#### 4. Extra Intensive Sessions when Necessary

--
In case of more than one group need for extra sessions, organize with your class representative to allocate suitable place for sessions.

---
#### Key Dates for the Project Planning

--
| Phase | Window |
|-------|--------|
| Topic Selection and Approval | **11/3** to **5/4** |
| Design Plan | **1/4** to  **10/4** |
| Extra Features Plans | **5/4** to **10/4** |
| Intensive Sessions (if needed) | **10/4** to **26/4** |
| First Prototype | **15/4** to **26/4** |
| Documentation | **22/4** to **26/4** |
| Final Output | **10/5** to **TBD** |
| Discussion | **TBD** |