\documentclass{beamer}[10pt]
\usepackage{beamerthemesplit}
\usetheme{Warsaw}
\usepackage{color}
\usepackage{fontspec}
\setmainfont[Script=Devanagari]{Sanskrit 2003}

\newfontfamily \dv[Script=Devanagari]{Sanskrit 2003}

\title{\textcolor{yellow}{Algorithms in Ancient India}}
\author{Amba Kulkarni}
\institute{ Department of Sanskrit Studies\\ University of Hyderabad}
\date{5th February 2018}

\begin{document}
\setbeamertemplate{footline}[frame number]
%===================================slide 1=========================%
\begin{frame}

\titlepage

\end{frame}
%============================================================%
\begin{frame}
\frametitle{Algorithm}
Algorithm: Step-by-step procedure to accomplish a certain task
\vspace{0.5cm}
Origin of the word, attributed to\\
Muḥammad ibn Mūsā al-Khwārizmī (9th century Persian Mathematician)
\end{frame}
%============================================================%
\begin{frame}
Al Khwarizmi wrote 'On the Calculation with Hindu Numerals' around 825 AD\\
About the Hindu–Arabic numeral system \\
spread throughout the Middle East and Europe.\\
\vspace{0.5cm}
It was translated into Latin as ``Algoritmi de numero Indorum''. \\
Al-Khwārizmī, rendered as (Latin) Algoritmi, led to the term ``algorithm''.
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Characterisation of an algorithm}
Knuth (1968, 1973) has given a list of five properties as requirements for an algorithm:
\begin{itemize}
\item Finiteness: An algorithm must always terminate after a finite number of steps
\item Definiteness: Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case
\item Input: quantities which are given to it initially before the algorithm begins. These inputs are taken from specified sets of objects
\item Output: quantities which have a specified relation to the inputs
\item Effectiveness: all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil
\end{itemize}
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Euclid's algorithm}
One of the oldest Algorithms: Euclid's Algorithm for computing GCD\\
Euclid's Elements (circa 400 BC)\\
\vspace{0.5cm}
$r_{k-2} = r_{k-1} + r_{k}$\\
\vspace{0.5cm}
$a = b+r_{0}$\\
$b = r_{0}+r_{1}$\\
$r_{0} = r_{1}+r_{2}$\\
.\\.\\.\\
$r_{n-2} = r_{n-1}+r_{n}$\\

When $r_{n} = 0$, $r_{n-1}$ is the GCD of $a$ and $b$
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Euclid's algorithm: An Example}
Find GCD of 21 and 35\\
35 = 21 + 14\\
21 = 14 + 7\\
14 = 7 + 7\\
7 = 7 + 0\\
GCD = 7\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Euclid's algorithm}
Better algorithm\\
\vspace{0.5cm}
$r_{k-2} = q_{k}r_{k-1} + r_{k}$\\
\vspace{0.5cm}
$a = q_{0}b+r_{0}$\\
$b = q_{1}r_{0}+r_{1}$\\
$r_{0} = q_{2}r_{1}+r_{2}$\\
.\\.\\.\\
$r_{n-2} = q_{n}r_{n-1}+r_{n}$\\

When $r_{n} = 0$, $r_{n-1}$ is the GCD of $a$ and $b$
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Euclid's algorithm: An Example}
Find GCD of 21 and 35\\
35 = 1* 21 + 14\\
21 = 1* 14 + 7\\
14 = 2* 7 + 0\\

GCD = 7\\
\end{frame}
%============================================================%
\begin{frame}
\frametitle{Euclid's algorithm: An Example}
\begin{itemize}
\item Finiteness: Algorithm terminates in finite steps
\item Definiteness: Each step is precisely defined.
\item Input: Two non-negative numbers
\item Output: A non-negative number which is GCD of the given input
\item Effectiveness: Each step can be effectively done with paper and pencil
\end{itemize}

\end{frame}
%%============================================================%
%\begin{frame}[fragile]
%%While using verbatim mode, we need to add fragile to frame !
%Recursive version (An OCaml code)\\
%Subtraction\\
%\begin{verbatim}
%let rec gcd a b =
%  if a > b then gcd (a-b) b
%  else if b > a then gcd a (b-a)
%  else a
%  ;;
%\end{verbatim}
%\end{frame}
%%============================================================%
%\begin{frame}[fragile]
%%While using verbatim mode, we need to add fragile to frame !
%Recursive version (An OCaml code)\\
%Modulo division\\
%\begin{verbatim}
%let rec gcd a b =
%    if b = 0 then a 
%    else gcd b (a mod b)
%;;
%\end{verbatim}
%\end{frame}
%%============================================================%
\end{document}