da5003_2026T2_ET_FN.pdf

Algorithms for Data Science · End Term · May 2026 FN

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 2 MCQ · 0.0 marks

**(BONUS Question)** Consider a non-zero data-matrix [[IMAGE:890f6ae3fdc6a60c_2_2]] of shape [[IMAGE:890f6ae3fdc6a60c_2_3]] that is invertible. Which of the following is true? [[IMAGE:890f6ae3fdc6a60c_2_4]] denotes the spectral norm.

[[IMAGE:890f6ae3fdc6a60c_2_5]]
[[IMAGE:890f6ae3fdc6a60c_2_6]]
[[IMAGE:890f6ae3fdc6a60c_2_7]]
[[IMAGE:890f6ae3fdc6a60c_2_8]]

A published solution is not available for this question yet.

Question 3 MCQ · 2.0 marks

Is the following statement true or false? Using the uniform convergence theorem for finite hypothesis classes, one can conclude that the train error is a good proxy for the Bayes' error for very large datasets, for every finite hypothesis class.

True
False

A published solution is not available for this question yet.

Question 4 MCQ · 2.0 marks

Is the given statement true or false? Given a desired utility and privacy, the number of users who need to be surveyed is quadratically smaller in the case of the randomized response mechanism than for the Laplace mechanism.

True
False

A published solution is not available for this question yet.

Question 5 MCQ · 2.0 marks

In the context of a binary classification problem with an underlying joint distribution [[IMAGE:890f6ae3fdc6a60c_3_9]] over features and labels, let [[IMAGE:890f6ae3fdc6a60c_3_10]] be a dataset of [[IMAGE:890f6ae3fdc6a60c_3_11]] points. If [[IMAGE:890f6ae3fdc6a60c_3_12]] denotes the Bayes' error and [[IMAGE:890f6ae3fdc6a60c_3_13]] denotes the train error of some classifier [[IMAGE:890f6ae3fdc6a60c_3_14]] , and [[IMAGE:890f6ae3fdc6a60c_3_15]] is the set of all binary classifiers, which of the following is true?

[[IMAGE:890f6ae3fdc6a60c_3_16]] for all [[IMAGE:890f6ae3fdc6a60c_3_17]]
[[IMAGE:890f6ae3fdc6a60c_3_18]] for all [[IMAGE:890f6ae3fdc6a60c_3_19]]
There is at least one classifier [[IMAGE:890f6ae3fdc6a60c_3_20]] such that [[IMAGE:890f6ae3fdc6a60c_3_21]]
There is no classifier [[IMAGE:890f6ae3fdc6a60c_3_22]] such that [[IMAGE:890f6ae3fdc6a60c_3_23]]

A published solution is not available for this question yet.

Question 6 MCQ · 2.0 marks

Let [[IMAGE:890f6ae3fdc6a60c_4_24]] be the Laplacian of a graph [[IMAGE:890f6ae3fdc6a60c_4_25]] with non-negative edge weights. If [[IMAGE:890f6ae3fdc6a60c_4_26]] and [[IMAGE:890f6ae3fdc6a60c_4_27]] , which of the following is true?

[[IMAGE:890f6ae3fdc6a60c_4_28]] for all [[IMAGE:890f6ae3fdc6a60c_4_29]]
[[IMAGE:890f6ae3fdc6a60c_4_30]] for all [[IMAGE:890f6ae3fdc6a60c_4_31]]
[[IMAGE:890f6ae3fdc6a60c_4_32]] for all [[IMAGE:890f6ae3fdc6a60c_4_33]]
There exists some [[IMAGE:890f6ae3fdc6a60c_4_34]] such that [[IMAGE:890f6ae3fdc6a60c_4_35]] and [[IMAGE:890f6ae3fdc6a60c_4_36]]

A published solution is not available for this question yet.

Question 7 MSQ · 3.0 marks

Let [[IMAGE:890f6ae3fdc6a60c_4_37]] be a finite hypothesis class in a binary classification problem and let [[IMAGE:890f6ae3fdc6a60c_4_38]] be a dataset of [[IMAGE:890f6ae3fdc6a60c_4_39]] points sampled from the underlying joint distribution [[IMAGE:890f6ae3fdc6a60c_4_40]] . Let [[IMAGE:890f6ae3fdc6a60c_4_41]] be a hypothesis trained deterministically on [[IMAGE:890f6ae3fdc6a60c_4_42]] . Consider the following events for some [[IMAGE:890f6ae3fdc6a60c_4_43]] [[IMAGE:890f6ae3fdc6a60c_4_44]] Which of the following is/are true?

