Defining Greedy Algorithm

An algorithm is called greedy if it follows the problem-solving heuristic of making the locally optimal choice at each stage with the aim of finding a global optimum.

In most situations, a greedy strategy does not lead to the optimal solution. Hence, it is extremely important to reason about the correctness of the greedy strategy before using it to solve a problem.

Problem 1: Too much to do!

Let's say you have to maximise the number of tasks that you complete in a 10-hour duration. You are given an array T = [2, 4, 1, 6] where T_i denotes the time required to complete the i^th task.

The answer to this question would be 3 as you would choose to do tasks T₂, T₀ and T₁ — which take 1, 2 and 4 hours respect...

The motivation for binary indexed trees is similar to that of segment trees. However, note that segment trees are much more flexible than binary indexed trees, and usually its true that any problem that can be solved with BIT can be solved with segment trees but not the other way around.

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.

Video for concept and walkthrough

First, let's watch a slow-paced easy-to-follow walkthrough of the breadth-first search and depth-first search algorithms.

A sequence (array) is really just a function which associates integers (indices) with the corresponding values. However, there is no reason to restrict our usage of binary search to tangible sequences. In fact, we can use the same algorithm described above on any monotonic function f. ... The only difference is that we replace an array lookup with a function evaluation: we are now looking for some x such that f(x) is equal to the target value.

Source: TopCoder

Example

Problem: Given a perfect square S (such as 16129 = 127 * 127) between 1 and 10 ** 6, find its square root (assuming you don't know how to calculate the square root).

Solution: Since the square is between 1 and 10 ** 6,...

This is a very comprehensive 94-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc.

The primary objectives of this course are to learn about 30 different algorithms and data structures. The algorithm tutori...

I recommend watching the following videos for learning about graphs. These are really well made videos and he covers a lot in these short videos, so if you feel overwhelmed, use the rewind and pause buttons.

Introduction to Graphs

What are graphs? What are different types of graphs (directed and undirected, trees and DAGs, etc)? And examples of using them to model web links, flights between cities, and other things.