Application: Garbage collector Mark-sweep algorithm. [McCarthy, 19601 Mark: mark all reachable objects Sweep: if object is unmarked, it is garbage(so add to free list) Memory cost. Uses 1 extra mark bit per object (plus DES stack) DFS needs o() space 9 How to do Mark-sweep with 00) space? 2/3/2021Application: Garbage collector Mark-sweep algorithm. [McCarthy, 1960] •Mark: mark all reachable objects. •Sweep: if object is unmarked, it is garbage (so add to free list). Memory cost. Uses 1 extra mark bit per object (plus DFS stack). roots 2/3/2021 Xiaojuan Cai 34 DFS needs O(|V|) space. How to do Mark-sweep with O(1) space?