Skip to the content ForoHackers
Log inJoin

Algorithms: start here

Algorithms
#889 · Ophuscado · · Report

An algorithm is a finite, precise procedure that turns an input into an output. The field asks which procedures are correct, how many steps and how much memory they need as inputs grow, and whether a better one exists. It is the difference between a program that answers in a second and one that never finishes.

Key concepts

  • Correctness: a loop invariant or an induction argument shows the procedure does what it claims, on every input.
  • Asymptotic cost: big-O describes how time and space grow with input size, ignoring constants.
  • Design paradigms: divide and conquer, greedy choice, dynamic programming, backtracking, randomisation.
  • Sorting and searching: the standard problems on which every technique is first learned.
  • Worst, average and amortised cases: the same algorithm can be judged by its worst input, a typical one, or a long sequence of operations.

Vocabulary

  • Recurrence: an equation that defines the cost of a problem through the cost of smaller ones.
  • Optimal substructure: an optimal answer is built from optimal answers to subproblems.
  • Heuristic: a method with no proof of the best answer, used because it is fast and usually good.
  • Approximation ratio: how far from optimal an answer can be, guaranteed in the worst case.

What to study, in order

  1. Write binary search and insertion sort from scratch, and state their invariants.
  2. Learn big-O and solve simple recurrences, such as the one for merge sort.
  3. Implement merge sort, quicksort and heaps; count comparisons on random and adversarial inputs.
  4. Solve classic problems with dynamic programming and greedy choice, and see where greedy fails.
  5. Study graph traversals and shortest paths, then measure your code against the predicted growth.

Related tags

#data-structures #complexity #graph-theory #competitive-programming

Log in or join to reply.