School of Engineering Department of Computer Science and Engineering 114 Analysis of Hierarchical Clustering Methods Supervisor: GOLIN Mordecai Jay / CSE Student: RUBAB Tamzid Morshed / DSCT Course: UROP1100, Fall In this report, I analyze two hierarchical clustering algorithms for graphs drawn from planted partition model. In this model, nodes are divided into k clusters at first, and intra-cluster edges are added independently with some probability p and inter-cluster edges are added independently with probability q, where p > q. For the first algorithm, we assume that the partitions (clusters) are known. In this case, we can assume a generalized version of planted partition (intra-cluster probabilities can be anything larger than q). And for the second one, the partitions are unknown. The former achieves 3k−2 3k approximation and the latter asymptotically finds at least 0.5-approximation. Constructing AIFV Codes Supervisor: GOLIN Mordecai Jay / CSE Student: ZHAO Jiachen / COSC Course: UROP1100, Summer Almost Instantaneous Fixed to Variable bit delay coding, also known as AIFV-m coding, is a lossless compression method for memoryless sources. Compared to Huffman coding, it sacrifices instantaneity for better performance. Instead of constructing a single tree like Huffman coding, AIFV-m coding generates trees to encode and decode the text. To construct the optimal trees, both local optimization, aiming to build the optimal m-th tree given certain conditions, and global optimization, aiming to coordinate different trees to achieve optimal performance, are necessary. This paper introduces an implementation of a new local optimization procedure for AIFV-m coding proposed in [2], which runs in ( +2) time and ( +2) space. [2] Mordecai J. Golin and Albert John L. Patupat. “Speeding Up AIFV-m Dynamic Programs by m–1 Orders of Magnitude.” 2022 IEEE International Symposium on Information Theory (ISIT’22). 2022.
RkJQdWJsaXNoZXIy NDk5Njg=