\documentstyle [12pt]{article}
\setlength{\oddsidemargin}{-.4cm}
\setlength{\topmargin}{-2cm}
\setlength{\headheight}{0cm}
\setlength{\textheight}{24.5cm}
\setlength{\textwidth}{17.3cm}
\setlength{\topskip}{0cm}
\setlength{\parindent}{0cm}
\setlength{\parskip}{.10in}
%
\pagestyle{plain}
\begin{document}
\vspace*{-.5cm}

\begin{minipage}[b]{19mm}
\setlength{\unitlength}{.4mm}
\begin{picture}(45,30)(-22.5,-15)
\thicklines
%
\put(0,0){\circle{15}}
%
\thinlines
\put( 7.5,  0){\oval(30,30)[t]}
\put( 7.5,-15){\line(1,0){15}}
\put( 7.5,-15){\line(0,1){15}}
\put(22.5,-15){\line(0,1){15}}
%
\put( -7.5, 0){\oval(30,30)[b]}
\put( -7.5,15){\line(-1,0){15}}
\put( -7.5,15){\line(0,-1){15}}
\put(-22.5,15){\line(0,-1){15}}
%
\end{picture}
\end{minipage}
\begin{minipage}[b]{6cm}
\footnotesize \sf
Computer Science and Engineering
\\
Ferguson Hall -- 0115
\\
472-2402
\end{minipage}
\hfill
\begin{minipage}[b]{8cm}
\begin{flushright}
\LARGE \bf
Course Specification\vspace*{3mm}
\end{flushright}
\end {minipage}
\vspace{.2cm}
{\bf \hrule}
\vspace{.5cm}

%------------------------------------------------------------------------
% NOTES TO USERS: 
%
% 1. Underlined text in this form is notes to you; please delete them.
%
% 2. DO NOT UNDERLINE your replacement text.
%
% 3. Try to observe the prescribed page-break, if at all possible.
%
%------------------------------------------------------------------------

{\Large \bf \begin{center} CSCE-310\\
Algorithms \\
\end{center} }

\paragraph{Catalogue Description:}~ \newline
310. Algorithms (3 cr) Prereq: CSCE 156 and 235.
Algorithmic approaches including greedy method, divide-and-conquer,
dynamic programming, and randomization.  A variety of common algorithms
for searching and sorting, indexing, hashing, heaps, problems on
graphs.  Introduction to NP Completeness and decidability.
Consideration of complexity and correctness.

\paragraph{Textbook(s) and/or Other Required Materials:}~ \newline
Cormen, Leiserson, and Rivest, {\em Introduction to Algorithms}, supplemented
as necessary with handouts

\paragraph{Prerequisites by Topic:} 
\begin{itemize}
\item {\bf Mastery} of data structures and operations for lists,
stacks, queues, trees, graphs.  Abstract data types. 
Discrete mathematics topics
including induction and recursion, set theory, elementary combinatorics,
elementary graph theory.
\item {\bf Familiarity} with recursive algorithms and recurrence relations.
\item {\bf Exposure} to complexity analysis.
\end{itemize}

\paragraph{Course Objectives:} 
\begin{itemize}
\item {\bf Mastery} of algorithmic approaches including greedy method
and divide-and-conquer.
A variety of common algorithms for searching and sorting,
hashing, heaps, DFS and BFS on trees and graphs.

\item {\bf Familiarity} with theoretic and
empirical complexity analysis. Problems on graphs.  
Algorithm correctness. (Place indices here?)

\item {\bf Exposure} to dynamic programming, randomization (in algorithms and
data structures), NP Completeness, decidability.

\end{itemize}

\vfill
{\small ~ \hfill  \today}
\newpage
\paragraph{Topics Covered:}~ \newline
It is expected that specific algorithms, problem solving techniques,
and complexity analysis will be taught as text book topics and strongly
reinforced with substantial theoretical and programming assignments, including
theoretical and empirical analyses
of complexity.  ``Mastery'' implies ability to apply the knowledge
gained in innovative and novel ways.  This requires skill through practice.

{\large\bf I tried to exemplify certain methods by focusing on graph problems,
e.g.\ MST, to reinforce graph theory from 235. 
Some such applications might have to be pruned.}

{\large\bf This enumeration does not necessarily imply a particular sequence!!!}

\begin{enumerate}
\item Algorithm analysis and asymptotic notation, revisiting Selection Sort and
Bubble Sort from CSCE 156 as examples. 
\item Solving recurrences, esp.~Master Method.
\item Divide-and-conquer algorithms: 
  merge sort, quick sort, closest pair of points, binary searching of a sorted
list (already in 156??). 
\item Heaps and heapsort.
\item $\Omega(n \log n)$ lower bound for sorting, radix sort
\item Randomization: randomized quicksort, expected performance of quicksort,
skip lists.
\item Hashing and hash tables.
\item Search trees: eg.~binary search trees, and a little on
  Red-Black trees and/or B-trees, and a little on indices. 
\item Greedy algorithms: Greedy choice and optimal substructure properties,
e.g.\ fractional knapsack, Huffman codes, MST (this last one is a good one
since it brings in some graph theory) 
\item Introduction to dynamic programming: optimal substructure property,
shortest paths problems, 0-1 knapsack problem
\item Graph traversal algorithms: DFS, BFS, applications to topological sort
and strongly connected components.
\item Introduction to NP-completeness and decidability. 
\end{enumerate}

% \begin{enumerate}
% \item Algorithm analysis and asymptotic notation. [1 week]
% \item Design patterns: containers, iterators, visitors, adapters, and
%    singletons. [2/3 week]
% \item Hashing, hash tables, and scatter tables. [2/3 week]
% \item Search trees: eg.~AVL search trees, M-Way Search trees,
%   Red-Black trees, B-trees and indices. [1 week]
% \item Heaps: binary heaps, leftist heaps, binomial queues, heapsort.
%   [2/3 week]
% %\item Dynamic storage allocation: singly- and doubly-linked free storage.
% \item Brute-force and greedy algorithms: eg. 0/1 knapsack problem,
%   topological sorting, bipartite cover, single-source shortest paths,
%   minimum cost spanning trees. [1 week]
% \item Backtracking algorithms: eg. 0/1 knapsack problem, max clique,
%   traveling salesman. [2/3 week]
% \item Divide-and-conquer algorithms: eg.~Strassen's matrix multiply,
%   merge sort, quick sort, closest pair of points. [2 weeks]
% \item Dynamic programming: eg. 0/1 knapsack problem, image compression,
%   matrix multiplication chains, all pairs shortest paths. [2 weeks]
% \item Randomized algorithms: eg. random number generators, Monte Carlo
%   techniques, simulated annealing. [1 week]
% \item Other Sorting algorithms: eg. shellsort, radix sort, external
%   sorting. [1 2/3 week]
% \item Other algorithms: eg. geometric, error detection/correction,
%   converting recursion to iteration,  parallel sort/merge, Branch and bound
%   algorithms: 0/1 knapsack problem, max clique, traveling salesman.
%   [2 weeks]
% \item NP-Completeness introduction. [1/3 week]
% \end{enumerate}

%\paragraph{Relationship of Course to Program Objectives:}~ 


%\paragraph{Contribution of Course to Meeting the Professional Component:}~ 


\paragraph{Class/Laboratory Schedule:}~ \newline
Lecture: 45 hours

\paragraph{Prepared by:}~ \newline
Charles Riedesel, Senior Lecturer.

\end{document}


