UROP Proceedings 2020-21

School of Engineering Department of Computer Science and Engineering 130 Parameterized Algorithms for Static Program Analysis Supervisor: KAFSHDAR GOHARSHADY Amir / CSE Student: CHENG Tien-chun / COMP Course: UROP1100, Spring Arranging frequently accessed data closely in the memory has long been considered an important program optimization. The relationship of data accesses can be model as a set of hierarchical clusters. In this article, we research an efficient algorithm to compute the data locality hierarchy parameterized by treewidth. We analyze a specific pattern of tree decomposition and perform a polynomial reduction on the parameterized problem to an NPComplete problem. We obtain a computational hardness result of measuring the closeness of two data under this hierarchical model. This result can be a major step toward proving the computational hardness of determining the closeness of a data group. Parameterized Algorithms for Static Program Analysis Supervisor: KAFSHDAR GOHARSHADY Amir / CSE Student: LAM Chun Kit / COMP Course: UROP1100, Spring In this project, we studied problems in static program analysis, trying to find useful parameterization for the problems and speedup existing algorithms. This report focuses on linearizability checking with program traces using strong d-hitting families. We proved the computation of the heuristics would take exponential time in the worse-case and devised an algorithm with slightly better upper bound on the number of generated schedules. Parameterized Algorithms for Static Program Analysis Supervisor: KAFSHDAR GOHARSHADY Amir / CSE Student: WU Zhiang / COSC Course: UROP1100, Spring Static analysis focuses on proving specific properties of a program via the argument on its code directly. Lots of problems in this field can be solved by parameterized algorithms with a better efficiency than traditional methods. In this semester, we first did a literature review on parameterized algorithm, automata on infinite words and basic model checking, then picked the numerical domain analysis which is a classical problem in static analysis to try to design a parameterized algorithm to solve it. In the end, some primal ideas were raised and we will try to solve the problem in the future.

RkJQdWJsaXNoZXIy NDk5Njg=