\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}
\syllabus{: Topics in Discrete Mathematics}{Weeks 1-10}

\section*{Basic Course Information}

\begin{itemize}
\item Professor: Padraic Bartlett.
\item Email: \href{mailto:padraic@math.ucsb.edu}{padraic@math.ucsb.edu}.
\item Class time/location: MWF 11:30-12:50, CCS Building 494, Room 164B.
\item Office hours/location: 12-1pm Tuesday, SH 6516 / 5-6:30pm  Thursday, SH 6516 / 10:30-12pm Saturday, CCS Building 494, Room 164B. These office hours will be shared with other classes.  Also, the Saturday hours might not run every weekend, due to travel commitments; I'll email changes when relevant.  Also-also, the Saturday hours will have pancakes!  Yay, pancakes.
\item Course webpage:  \href{http://math.ucsb.edu/~padraic/}{http://math.ucsb.edu/{\raise.17ex\hbox{$\scriptstyle\sim$}}padraic/}.
\item Homework due date: Fridays, at the start of class.  
\end{itemize}

\section*{Course Description}

Think about most of the math classes you've taken before.  You go to lecture, copy down notes, solve stacks of integrals and box your answers, and go onto the next topic.  Repeat for the entirety of high school and Calc 1-3.

By contrast, compare this with mathematics outside of high school.  In industry, for example, no-one will ask you to calculate a stack of derivatives or solve some pile of equations (that's what Mathematica is for!)  Instead, you're going to see open-ended problems.  You'll be advising supply firms on how much product to buy; you're going to figure out how much weight a bridge can support without failing; you'll be determining how many flights your company needs to schedule between LAX and PEK next year.  

Furthermore, when you get your answers, you won't be able to just say to your project team ``Oh, 38 tons'' and walk away; you're going to have to explain to them \textbf{how} you derived your answer, so they can understand it and double-check it.  Furthermore, if you get something wrong, it's not like your bridge gets ``$83\%$, B-'' stamped on the side: you have to go back and \textbf{fix your answers} until they are \textbf{right}.

If you go into academia, this all counts double.  When you're doing research in mathematics, you're often not just discovering the answers but also the questions; more of your time is spent on studying definitions and concepts than actually calculating anything.  To illustrate this point, here is a page from Robertson et. al.'s paper that proves the four-color theorem\footnote{The four-color theorem is a famous result in graph theory about the following problem: take any map, and suppose you want to give each country on this map its own color so that no two countries that touch have the same color.  How many colors do you need?  Perhaps surprisingly, if you assume that every country is \textbf{contiguous} (i.e. connected, so we don't allow things like Alaska and the US, or Kaliningrad and Russia), it turns out you only need four colors!  This problem was first posed in 1852, and was only solved in 1976; its proof is notorious because a large chunk of it relies heavily on computer-aided search.  No completely human-written proof is known.}.  Notice how this is almost entirely words and pictures!
\begin{center}
\includegraphics[width=2.5in]{4ctproofpage.pdf}
\end{center}


If you're in this classroom, there's a pretty good chance you're interested in being a mathematician.  That page above is what math in the real world looks like.  Therefore, this is what math is going to look like in our classroom!  This means we're going to do a number of things in this classroom that you may not have done before in a math class:\\
\begin{enumerate}
\item Lectures will be very interactive; I will ask questions constantly in class, and expect you to contribute examples, ask questions, and think on the spot.
\item Homework sets will be handed out daily.  Homework problems will often be open-ended, involve multiple stages, and involve more thought than ``just apply theorem x.''  Sets will be collected on Fridays of each week.
\item Homework problems will be graded with respect to two criteria:
\begin{enumerate}
\item Did you arrive at the correct answer, using a sound chain of logical statements?
\item Does your work cleanly and carefully lay out a full and complete solution to the problem at hand?  I.e.\ could your solution be used as an example in a textbook?
\end{enumerate}
Each homework problem will receive either a point (if the work satisfies both of the above criteria,) half a point (if it makes substantial progress towards these criteria, but is flawed) or no credit (if it is fundamentally flawed on at least one of the two criteria above.)  The TA and I will be pretty strict when grading these problems.  In particular, one common misstep students make is not knowing how much to write down in their proofs.  While there is no hard and fast rule, a heuristic I tend to use is the following: would it take an average student in this course more than twenty seconds to figure out how one line of my proof follows from the previous line?  Alternately: am I using any nontrivial results from this class or other fields to go from one line of my proof to the next?  If so: explain in words how we moved from one line to the next!
\end{enumerate}

\section*{Course Evaluation}

There are three components of your grade in this course:
\begin{enumerate}
\item \textbf{Homework} (75\%.)  There will be problem sets handed out daily, collected and turned in \textbf{at the start of class on Friday} each week.  Problem sets need to be written in LaTeX to be graded.  


These will be tricky homework sets, and will often contain problems that are hard/graduate-level/maybe even open/etc.  Consequently, I'm not expecting anyone to solve every problem throughout the course!  In fact, this is built into the structure of the assignments themselves; each problem set will consist of $n$ problems, from which you will have to choose $k$ to solve (for values of $n$ and $k$ defined on the homework set.)  This allows you to pick out the problems that are interesting/challenging to you, and lets me assign a greater breadth of homework than a normal class.

Over the course, your lowest three daily HW scores will be dropped!  Correspondingly, to make life easier for the grader and myself, \textbf{late homework will not be accepted.}  Exceptions to this policy can be made with at least 24 hours notice for students with legitimate reasons (sickness, travel, other reasonable difficulties.)  If it is within 24 hours of the deadline, then exceptions will only be granted with a corresponding doctor's/counselor's note.  Talk to me if you are confused by this policy, or have questions.

