float('inf') represents an infinitely large number with the type float
user defined classes
sorting: define a __lt__ method. Built-in sort is guaranteed to call
__lt__.
hashing: define __eq__ and __hash__ methods.
Data structures
Linked list
List, dynamic array, fixed array
dictionary
trie
tree
graph
set
deque
algorithms
shortest path
Djikstra
A*
strongly connected components
minimum spanning tree
quicksort
quickselect, statistics.median will also find median of unsorted list
mergesort
binary search
insertion sort
topological sort
NP-complete
problems that can’t be solved efficiently; use heuristics
backtracking, simulated annealing
traveling salesman
visit each vertex once and return to starting vertex
knapsack
graph coloring
hamiltonian path
visit each vertex once
binary
negative signed integers are usually represented as two’s complement integers
the left-most bit is a negative number and the others are positive
in two’s complement, inverting bits changes the sign of the integer
~x = -(x+1)
Python uses arithmetic right shifts: the most significant bit is copied
This preserves the sign of the integer
Python will grow the integer if it detects integer overflow
In other languages, it will sometimes generate an error or it will only
keep bits that will fit
XOR: unique ability to cancel duplicate values
continually XORing a list of integers can find a single unique value in a list of duplicates
Count bits: Assuming an unsigned integer, update x &= x - 1 until x
equals zero. The number of iterations equals the number of bits. If signed
integer, switch to positive integer x = ~x + 1 and add one to the count
because we need to count the signed bit.
This runs in O(lg(n)) time, but could run faster since it skips bit
positions where the bit is zero.