Work Note 8, DM546, Spring 2015

Lecture March 10

• Garbage collection.

Exercises March 13

• Appel 10.1, 10.4, 10.5.
• Estimate the asymptotic complexity of finding a fixed point as a function of the number of temporaries and the size of the control flow graph (with the lecture transparencies as the starting point). Consider the representation of sets carefully. Next, consider the complexity of building the conflict graph and the complexity of coloring by simplification, including which supporting data structures to employ.