# DS-563/CS-543: Self–Assessment Questionnaire (Fall 2021)

The Purpose: The goal of this self–assessment questionnaire is to help students considering enrolling in Algorithmic Techniques for Taming Big Data (DS-563/CS-543, Fall 2021) evaluate their preparation for the course and help them identify areas that may require additional self–study. This questionnaire is not meant to be exhaustive. See the main course website for more information, including the full course prerequisites. If you have any questions, please contact the course instructor.

## Programming

• Do you know how to write simple programs?
• Can you write a program that reads a database of dates of birth and salaries represented as a text file, in which each line is of the form "name;date of birth;salary"? The program should create an appropriate representation of the database in memory. Sample input file:
Alice;1991-09-01;$123456.78 Bob;1993-09-03;$98765.43
• Can you write a program that simulates tossing a biased coin 10,000 times and reports 10 most common subsequences of five consecutive coin tosses?

## Algorithms

• What is binary search?
• What are (balanced) binary search trees?
• How much time does it take to sort a sequence of $n$ real numbers?
• What is Depth–First Search and Breadth–First Search?
• What are hash tables?
• What is the Minimum Spanning Tree problem? How to solve it efficiently?

## Mathematics

• Can you conduct simple mathematical proofs?
• What is the rank of a matrix? What is the rank of this matrix? $$\begin{pmatrix}3&2&-1&5&3\\0&11&3&1&1\\-6&7&5&-9&-5\\0&9&4&-4&0\end{pmatrix}$$
• What is the dot product of two vectors?
• Do you know (and can prove) Markov's inequality?
• Do you know (and can prove) Chebyshev's inequality?
• If $X$ and $Y$ are random real variables, when does $E[X+Y] = E[X] + E[Y]$?
• If $X$ and $Y$ are random real variables, when does $E[X\cdot Y] = E[X] \cdot E[Y]$?