% marc thomas
%
% define the following macros:
%
\def\scriptA{{\cal A}} % \cal for math mode only and no
\def\boldN{{\bf N}}
\def\boldR{{\bf R}}
\def\boldRP{{\bf R}$^+$} % bold-face R plus
\def\boldC{{\bf C}}
%
% end of macros
%
% \magnification=\magstep1 % 1200 magnify output chosen number of steps
\magnification=\magstephalf % 1095
\nopagenumbers
\voffset -0.35 true in
\hsize = 6.8 true in % but keep same page size
\vsize = 9.75 true in
\baselineskip12pt
\parskip2pt
\noindent
% {\bf Course Description} \hfill\break
% {\bf CMPS 312}
\centerline{\bf CMPS 312 Algorithm Analysis and Design}
% \centerline{\bf Algorithm Analysis and Design}
\vskip5pt
\noindent
\underbar{\bf Catalog Description}
\item{} {\bf CMPS 312 Algorithm Analysis and Design (5)}
\item{} Algorithm analysis, asymptotic notation, hashing,
hash tables, scatter tables, and AVL and B-trees, brute-force
and greedy algorithms, divide-and-conquer algorithms, dynamic
programming, randomized algorithms, graphs and graph algorithms,
and distributed algorithms. Each week lecture meets for 200
minutes and lab meets for 150 minutes. Prerequisite: CMPS 295/300
and CMPS 223.
\noindent
\underbar{\bf Prerequisites by Topic}
\item{} Discrete Structures
\item{} Data Structures
\noindent
\underbar{\bf Units and Contact Time}
\item{} 5 quarter units. 4 units lecture (200 minutes), 1 unit
lab (150 minutes).
% \noindent
% {\bf Instructor:}
% \item{} Marc Thomas
\noindent
\underbar{\bf Type}
\item{} Required for Computer Science
\noindent
\underbar{\bf Required Textbook}
\item{} Introduction to the Design and Analysis of Algorithms,
3rd edition, Anany Levitin, Pearson, 2012, ISBN-10: 0-13-231681-1;
ISBN-13: 978-0-13-231681-1.
\noindent
\underbar{\bf Recommended Textbook and other Supplemental Materials}
\item{} None
\noindent
\underbar{\bf Coordinator(s)}
\item{} Marc Thomas, Donna Meyers
\noindent
\underbar{\bf Student Learning Outcomes} \hfill\break
This course covers the following ACM/IEEE Body of Knowledge student learning
outcomes:
\item{} (CC-AL1) Basic algorithmic analysis.
\item{} (CC-AL2) Algorithmic strategies.
\item{} (CC-AL3) Fundamental computing algorithms.
\item{} (CC-AL4) An introduction to distributed algorithms.
\item{} (CE-ALG5) Algorithmic complexity.
% \item{} (Laboratory) Become proficient in writing
% programs implementing algorithms, understanding memory usage,
% user and system time, and impact of caches and virtual memory
% on performance.
\noindent
\underbar{\bf ABET Outcome Coverage} \hfill\break
This course maps to the following performance indicators for Computer
Science (CAC/ABET):
\item{} (CAC PIa1):
{\it 3a. An ability to apply knowledge of computing and mathematics
appropriate to the discipline: PIa1. Apply and perform the correct
mathematical analysis.}
\itemitem{}
Laboratory/homework assignments and questions on the
midterms and final require direct applications of the
mathematical theory of algorithms pertinent to computer science.
\item{}(CAC PIb1):
{\it 3b. An ability to analyze a problem, and identify and define
the computing requirements and specifications appropriate to
its solution: PIb1. Identify key components and algorithms necessary
for a solution.}
\itemitem{}
Implementation on actual hardware and the ability to analyze
performance (e.g. the roles of caches, virtual memory, use of
multi-threaded code) will be required for successful completion
of laboratory/homework assignements and will be tested on
the exams.
\item{}(CAC PIj1):
{\it 3j. An ability to apply mathematical foundations, algorithmic
principles, and computer science theory in the modeling and
design of computer-based systems in a way that demonstrates
comprehension of the tradeoffs involved in design choices: PIj1.
Understand performance and cost as these relate to
software/firmware-based and hardware-based implementations.}
\itemitem{}
Implementation and performance analysis of different algorithms
(e.g. direct, recursive, etc.) which solve the same problem will
be required for successful completion of laboratory and homework
assignments and will be tested on the exams.
\noindent
\underbar{\bf Lecture Topics and Rough Schedule (Sections by Week)}
\itemitem{W1:} (1.1--1.4 and Appendix~A) introduction, basic
issues with examples, useful formulas, important problem
types, and review of data structures.
\itemitem{W2:} (2.1--2.3) input size, order of growth
and big-{\cal O}
notation, analysis and examples of non-recursive algorithms,
\itemitem{W3:} (2.4, Appendix~B, and 3.1--3.2) analysis and
examples of recursive algorithms,
searching, sorting, and string matching.
\itemitem{W4:} (3.3--3.4) closest-pair, convex hull problems,
and exhaustive search (traveling salesman, knapsack).
\itemitem{W5:} (4.1) insertion sort, (4.2) topological sorting,
and (4.3) combinatorial considerations.
\itemitem{W6:} (4.4) binary search, (4.5) Lomuto partitioning,
(5.1) mergesort, and (5.2) quicksort.
\itemitem{W7:} (5.3--5.4) binary tree traversals. (6.2) Gaussian
elimination.
\itemitem{W8:} (6.3) AVL and 2--3 search trees and (6.4) heapsort.
\itemitem{W9:} (6.5) Horner's rule, (7.3) hashing, and (7.4) B-trees.
\itemitem{W10:} Additional topics (e.g. P and NP, multi-threaded
code, and distributed algorithms).
\noindent
\underbar{\bf Laboratory Topics}
\item{} The laboratory session will parallel the
lecture, illustrating the principles and familiarizing the
student with actual coding and hardware performance. Coding
will be in {\bf both} the {\tt C} and {\tt C++} languages and
we will cover the use of timing
({\tt user}, {\tt system}) routines.
\noindent
\underbar{\bf Estimated ABET Category Content}
\item{} Math and Basic Sciences
\item{} Fundamental Computing
\item{} Advanced Computing
\noindent
\underbar{\bf Design Content Description}
\item{} Not applicable to this course.
\noindent
\underbar{\bf Prepared by}
\item{} Marc Thomas on October 21, 2013.
\noindent
\underbar{\bf Approval}
\item{} Approved by CEE/CS Department \ \ \
\leaders \hrule \hskip 2.0 in \hfill
\item{} Effective Fall 2013
%
% force page break
%
\vfill
\eject
\null
\centerline{\bf CMPS 312 Addendum to Syllabus}
\vskip5pt
\noindent
\underbar{\bf Grading:}
\item{} Two midterms will be given, each worth 25\%.
I do not give make-up midterms; for an excused absence I count the
other grades proportionately higher. One final exam, comprehensive
but emphasizing the later material, will be given. It is mandatory
and worth 25\%. Homework and lab work are together worth the
remaining 25\%.
\noindent
\underbar{\bf Final Exam:}
\item{} The final exam is mandatory and should be taken at
the scheduled time which is posted on the CSUB campus main web page.
Making travel arrangements on or before the date of the final
exam will {\bf not} be considered a valid excuse for being able
to take the final exam at a different time.
\noindent
\underbar{\bf Attendance Policy:}
\item{} Students are responsible for their own attendance.
Course materials and assignments will be posted on the course
website: \hfil\break
{\tt http://www.cs.csubak.edu/\~{}marc/code/cs312.html}
\noindent
\underbar{\bf Academic Integrity Policy:}
\item{} Homeworks and labs may be worked on and strategy
discussed in groups. However, unless otherwise stated, all
assignments are {\it individual} assignments in that each
student must turn in his/her own work; {\bf no} direct copying
is allowed. Refer to the Academic Integrity policy printed in
the campus catalog and class schedule.
\noindent
\underbar{\bf Tutoring Center:}
\item{} The Tutoring Center in Sci~III 324 is available for
use by students in this course outside of class time on a first
come, first serve basis. Priority in the lab is given to students
who are completing assignments for department courses. The hours
for the Tutoring Center are posted on the department website.
%
% \item{} Students in this course may ask the tutors for
% assistance on assignments. The tutors are not allowed to solve
% the assignment for you, but they can assist with problems like
% cryptic compiler errors.
%
\vfill
\eject
\end