What this topic covers
18 subtopics- Counting bits5
- Greedy foundations5
- XOR tricks5
- Bit masks4
- Interval scheduling4
- Two's complement4
- Bit tricks3
- Bitwise operators3
- Reachability2
- Scheduling2
- Activity selection1
- Bit manipulation1
Show all 18 subtopics
- Coin change1
- Custom ordering1
- Fractional knapsack1
- Huffman coding1
- Matching1
- Two-pass greedy1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
A greedy algorithm makes the locally best choice at each step and never reconsiders. It is fast and simple, but correct only when the problem has the greedy-choice property – which is why many questions here pair the greedy answer with a brute-force check. Bit manipulation works directly on binary representations: AND to test or clear bits, OR to set them, XOR to toggle or cancel, shifts to multiply or divide by powers of two. Numbers are drawn in binary where it helps.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
Activities (start, finish): (1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16). One room; an activity may start when the previous one finishes. What is the maximum number of activities?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
Always pick the compatible activity that finishes earliest: (1, 4), (5, 7), (8, 11), (12, 16). Finishing early leaves the most room for the rest – an exchange argument proves it optimal.
Characters a–f have frequencies 5, 9, 12, 13, 16, 45. Huffman coding repeatedly merges the two least frequent nodes. How many bits does the encoded text take in total?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
Merges: 5 + 9 = 14, 12 + 13 = 25, 14 + 16 = 30, 25 + 30 = 55, 45 + 55 = 100. The total cost is the sum of the merged weights: 14 + 25 + 30 + 55 + 100 = 224 (f gets a 1-bit code, a and b 4-bit codes).
For which problems is a natural greedy algorithm guaranteed optimal? Select all that apply.
Show answer and explanation
Explanation
The first three have greedy-choice proofs. 0/1 knapsack and general coin change need dynamic programming – the counterexamples earlier in this topic show greedy failing.
Why the other options are wrong
- AFails for coins {1, 3, 4} and amount 6.
- DFails when leftover capacity is wasted (value 160 vs 220).