Q$1.$ Indicate whether the following statements are true or false, and provide one sentence reasoning for your choice.

Streaming algorithms require the entire input stream to be stored in memory for processing.

Streaming algorithms are only applicable to real$-$time data streams and cannot be used on static datasets.

Streaming algorithms can only process data in a sequential manner and cannot handle parallel processing.

Streaming algorithms always provide exact results for computations on streaming data.

Universal hashing requires the use of cryptographic hash functions.

Universal hashing guarantees that every key will be hashed to a unique location in the hash table.

Universal hashing guarantees a constant time complexity for insertion and retrieval in a hash table.

Property testing is only applicable to numerical or quantitative properties, not qualitative properties.

Property testing algorithms can handle dynamic datasets that change over time.

Property testing guarantees finding an exact solution to a problem in sublinear time.

Q$2.$ Given a data stream of integers $2,3,1,4,2,3,1,3,1,4,5,3,2,1,6.$

$[10$ marks$]$

Apply the Misra$-$Gries algorithm with a parameter $k=3$ to identify the top$-$k frequent items in the stream. Show the step$-$by$-$step process of the algorithm by drawing a table, including the initialization, updating counts, and evicting infrequent items. Finally, provide the final output of the algorithm. Discuss the benefits of using the Misra$-$Gries algorithm compared to traditional frequency counting approaches for large streams of data.

Note: Not drawing table in your solution will result in $0$ marks for this question.

Perform Reservoir Sampling to select a subset of size $5$ from the stream. Show the step$-$by$-$step process of selecting the elements and the final subset.

$[10$ marks$]$

Q$3.$ Universal hashing is important in designing solutions as it allows for efficient and effective hash$-$based data structures.

Formally define a universal one$-$way hash function family.

Provide a solution $($data structre and algorithm$)$ that utilizes such a family to speed$-$up searching keywords across a large set of text documents.

Define the properties of your solution and their relations. What are the trad$-$offs?

Why was a universal hash function family required in your solution? $($i$.$e$.$ is it not possible to use any other hash function in your method? What impact it has on your solution?$)$

$[10$ marks$]$

Q$4.$ Property testing provides a means to verify if an algorithm correctly satisfies certain properties without examining the entire input. In this question, consider property testing for an algorithm that determines whether a graph is connected or not.

Formally define the property of "connectedness" for a graph. Include the necessary conditions for a graph to be considered connected.

Describe the process and steps in which your defined property can be tested to verify if a given algorithm correctly determines the connectedness of a graph.

Assume you are given a graph represented by its adjacency matrix. Provide with an example a stepby$-$step explanation of how you would conduct the property test and determine if the algorithm passes or fails the test.

$[10$ marks$]$