Author Archives: Partha Biswas

Final review

Download article as PDF Asymptotic complexity Upper bound function Lower bound function Order function Solving recurrence equations Sorting Insertion sort – algorithm, complexity and benefits Selection sort – algorithm, complexity and benefits Quicksort – algorithm, complexity and benefits Mergesort – … Continue reading

Posted in Data-structures | Comments Off

Mergesort and Quicksort

Download article as PDF Mergesort (not an in-place sort) mergesort(a, i, j) {       if (i >= j) return;       mid = (i + j)/2;       mergesort(a, i, mid);       mergesort(a, mid + 1, j);       merge(a, i, j); } … Continue reading

Posted in Data-structures | Comments Off

Trees and Graphs

Download article as PDF Here are definitions of some of the common terms you would often encounter in the context of trees and graphs. Trees Tree: A set of nodes and edges connecting the nodes such that there is exactly … Continue reading

Posted in Data-structures | Comments Off

Midterm review

Download article as PDF Linked Lists: 1. Write an algorithm to detect a cycle in a linked list. 2. Remove consecutive duplicate entries from a given linked list. 3. Get the k-th to the last element in the linked list … Continue reading

Posted in Review | Comments Off

Growth of functions

Download article as PDF In algorithmic analysis, we learn to characterize the complexity in terms of an upper bound (Big-oh), a lower bound (Big-omega) and an order function (Big-theta). Here are the definitions: 1. Upper bound function (i.e., T(n) is … Continue reading

Posted in Data-structures | Comments Off

Debugging with Emacs

Download article as PDF Compile (say, files f1.cpp and f2.cpp) with the following command from Emacs: M-x compile <return> Compile command: g++ -o myprogram -g f1.cpp f2.cpp The presence of ‘-g’ flag tells the compiler to generate the debug symbols … Continue reading

Posted in Emacs | Comments Off

DOT Language

Download article as PDF http://en.wikipedia.org/wiki/DOT_language  

Posted in Graphviz | Comments Off

Inheritance in C++

Download article as PDF // base.h class base { public: void f1();           // f1 cannot be overwritten virtual void f2();      // f2 can be overwritten virtual void f3() = 0;  // f3 is a pure virtual function and … Continue reading

Posted in C++ | Leave a comment