Description
Show all your computation to get full credit. This is an individual project, no
groups are allowed
Consider a set of n boxes with their positions numbered from 1 to n. Initially all the boxes are CLOSED. These n boxes are subject to modi cations over n iterations as follows. At the ith iterations the boxes at the positions whose ids are multiples of i are ipped, i.e. changed from CLOSED to OPEN or vice-versa. For example, at iteration 1, boxes at all positions are ipped, at iteration 2, boxes at positions 2,4,6,etc. are ipped, at iteration 3, boxes at positions 3,6,9, etc. are ipped.
Propose an algorithm for nd out, that after n such iterations how many boxes will be OPEN. Note that the answer requires only how many boxes, not their positions. Describe the rationale for the algorithm, give the pseudocode, and its complexity. Grading scheme: (your grade will be based on whichever class your algorithm falls in)
For algorithms with complexity O(n2) or higher (5 pts)
For algorithms with complexity O(kn), where k is the number of digits of n (8 pts)
For algorithms with complexity O(M(k)), where k is the number of digits of n, and M(k) is the complexity of multiplying two k digit numbers (10 pts)
1
