%---TeX-start-of-header---
\documentclass[titlepage]{article}
\usepackage{epsfig,mathematica,figi}
%\mmanobreak

\begin{comment}

\begin{mathematica}
<<tek.m;
\end{mathematica}

\begin{mathematica}
SetOptions["stdout", PageWidth->Infinity];
zero = 0.00001;
ohide = DisplayFunction->Identity;
oshow = DisplayFunction -> $DisplayFunction;
ojoin = PlotJoined -> True;
oall = PlotRange->All;
osurf = HiddenSurface->False;
deg = N[Degree];
pi = N[Pi];
\end{mathematica}

\begin{mathematica}
<<Miscellaneous`Units`;
\end{mathematica}

\end{comment}

\begin{document}
\psfiginit
%---TeX-end-of-header---

\author{Tomasz J.\ Cholewo}
\title{Design and Analysis of Computer Algorithms, EE619\\
Homework \#1}
\maketitle
%====================================================================
\section{Problem 1}

The three given functions: $g_1(n) = 12n^2 + 100$, $g_2(n) = 2n^2 + 100n
+ 2500$, and $g_3(n) = 15n \log_2 n + 5000$ can be written in \Mma{} as:
\begin{mathematica}
g1[n_] := 12 n^2 + 100;
g2[n_] := 2 n^2 + 100 n + 2500;
g3[n_] := 15 n Log[2, n] + 5000;
\end{mathematica}

Their plot, shown in Figure~\ref{g123}, reveals that interesting
us intersections can be found in an interval $(20,30)$.
\begin{comment}
\begin{mathematica}
Display["g123.eps", Plot[{g1[n],g2[n],g3[n]},{n, 1, 40}], "EPS"];
\end{mathematica}
\end{comment}
\figi{g123}{Functions $g_1$, $g_2$, and $g_3$.}

One can easily calculate their mutual intersections in this range using $n=20$ as a
starting point.
\begin{mathematica}
Print[FindRoot[g1[n] == g2[n], {n, 20}]];
Print[FindRoot[g1[n] == g3[n], {n, 20}]];
Print[FindRoot[g2[n] == g3[n], {n, 20}]];
.
{n -> 21.2788}
{n -> 23.2421}
{n -> 29.2561}
\end{mathematica}
From the above and from the fact that obviously $O(g_1) \geq O(g_2) \geq
O(g_3)$ one can conclude that $g_2$ becomes favorable to $g_1$ for $n >
21.2788$, that $g_3$ is smaller than $g_1$ for $n > 23.2421$ and that
$g_3$ is preferable also to $g_3$ when $n > 29.2561$.

%====================================================================
\newpage
\section{Problem 2}

Using a special function for time units conversion
\begin{mathematica}
timeunit[x_] := If[# =!= Null, #, x Second]& @
  Scan[ If[#[[1]] >= 1., Return[#]]& [Convert[x Second, #]]&,
    Reverse[{Second, Minute, Hour, Day, Week, Month, Year, Century, Millenium}]]
\end{mathematica}
the desired values supplementing Table~1.1 can be calculated by the
following single statement:
\begin{mathematica}
Print[N[(timeunit[10^-6 #]&/@{33#, 46# Log[2,#], 13#^2, 3.4#^3, 2^#})& /@
  {25, 50, 200, 500},3] //TableForm[#,TableHeadings->{{25, 50, 200,
      500}, {"33 n","46 n lg(n)","13 n^2","3.4 n^3","2^n"}}]&];
.
      33 n              46 n lg(n)       13 n^2           3.4 n^3         2^n
25    0.000825 Second   0.00534 Second   0.00813 Second   0.0531 Second   33.6 Second

50    0.00165 Second    0.013 Second     0.0325 Second    0.425 Second    35.7 Year

                                                                                43
200   0.0066 Second     0.0703 Second    0.52 Second      27.2 Second     5.1 10   Millenium

                                                                                 134
500   0.0165 Second     0.206 Second     3.25 Second      7.08 Minute     1.04 10    Millenium
\end{mathematica}
%====================================================================
%====================================================================
\newpage
\section{Problem 4 -- working version}

Function \texttt{max2} for a given list of numbers $L$ finds a list
consisting of the largest and second largest values in this list using
tournament algorithm.  Optional parameter $test$ allows showing all
comparisons performed by the algorithm and the state of loser links array.
\begin{mathematica}
max2[L_List, test_:False] :=
Module[{n, loserlist, loserlinks, tolose, i, j, loser, winner, link,
  largest, secondLargest},
  n = Length[L];
  loserlist = Table[False, {n}];
  loserlinks = Table[0, {n}];
  tolose = n;
  While[tolose > 1,
    i = 1;
    While[i < n,
      If[ !loserlist[[i]],
        For[j = i + 1, j <= n, j = j + 1,
          If[ !loserlist[[j]],
             If[ L[[i]] > L[[j]],
               winner = i; loser = j,
               winner = j; loser = i
             ];
             loserlist[[loser]] = True;
             If[ loserlinks[[winner]] != 0,
               loserlinks[[loser]] = loserlinks[[winner]]
             ];
             loserlinks[[winner]] = loser;
             largest = L[[winner]];  (* keep track of last winner *)
             If[test, Print["L[", winner, "] > L[", loser, "], ", loserlinks]];
             tolose = tolose - 1;
             i = j + 1;  (* initialize next iteration of While[i < n] *)
             Break[];
          ]
        ], (* For *)
        i = i + 1  (* else *)
      ] (* If *)
    ] (* While *)
  ]; (* While *)
  secondLargest = -Infinity;
  For[i = 1, i <= n, i = i + 1,
    link = loserlinks[[i]];
    If[link > 0 && secondLargest < L[[link]],
      secondLargest = L[[link]]
    ]
  ];
  {L[[winner]], secondLargest}
];
\end{mathematica}

\newpage
Let us try this algorithm on the example given in the textbook:
\begin{mathematica}
max2[{3, 12, 14, 10, 16, 19}, True]
.
L[2] > L[1], {0, 1, 0, 0, 0, 0}
L[3] > L[4], {0, 1, 4, 0, 0, 0}
L[6] > L[5], {0, 1, 4, 0, 0, 5}
L[3] > L[2], {0, 4, 2, 0, 0, 5}
L[6] > L[3], {0, 4, 5, 0, 0, 3}

Out[8]= {19, 16}
\end{mathematica}

It works even for some more complicated data:
\begin{mathematica}
max2[{7, 12, 14, 50, 15, 1, 20, 3, 40}, True]
.
L[2] > L[1], {0, 1, 0, 0, 0, 0, 0, 0, 0}
L[4] > L[3], {0, 1, 0, 3, 0, 0, 0, 0, 0}
L[5] > L[6], {0, 1, 0, 3, 6, 0, 0, 0, 0}
L[7] > L[8], {0, 1, 0, 3, 6, 0, 8, 0, 0}
L[4] > L[2], {0, 3, 0, 2, 6, 0, 8, 0, 0}
L[7] > L[5], {0, 3, 0, 2, 8, 0, 5, 0, 0}
L[4] > L[7], {0, 3, 0, 7, 8, 0, 2, 0, 0}
L[4] > L[9], {0, 3, 0, 9, 8, 0, 2, 0, 7}

Out[8]= {50, 40}
\end{mathematica}
%====================================================================


\end{document}