% 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
