TopCoder Tutorials

A series of interesting tutorials from TopCoder that are educational and fun.

TopCoder Software Development Tutorials

Also, I’ve found these high-level Wikipedia articles to be useful review.

Wikipedia Algorithms Overview

Wikipedia Analysis of Algorithms

Wikipedia Big O Notation

Wikipedia Computational Complexity Theory

Wikipedia NP-complete

From the Wikipedia Big O notation page, this handy table:

 

Notation Name Example
O(1)\, constant Determining if a number is even or odd; using a constant-size lookup table or hash table
O(\log \log n)\, double logarithmic Finding an item using interpolation search in a sorted array of uniformly distributed values.
O(\log n)\, logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.
O(n^c),\;0<c<1 fractional power Searching in a kd-tree
O(n)\, linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
O(n\log n)=O(\log n!)\, linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
O(n^2)\, quadratic Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
O(n^c),\;c>1 polynomial or algebraic Tree-adjoining grammar parsing; maximum matching for bipartite graphs
L_n[\alpha,c],\;0 < \alpha < 1=\,
e^{(c+o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}
L-notation or sub-exponential Factoring a number using the quadratic sieve or number field sieve
O(c^n),\;c>1 exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
O(n!)\, factorial Solving the traveling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors.
Advertisements

About Chris Russell

http://www.chrisrussell.net
This entry was posted in Software. Bookmark the permalink.

2 Responses to TopCoder Tutorials

  1. URL says:

    I actually like reading by means of and I feel this site got some genuinely utilitarian stuff on it! . 999224

  2. Pingback: URL

Comment on this article

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s