Problems Base course RU

Solves

estimation

Articles

GRA Technique Storing a graph Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply.

neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists

2 problems TEC Technique Big O How work grows with the data: O, Ω and Θ, rules for estimating code, and where asymptotics mislead. estimated from the program text 1 problem TEC Technique How to benchmark honestly Repetitions, warm-up, median and minimum, timeit and testing.Benchmark—and the usual ways to fool yourself with a measurement. enough repetitions for a series to take at least a tenth of a second 1 problem TEC Technique Complexity from measurements The growth of running time from measurements: the slope, the ratio test, exponentials, and where measurement lies. O(B) per attempt 1 problem

Problems

Is there such a street piece Size the filter A verdict from measurements How many schemata survive The k-th root Cache misses How many times the line runs

Often together

interviews 4 measurement 3 classic 2 in production 2 graph 1 matrix 1 array 1 hash table 1 cache-friendly 1 maps and navigation 1 contests 1 sorting 1