Saltar al contenido ForoHackers

Algorithms: start here

Algoritmos
#3395 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder