Introduction

Computers can only do a limited number of operations in a given time, usually about a billion operations per second. Here, by an individual operation, we mean addition, multiplication, assigning a value to a variable, etc. Hence, if we want our algorithm to finish executing in a second or so, then we need to make sure that the total number of operations we are asking it to do is less than 1 billion.

Estimating the exact run-time of an algorithm without implementing and executing it is very tough since it depends on so many factors - including the programming language being used, the compiler, the hardware of the computer itself, and more. Instead, what we'd like to do most of the time, is to estimate the run-time approximately.

Rate of growth

In algorithms, we focus on estimating the execution ...

This discussion is for expanding your array of maneuvers needed to code quickly and efficiently.

STL:

The first and most important thing that I'd like to discuss about is the C++ STL. Learning it would enable you to code up an assortment of algorithms and complicated data structures in a matter of seconds.

You can learn to use the C++ STL from the following amazing sites:

Studytonight : Contains syntax and examples for most of the STL containers and algorithms.

Sanfoundry : Shows how to implement what you've learnt in complete programs

Topcoder(Highly recommended) : This place teaches yo...

Prerequisites: Matrix in algebra, Matrix multiplication

Introduction: Matrix Exponentiation (also known as matrix power, repeated squaring) is a technique used to solve linear recurrences. This technique is very useful in competitive programming when dealing with linear recurrences (appears along Dynamic Programming). This technique also solves a lot of problems in graph theory. Only solving recurrences is covered here, applications on graph theory will be discussed later.

This video shows how to find the n-th term of any linear recurrence relation (where n is very large ~10^18) . You should be able to understand the technique after watching these videos.

Problem : Problem SEQ

Dynamic programming is a fancy name for storing intermediate results and re-using the stored result instead of re-computing them each time.

Let's see an example of a dynamic programming problem. Once we solve the problem using dynamic programming, the formal technical definitions will be easier to follow.

Tiling problem

This tutorial understand you the Way to solve Tiling Problems .

Problem: You are given a grid of size n \times 2 and n tiles of size 2 \times 1. In how many different ways can you tile the grid such that the entire grid is covered and no tiles overlap. (The tiles look identical to each other. Two ways of tiling are different based on whether the tiles are placed horizontally or vertically).

Example: There are 3 possible ways of tiling a 3 \times 2 grid.

Tiling 1: 

Recursion is a fundamental technique used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.

In computer science, a common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is Dynamic Programming. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.

It's recommended that you learn mathematical induction before learning recursion. You can find a tutorial here:

Mathematical Induction

If you are familiar with mathematical induction, rec...

Floyd Warshall algorithm is an All-Pairs shortest path algorithm. This means it calculates the value of the shortest path between each pair of nodes in a graph.

The most important questions are:

1: What are the main differences between Floyd Warshall and Dijkstra?

• Floyd Warshall algorithm is a Dynamic Programming based algorithm. The technique used in this algorithm is known as Matrix Chain Multiplication. A shortest path between 2 nodes in a graph would be a chain of nodes.
• Floyd Warshall algorithm runs in O(V^3) where V is the number of nodes in our graph.
• Since there isn't a more efficient implementation for sparse graphs, other shortest path algorithms are often better suited for sparse graphs.

2: Why don't we make Dijkstra from each node in our ...