This assignment is the coursework for the CSE558 Data Science course at IIIT Delhi.
The objective of this assignment is to implement various techniques in randomised algorithms, dimensionality reductions, Random Vectors and Approximations.
The assignment is divided into three main topics:
-
Hashing and Sketching: Implement and analyze different hashing strategies, including universal hashing and MD5-based functions. The aim is to compare their performance in terms of collision handling (chain lengths) and apply them to implement the Flajolet-Martin algorithm for estimating the number of unique items in a dataset.
-
Data Streaming Algorithms: Using a large transactional dataset, implement and evaluate two key streaming algorithms. The first is the Bloom Filter, where the objective is to analyze its false positive rate under various parameters. The second is the Misra-Gries algorithm, where the aim is to identify frequent items from the data stream and compare the algorithm's accuracy against the exact counts.
-
Dimensionality Reduction: Use the KDD Cup dataset to explore the effects of Johnson-Lindenstrauss (JL) random projections. The objective is to apply these projections to the data and then measure how this dimensionality reduction impacts the cost and loss of two standard machine learning tasks: k-means clustering and linear regression.
| Name | Roll Number |
|---|---|
| Anushk Kumar | 2023115 |
| Arhan Jain | 2023118 |