CMPS 3120 Algorithm Analysis
Decrease and Conquer
Topological Sort problem: Topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies.
How can we write a program to solve it?
- Decrease by a constant
- Decrease by a constant factor
- Variable-size decrease
One-Pile Nim: There is a pile of n chips. Two players take turn by removing from the pile at least 1 and at most m chips. (The number of chips taken can vary from move to move.) The winner is the player that takes the last chip. Who wins the game – the player moving first or second, if both player make the best moves possible?