Skip to the content ForoHackers
Log inJoin

Algorithms: start here

Algorithms
#3395 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply