Skip to content
- Topological Sorting
- Topo sort arranges all vertices on a DAG in order so that for an edge from u
to v on the graph, u always lies before v in the order
- Notes
- Topo order only exists if and only the graph is a DAG
- A DAG can have many topo orders
- 2 main algorithms
- DFS (Post-order traversal)
- Kahn (based on BFS)
- Time complexity: O(V + E)
- DFS
- Save edges to graph data type
- Prepare visited and result arrays
- From the visited list, choose one unvisited vertex
- Perform DFS on it
- Add vertices where there are no adjacent and unvisited vertices to the
result array
- The topo order is in reverse order of the result array
- Kahn
- Calculate the indegree of each vertex in an indegree array
- Add vertices where indegree = 0 into zero_indegree queue
- Pop from zero_indegree, save that vertex into result array
- Decrease the indegree of adjacent vertices of the popped vertex
- Repeat from step 2 (do not add vertices that have been saved to result)
- Bit Manipulation
- Used in data compression, exclusive-or encryption, graphics, embedded
systems, networking, etc.
- 1 byte = 8 bits
- Numbers → binary representation → bits
- Characters → ASCII (Chars map to 0-255) → binary representation → bits
- Bitwise operators
- Operate on bit strings
- A = 60 (0011 1100 binary) and B = 13 (0000 1101 binary) → a bit holds a
- &
- Binary AND copies a bit to the result if it exists in both operands
- A & B = 12 (0000 1100)
- |
- Binary OR copies a bit if it exists in either operand
- A | B = 61 (0011 1101)
- ^
- Binary XOR (exclusive OR) copies the bit if it is set in one operand but
not both
- A ^ B = 49 (0011 0001)
- ~
- Binary One’s Complement flip bits
- ~A = ~(60) = (1100 0011)
- <<
- Binary Left Shift moves the left operand value by the number of bits
specified by the right operand
- Left-shifting k bits equals multiplying the bit pattern by 2^k
- A << 2 = 240 (1111 0000)
- >>
- Binary Right Shift
- Right-shifting k bits equals dividing the bit pattern by 2^k (omitting
the remainder)
- B >> 3 = 1 (0000 0001)
- Trick: find the average of two integers fast and not exceed the limit of
the int data type
- -
- Binary Two’s Complement flip bits and add 1 to the result → ~ then + 1
- -A = -60 = (1100 0011) + 1 = (1100 0100)
- Algorithms - Check if a given number x is a power of 2 - x = 2^k - Note
that the binary representation of x can only have the form 1000000… - The
binary representation of x - 1 will then be 011111… - x & (x - 1) =
000000… for x = 2^k - Note that 0 itself is not a power of 2 - Count the
number of 1’s in the binary representation of a given number x - x & (x - 1)
reduces the number of 1’s in x by 1 → keep track of that - Keep doing that
while x > 0 - Check if the ith bit is set in the binary form of a given
number x - 2^i binary representation will only have one 1 at the ith bit -
x & 2^i will yield - 0 → the ith bit is not set (0) in x - Non-zero → the
ith bit is set (1) in x - Generate all the possible subsets of a set - A bit
corresponds to an element - 1 denotes the presence of that element in the
subset, while 0 means the absence
- Find the largest power of 2 (the most significant bit in binary form), which
is less than or equal to the given number N
- N is represented in binary as 1XXXX… → the largest power of 2 is
represented as 10000…
- Idea: Transform all bits to the right of the most significant bit to 1, add
1 to the result, and shift right by 1 bit (divide by 2) to obtain the result
- Transform bits to 1 by “infecting” bits starting from the most significant
bit - N = N | (N >> 1) to copy the most significant bit to its adjacent
right side - N = N | (N >> 2) to copy the 2 rightmost set bits to their
adjacent right side - N = N | (N >> 4) - N = N | (N >> 8) → all 16
bits have been “infected” → all bits of the long data type (16 bit integer)
→ type-dependent “infection”
- Bit manipulation tricks
- Obtain binary representation of x - 1 by flipping all the bits to the right
of the rightmost 1 and also the 1
- A = 60 (0011 1100), A - 1 = 59 (0011 1011)
- The reverse is true, find x + 1 by flipping all the bits to the right of
the rightmost 0 and also the 0
- 2^k can be written as 1 << k = 1 * 2^k
- Return the rightmost 1 in binary representation of x
- x ^ (x & (x - 1))
- x & (x - 1) will have all the bits equal to x except for the rightmost 1
- The bitwise XOR with x will return the rightmost 1
- Another solution
- Return the number x with the nth bit set
- Return the number x with the nth bit unset
- Get bit at nth position
- Flip bit at nth bit
- Fast modulus divisor of power of 2 - x % 2^k = x & (2^k - 1)
- Backtracking
- Kadane’s algorithm
- Divide and Conquer
- Number Theory I
- Congruence relation: Nếu 2 số nguyên a và b cùng chia cho m và có số dư
giống nhau thì a và b gọi là đồng dư theo module m
- Tính chất modulo - Phép cộng - (a + b) mod m = ((a mod m) + (b mod m)) mod
m - Phép trừ - (a - b) mod m = ((a mod m) - (b mod m)) mod m - Phép nhân -
(a * b) mod m = ((a mod m) * (b mod m)) mod m - Phép chia - (a / b) mod m
- Bài toán minh họa
- Modular exponentiation
- Tính phần dư phép lũy thừa của a^b với module m