[[IMAGE:890f6ae3fdc6a60c_4_45]]
[[IMAGE:890f6ae3fdc6a60c_4_46]]
[[IMAGE:890f6ae3fdc6a60c_4_47]]
[[IMAGE:890f6ae3fdc6a60c_5_48]]

A published solution is not available for this question yet.

Question 8 MSQ · 2.0 marks

Which of the following hypothesis classes have finite VC dimensions? The feature space is [[IMAGE:890f6ae3fdc6a60c_5_49]] and all classifiers in the options are from [[IMAGE:890f6ae3fdc6a60c_5_50]] to [[IMAGE:890f6ae3fdc6a60c_5_51]] .

The set of all decision trees classifiers, where each tree can be trained to arbitrary depth.
The set of all functions from [[IMAGE:890f6ae3fdc6a60c_5_52]] to [[IMAGE:890f6ae3fdc6a60c_5_53]] .
The set of all linear classifiers.
The set of all classifiers whose decision boundary is a circle centered at the origin.

A published solution is not available for this question yet.

Question 9 MSQ · 2.0 marks

Consider a survey of [[IMAGE:890f6ae3fdc6a60c_5_54]] users of a product. The users respond to the survey by saying "Yes" (1) if they find the product useful and "No" (0) if they don't. The trusted curator of the survey uses the Laplace mechanism with the average function to ensure privacy even while he publishes a report on the usefulness of the product. Which of the following is/are true?

The curator outputs the exact average value of the inputs he receives from the users.
The curator outputs a noisy version of the average value of the inputs he receives from the users.
The curator is given a randomized version of the users' data.
The curator is given the users' data exactly without any randomization.

A published solution is not available for this question yet.

Question 10 MSQ · 2.0 marks

Consider a dataset [[IMAGE:890f6ae3fdc6a60c_6_55]] of [[IMAGE:890f6ae3fdc6a60c_6_56]] data-points in [[IMAGE:890f6ae3fdc6a60c_6_57]] . Given [[IMAGE:890f6ae3fdc6a60c_6_58]] , let [[IMAGE:890f6ae3fdc6a60c_6_59]] be a linear map from [[IMAGE:890f6ae3fdc6a60c_6_60]] , a linear, approximate isometry as guaranteed by the JL lemma, with [[IMAGE:890f6ae3fdc6a60c_6_61]] . Which of the following is/are true?

[[IMAGE:890f6ae3fdc6a60c_6_62]]
[[IMAGE:890f6ae3fdc6a60c_6_63]] , for all [[IMAGE:890f6ae3fdc6a60c_6_64]] and all [[IMAGE:890f6ae3fdc6a60c_6_65]]
[[IMAGE:890f6ae3fdc6a60c_6_66]] , for all [[IMAGE:890f6ae3fdc6a60c_6_67]]
[[IMAGE:890f6ae3fdc6a60c_6_68]] , for all [[IMAGE:890f6ae3fdc6a60c_6_69]]

A published solution is not available for this question yet.

Question 11 MSQ · 1.0 marks

Which of the following pieces of information are indispensable if we need to apply Markov's inequality for a random variable? Select all that apply.

The non-negativity of the random variable.
Availability of the variance of the random variable.
Availability of the third moment of the random variable.
Availability of the expected value of the random variable.

A published solution is not available for this question yet.

Question 12 NAT · 3.0 marks

Consider a binary classification problem with features in [[IMAGE:890f6ae3fdc6a60c_6_70]] and labels in [[IMAGE:890f6ae3fdc6a60c_6_71]] . Let [[IMAGE:890f6ae3fdc6a60c_6_72]] be the hypothesis class of classifiers from [[IMAGE:890f6ae3fdc6a60c_6_73]] that predict [[IMAGE:890f6ae3fdc6a60c_6_74]] on at most [[IMAGE:890f6ae3fdc6a60c_6_75]] distinct points. Formally, let [[IMAGE:890f6ae3fdc6a60c_6_76]] , where [[IMAGE:890f6ae3fdc6a60c_7_77]] Find the VC dimension of [[IMAGE:890f6ae3fdc6a60c_7_78]] .

A published solution is not available for this question yet.

Question 13 NAT · 3.0 marks