\item \textbf{Quizzes} (25\%.)  There will be weekly brief quizzes on Fridays at the start of class.  Your lowest quiz score will be dropped; accordingly, quizzes cannot be made up (with a similar 24-hour-in-advance buffer required to seek any exceptions.)

\item \textbf{Extra Credit} (?\%)  Before any class starts, you may write on the board any of the problems that you had difficulty with.  If this problem is on a homework set that is still live, we'll talk for a bit about how to approach it; students who know how to solve it are invited to offer hints here!   If the problem is on a homework set that was handed in (either at the start of this class or a previous class,) any student who feels like they have a solution to any such problem is welcome to present their solution to the class.  This is done with the caveat that we may not always be able to get to all of the problems listed in any class, due to time constraints.  

If a student successfully presents a correct solution to a problem in this fashion in a class, they get a flat $+.5\%$ to their final grade!  In the event that there are multiple students with solutions to a problem, the student with the smallest number of presented problems will get priority.  Incorrect or flawed presentations may or may not receive partial credit, depending on the quality of the attempted solution.
\end{enumerate}

This course is pass-fail and for five units.  As defined by the CCS Mathematics department, your percentage score in this class is transformed into units via the following policy:
\begin{itemize}
\item Students receive the full five units for work at or above the A- level.
\item Students receive four units for work at or above the B level.
\item Students receive three units for work at or above the C level.
\item Students receive no units for work below the C- level.
\end{itemize}
The correspondence between percentage marks and letter grades depends heavily on class performance; there are years where a 75\% can correspond to an A, and others where it corresponds to a C, depending on the pace/difficulty of the course.  Throughout the course, I will report HW averages along with what letter grade those performances correspond to, so that you can keep track of your position throughout the class.  

However, if you want an absolute metric to keep in mind: a 90\% will always correspond to some flavor of A, an 80\% will always be at least a B, and so on/so forth.  It is likely that our grading scale will be much kinder than this.


\section*{Collaboration/resources policy}
Collaboration is allowed (and indeed encouraged) on the homework sets; mathematics at the research level is a collaborative activity, and there is no reason that it should not also be this way in a classroom.  Work with your classmates! 

Resources are a little trickier.  On one hand, you are now researchers; limiting your resources would seem to be contradictory to the spirit of emulating what research mathematics is like.  On the other hand, answers to almost everything in elementary mathematics can be found via Google and some patience; if you had unfettered access to every resources in existence, you would likely inadvertently rob yourself of some of the best problems in your education.  So we need to strike a balance.

For this class: Wikipedia is a legitimate resource, as are any physical books you get from the library or have yourself.  Mathematica/Wolfram Alpha/etc. are also valid tools, though you need to justify any calculations you perform using any computational systems.  Upper-classmen are also valid resources to talk to about problems, provided you follow the citation system described below; however, I would ask that you restrict them to hints instead of answers if they know the problem!  (This should rarely happen; these are not problems they would have seen in their own run of this class.)  Other resources are off-limits.  If this policy seems restrictive, talk to me; I am more than glad to make common-sense exceptions where appropriate.

The only things that we ask of you are the following:
\begin{enumerate}
\item Write up your work separately, and only write up solutions you understand fully.  
\item When writing up your own work, you can directly cite and use without proof anything proven in class or in the class notes posted online.  Anything else --- i.e. results from textbooks, Wikipedia, etc. --- you need to both (1) cite in your writeup, and (2) reprove the results you're using from those sources carefully in your own words.  Simply copying solutions over directly is plagiarism / cheating / otherwise poor academic form; it is passing of as your own work the ideas of others.  You are certainly welcome to read and learn what other people have attempted!  All I am asking you to do here is to (1) not pass it off as your own work, and (2) rephrase and present it in a new way so that it is clear that you have actually learned something.
\item As an important corollary to the above: if the TA or I find that you have copied sentences/work/etc. directly from outside sources,
\begin{enumerate}
\item On your first violation, the offending set's score will be set to -100\%.
\item If there is any second violation, we will get the university involved.  Consequences include failing the course and a likely dismissal from CCS.
\end{enumerate}
Please, please don't make me have to ever go through (b) above.
\item If you work with other students on a problem, it is considered good form to refer to them (i.e. "I worked with Andrew Wiles on this proof of Fermat's Last Theorem'') when writing up your solutions.  I mostly ask this because crediting collaborators is something you're going to do as mathematicians, and should get in the habit of.
\item Don't post questions to online messageboard-style services.    
\end{enumerate}

If you have any questions on the collaboration policy, please email me and I'll be glad to clarify matters.

\section*{Course Textbook}

There is no primary textbook for this course.  I will post notes on the course website.

\section*{Tentative Course Outline}

This depends heavily on what pace I can take this course at, and what your respective interests and desires are; it is likely that we will take at least a few detours from this path as the quarter progresses!  That said, here is a tentative list of subjects:\\
\begin{multicols}{2}
\begin{enumerate}
\item Basic counting techniques.
\item Advanced counting techniques; generating functions.
\item Special numbers: Stirling,\\ Catalan, Bernoulli, etc.
\item Groups: definitions, examples.
\item Groups and cryptography.
\item Finite fields: definitions, constructions.
\item Elliptic curves over finite fields.
\item Vector spaces, basis, and dimension.
\item Maps, matrices, and determinants.
\item Error-correcting codes.
\end{enumerate}
\end{multicols}

\end{document}