Functional Programming Principles in Scala course review

Here, I review the course “Functional Programming Principles in Scala” available at Coursera. It is offered by Professor Martin Odersky of École Polytechnique Fédérale de Lausanne (EPFL).

Continue reading

Advertisements

Topological Sorting

A topological sorting of a directed graph G is a linear ordering of its vertices such that for every directed edge u->v, u comes before v in the ordering. A topological sorting is possible if and only if the graph has no directed cycles i.e., it is a Directed Acyclic Graph (DAG). It is always possible to find a topological order for a DAG and this can be done in linear time.

Continue reading

Kadane’s Algorithm

Here, I describe variants of Kadane’s algorithm to solve the maximum subarray and the minimum subarray problems. The maximum subarray problem is to find the contiguous subarray having the largest sum. Likewise, the minimum subarray problem is to find the contiguous subarray having the smallest sum. Variants of Kadane’s algorithm can solve these problems in O(N) time.

Continue reading