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

Credits: CC BY-SA 3.0

Implementation

#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

#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

credits: GNU license

Implementation

#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

#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.

Read Arundhati Kanungo's answer to 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? on Quora

Searching

Closest Pair

Application 1: Gene Expression Clustering

{Gene expression profiling}

Application 2: Tree of Life (Evolutionary Bioinformatics)

Interactive Tree of Life (iTOL)

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

Intuitive, informal language

Chapter 10: Quantum algorithms?

Quantum physics is a beautiful and mysterious theory that describes Nature in the small, at the level of elementary particles. One of the major discoveries of the nineties was that quantum computers—computers based on quantum physics principles— are radically different from those that operate according to the more familiar prin- ciples of classical physics. Surprisingly, they can be exponentially more powerful: as we shall see, quantum computers can solve FACTORING in polynomial time! As a result, in a world with quantum computers, the systems that currently safeguard business transactions on the Internet (and are based on the RSA cryptosystem) will no longer be secure.

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

C++

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

Automated Tested Exercises

Exercism.io

Soon!

Online Courses

Specialization 1:Bioinformatics Algorithms Specialization

  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

Although this Specialization centers on computational topics, you do not need to know how to program in order to complete it. If you are interested in programming, we feature an “Honors Track” (called “hacker track” in previous runs of the course). The Honors Track allows you to implement the bioinformatics algorithms that you will encounter along the way in dozens of automatically graded coding challenges. By completing the Honors Track, you will be a bioinformatics software professional!

Introductory Video

Accompanied Competitive Bioinformatics Challenges

Rosalind.info

Some C++ Implementations, by Me

Specialization 2: Data Structures and Algorithms

Contributing on This Website Using Pull Requests

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

Once you find an interesting application, discuss it 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