language: java

install:

- sudo add-apt-repository -y ppa:ubuntu-toolchain-r/test

- sudo apt-get update -y

- sudo apt-get install -y gcc-4.8 g++-4.8

- sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-4.8 50

- sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-4.8 50

script: ./test

1. Implementations

1. [Getting started](getting-started.md)

1. [src/](src/)

1. [data/](data/)

1. [test](test)

1. Introduction to algorithms

1. [Tree](tree.md)

1. [Map](map.md): [map.cpp](src/cpp/map.cpp), [bst.cpp](src/cpp/bst.hpp)

1. [Hash map](hash-map.md): [hash_map.cpp](src/cpp/hash_map.hpp)

1. [Heap](heap.md): [Heap.java](src/java/Heap.java)

1. [Quicksort](quicksort.md): [QuickSort.java](src/java/QuickSort.java), [QuickSortTail.java](src/java/QuickSortTail.java), [HeapSort.java](src/java/HeapSort.java)

1. String algorithms

1. [Longest common subsequence](longest-common-subsequence.md)

1. [Longest increasing subsequence](longest-increasing-subsequence.md)

1. [Maximum subarray](maximum-subarray.md)

1. [String search](string-search.md): [StringSearchNaive.java](src/java/StringSearchNaive.java), [KnuthMorrisPratt.java](src/java/KnuthMorrisPratt.java)

1. Linear programming

1. [Change making](change-making.md)

1. Out-of-core

1. [tac](tac.md): [tac.c](src/c/tac.c), [Tac.java](src/java/Tac.java)

1. Misc algorithms

1. [Hanoi tower](hanoi-tower.md)

1. [XOR-swap](xor-swap.md)

1. [TODO](TODO.md)

1. [Knapsack](knapsack.md)

Algorithms that could be included:

- <http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers>

Find the missing number of an increasing sequence that has been mixed up.

E.g., start with:

1 2 3 4 5 6

Mix up:

6 3 5 4 2 1

Remove an unknown number:

6 5 4 2 1

Which number was removed?

Solution: sum up, use the sum formula, take difference.

- <http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe>

Same as above, but remove 2 numbers instead.

- <http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list>

Find the smallest non-negative integer *not* in an unsorted array of length `N`.

The array is stored in RAM.

Application: generate unique IDs in a system where any ID can be removed.

Solution intuition:

- `N` is the largest possible value in case of an increasing sequence. This means that you can throw away any number larger than `N`.

- if the array were sorted, it would be easy.

- there are non-comparison sorting algorithms for integers in a fixed range that perform $O(N)$ time $O(1)$ memory.

Solution: 2 passes, first try to put every number smaller than `N` in the array position with same value as the number. If already occupied by another number, do the same for the other number. Throw away anything larger than `N`.

- <https://en.wikipedia.org/wiki/Out-of-core_algorithm>. We currently have `tac`. Find more.

- <http://en.wikipedia.org/wiki/Partition_problem>. Partition a multiset into two sub-multisets such that the sum of each sub-multiset is equal. NP-complete.

Many not have a solution, which leads to the optimization version: minimize the difference. NP-hard.

- <http://en.wikipedia.org/wiki/Stable_marriage_problem>

- <http://en.wikipedia.org/wiki/National_Resident_Matching_Program#Matching_algorithm>

- <http://en.wikipedia.org/wiki/Stable_roommates_problem>

Some NP-complete ones:

- <http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems>

- <http://en.wikipedia.org/wiki/Vertex_cover>

- <https://github.com/vhf/free-programming-books>: huge list of free books and algorithmic problem sets

- <http://algs4.cs.princeton.edu/home/>, which has lots GPL Java source. This kind soul has put the source up on GitHub: <https://github.com/aistrate/AlgorithmsSedgewick>

- <http://www3.cs.stonybrook.edu/~algorith/>. Links to tons of open source algorithm implementations that solve many problems. Each algorithm has a rating, and algorithms are all classified.

- <http://www.geeksforgeeks.org/fundamentals-of-algorithms>

- <http://en.wikibooks.org/wiki/Algorithm_Implementation>

My favorites are:

- [TopCoder](http://www.topcoder.com/active-challenges/develop). No solutions. 6M registered users. Money prizes. Some company proposed problems have Non Disclosure Agreements. Timed submission contests.

- [HackerRank](https://www.hackerrank.com/categories/fp/intro). No solutions, 3M Round A. Timed submission contests.

- [Kaggle](https://www.kaggle.com/competitions). Data science focused. No solutions. Some problems have money prizes.

- [Sphere Online Judge (SPOJ)](http://www.spoj.com/problems/classical/all/). No solutions. 200K users, 10000 problems.

- [Project Euler](http://projecteuler.net/problems). 350K users, only ~450 problems. No solutions. Since 2001. Probably one of the oldest around, but did not evolve much.

- [UVa](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=1). 100K registered users. No solutions. Slow website.

- [CareerCup](http://www.careercup.com): Interview questions.

Yearly contests:

- [ACM International Collegiate Programming Contest](http://icpc.baylor.edu/). [Wiki](en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest). No solutions. Eligibility: less than five years of university education before the contest. Started in 1977. [World final problems](http://icpc.baylor.edu/worldfinals/problems).

- [Google Code Jam](http://code.google.com/codejam/contests.html). Only a few solutions.

- [ICFP](http://en.wikipedia.org/wiki/ICFP_Programming_Contest). One problem per year. Since 1998.

Knapsack-like problem where:

- each weight is fixed to 1

- the goal must be reached exactly

- infinite supply of items

Even the feasibility is NP-complete.

If the input set is <http://en.wikipedia.org/wiki/Superincreasing_sequence>, like the coin denomination of most countries, then the greedy algorithm works. This is why there is cannot be a 3 euro coin: otherwise 3 + 2 + 1 = 6 > 5, and change making would be NP-complete.

- [make_change.cpp](src/cpp/make_change.cpp)

- <https://web.archive.org/web/20131007212811/http://www.or.deis.unibo.it/kp/Chapter5.pdf>

Language agnostic test data.

3

1 2 0

0 1 2

4

1 3 2 0