{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 1 (DATS-6001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your Name: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selection Sort "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider sorting $n$ numbers stored in array $A[0:n-1]$ by first finding the smallest element of $A[0:n-1]$ and exchanging it with the element in $A[0]$. Then find the smallest element of $A[1:n-1]$, and exchange it with $A[1]$. Then find the smallest element of $A[2:n-1]$, and exchange it with $A[2]$. Continue in this manner for the first $(n-1)$ elements of $A$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 1 (2 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why does it need to run for only the first $(n-1)$ elements, rather than for all $n$ elements?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2 (2 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Describe the worst-case input for the algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3 (3 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Give the worst-case running time of selection sort in terms of the input size $n$. Try to be as thorough as possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 4 (3 points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implement the algorithm in Python\n",
    "def selection_sort(arr):\n",
    "    pass # TODO: replace this line with your code\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Median"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 5 (5 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a Python program to find the [median](https://en.wikipedia.org/wiki/Median) of two *sorted* arrays of different sizes. I am looking for not the most efficient algorithm, but something that's *correct*, *bug-free*, and *well-documented*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 6 (5 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analyze the time complexity of your algorithm using a table."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "dats-6103",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}