{
 "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": [
    "Explain why selection sort is considered an *in-place* sorting algorithm? Explain in detail"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2 (2 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What input leads to the worst-case performance of the Selection Sort algorithm, and why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3 (3 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare the best-case and 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": "markdown",
   "metadata": {},
   "source": [
    "Write a Python code to count the total number of swaps made by the selection sort algorithm to sort an input array in ascending order."
   ]
  },
  {
   "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": [
    "## Analyzing complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 5 (5 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an unsorted integer array $nums$. return the smallest positive integer that is not present in $nums$. Note: 0 is not the positive integer.\n",
    "\n",
    "Input: arr[] = [2, -3, 4, 1, 1, 7]  \n",
    "Output: 3  \n",
    "Explanation: 3 is the smallest positive number missing from the array.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a. Analyze the time complexity of your algorithm using a table. \n",
    "\n",
    "Note: Include the program code you wrote for the coding homework to support your analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 6 (5 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a square matrix (list of lists), calculate the absolute difference between the sums of its diagonals.\n",
    "\n",
    "Eg:\n",
    "Input: \n",
    "mat =   \n",
    "[[11,2,4],  \n",
    "[4,5,6],  \n",
    "[10,8,-12]]    \n",
    "\n",
    "Output: 15  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a. Analyze the time complexity of your algorithm using a table. \n",
    "\n",
    "Note: Include the program code you wrote for the coding homework to support your analysis."
   ]
  }
 ],
 "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
}