Consider a binary classification problem with features in [[IMAGE:890f6ae3fdc6a60c_7_79]] and labels in [[IMAGE:890f6ae3fdc6a60c_7_80]] . Let [[IMAGE:890f6ae3fdc6a60c_7_81]] be a hypothesis class. [[IMAGE:890f6ae3fdc6a60c_7_82]] is defined as: [[IMAGE:890f6ae3fdc6a60c_7_83]] If [[IMAGE:890f6ae3fdc6a60c_7_84]] has a sample compression scheme of size [[IMAGE:890f6ae3fdc6a60c_7_85]] , find [[IMAGE:890f6ae3fdc6a60c_7_86]] .

A published solution is not available for this question yet.

Question 14 NAT · 3.0 marks

Students who have just received their board exam results are being surveyed about their performance. Each student has either passed or failed. The students have to reply with one of two answers to the surveyor: pass/fail. To guarantee privacy, the surveyor asks each student to follow the randomized mechanism given below: 1. Flip a fair coin. 2. If tails, respond truthfully. 3. If heads, then flip a fair coin again. Respond "pass" if heads and "fail" if tails. This randomized response mechanism is [[IMAGE:890f6ae3fdc6a60c_8_87]] -differentially private, where [[IMAGE:890f6ae3fdc6a60c_8_88]] . Enter the most appropriate integer [[IMAGE:890f6ae3fdc6a60c_8_89]] .

A published solution is not available for this question yet.

Question 15 NAT · 2.0 marks

Let [[IMAGE:890f6ae3fdc6a60c_8_90]] be a hash family that is [[IMAGE:890f6ae3fdc6a60c_8_91]] -sensitive with [[IMAGE:890f6ae3fdc6a60c_8_92]] . Let [[IMAGE:890f6ae3fdc6a60c_8_93]] be two points such that [[IMAGE:890f6ae3fdc6a60c_8_94]] . The probability that both these points are hashed to the same value by a hash function sampled from this family is at least [[IMAGE:890f6ae3fdc6a60c_8_95]] . Enter the value of [[IMAGE:890f6ae3fdc6a60c_8_96]] .

A published solution is not available for this question yet.

Question 16 MCQ · 3.0 marks

Consider a binary classification problem with labels in [[IMAGE:890f6ae3fdc6a60c_9_97]] with a single feature that can take one of three values in the set [[IMAGE:890f6ae3fdc6a60c_9_98]] . The underlying distribution, [[IMAGE:890f6ae3fdc6a60c_9_99]] , over the feature-label space is given as follows: 1. the prior probability for choosing class- [[IMAGE:890f6ae3fdc6a60c_9_100]] is given as: [[IMAGE:890f6ae3fdc6a60c_9_101]] . 2. the class conditional values for the probability mass function are given for a few values of [[IMAGE:890f6ae3fdc6a60c_9_102]] and [[IMAGE:890f6ae3fdc6a60c_9_103]] : • [[IMAGE:890f6ae3fdc6a60c_9_104]] , [[IMAGE:890f6ae3fdc6a60c_9_105]] • [[IMAGE:890f6ae3fdc6a60c_9_106]] , [[IMAGE:890f6ae3fdc6a60c_9_107]] Based on the above data, answer the given subquestions.

Find the Bayes' classifier, [[IMAGE:890f6ae3fdc6a60c_9_108]] .

[[IMAGE:890f6ae3fdc6a60c_9_109]]
[[IMAGE:890f6ae3fdc6a60c_9_110]]
[[IMAGE:890f6ae3fdc6a60c_9_111]]
[[IMAGE:890f6ae3fdc6a60c_9_112]]

A published solution is not available for this question yet.

Question 17 NAT · 3.0 marks

Compute the Bayes' error, [[IMAGE:890f6ae3fdc6a60c_10_113]] . Enter your answer correct to two decimal places.

A published solution is not available for this question yet.

Question 18 NAT · 3.0 marks

Consider a binary classification problem with features in [[IMAGE:890f6ae3fdc6a60c_10_114]] and labels in [[IMAGE:890f6ae3fdc6a60c_10_115]] . Let [[IMAGE:890f6ae3fdc6a60c_10_116]] be a hypothesis class. [[IMAGE:890f6ae3fdc6a60c_10_117]] is defined as: [[IMAGE:890f6ae3fdc6a60c_10_118]] A dataset [[IMAGE:890f6ae3fdc6a60c_10_119]] that has [[IMAGE:890f6ae3fdc6a60c_10_120]] points, where each point is a feature-label pair denoted as [[IMAGE:890f6ae3fdc6a60c_10_121]] , is given below: [[IMAGE:890f6ae3fdc6a60c_10_122]] Based on the above data, answer the given subquestions.

Find [[IMAGE:890f6ae3fdc6a60c_11_123]] . Enter your answer correct to one decimal place.