School of Engineering Department of Computer Science and Engineering 116 Parameterized Algorithms for Static Program Analysis Supervisor: KAFSHDAR GOHARSHADY Amir / CSE Student: CHENG Tien-chun / COMP Course: UROP2100, Fall UROP3100, Spring Data locality problem is an important topic in program optimization, and the hierarchical model is one of a way we can cluster data. Previous studies have proved the hardness of a task associated with constructing the hierarchical model. In this report, we attempt to find a polynomial-time algorithm parameterized by treewidth. In light of the difficulty in finding a direct parameterized algorithm, we discuss a side approach to this problem and propose some properties about treewidth. At the end of the report, we discuss how we might utilize these properties in finding a parameterized algorithm and propose possible future work. Parameterized Algorithms for Static Program Analysis Supervisor: KAFSHDAR GOHARSHADY Amir / CSE Student: HUANG Yi-feng / COMP Course: UROP1100, Fall Static program analysis aims to evaluate the program through abstraction of the program and provide useful information about the program. Useful examples include live variables analysis, available variable expressions analysis, and flow analysis. These analyses help with improving the efficiency of the program or help verify the correctness of the program. Many of the analysis in static program analysis can be modeled by a graph. And we had learnt parameterized algorithm for graph with bounded treewidth and path width such that certain order of traversing the graph can be exploited to reduce the time complexity of the algorithm running on the graph. In this research project, we studied the parameterized algorithms and try to use parameterized algorithm in solving problems in static program analysis, and hopefully on the area of points-to analysis, which analyze the point to source and target relationship.
RkJQdWJsaXNoZXIy NDk5Njg=