import numpy as np

def genInstance(m, n, k):
    """
    Generate a random instance of a sparse linear system.

    Arguments
    ---------
    m : int
        The number of equations
    n : int
        The number of unknowns
    k : int
        The sparsity level of the solution

    Returns
    -------
    y : numpy.array
        A numpy vector containing the linear measurements
    A : numpy.array
        The generated design matrix
    x : numpy.array
        The ground truth solution
    """
    x = np.random.randn(n)
    x[np.random.choice(n, n - k, replace=False)] = 0.0
    x /= np.linalg.norm(x)
    A = np.random.randn(m, n)
    return A @ x, A, x


def project_sparse(v, k):
    """
    Project a vector `v` to the set of `k`-sparse vectors, by keeping
    the k elements with the largest magnitude and setting all others
    to 0.

    Arguments
    ---------
    v : numpy.array
        The vector to project
    k : int
        The desired sparsity level

    Returns
    -------
    numpy.array
        The projected vector with `k` nonzero elements
    """
    # TODO: Complete the code here


def iht_solve(A, y, x_0, T, eta, k):
    """
    Solve a sparse linear system using iterative hard thresholding.

    Arguments
    ---------
    A : numpy.array
        The design matrix
    y : numpy.array
        The vector of measurements
    x_0 : numpy.array
        An initial guess for the solution
    T : int
        The number of steps to run the IHT algorithm
    k : int
        The desired number of nonzero elements of the solution

    Returns
    -------
    x_T: numpy.array
        The estimate found after T iterations
    """
    for t in range(T):
        # TODO:
        # 1. Take a step in the negative gradient direction
        # 2. Project the resulting iterate to the set of k-sparse vectors
        #    (use the project_sparse() function)