$\newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator*{\minimize}{minimize} \DeclareMathOperator*{\maximize}{maximize} \DeclareMathOperator{\subjectto}{subject to} \newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\MIN}[2]{\begin{array}{ll} \minimize_{#1} & {#2} \end{array}} \newcommand{\MINone}[3]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\MINthree}[5]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \\ & {#4} \\ & {#5} \end{array}} \newcommand{\MAX}[2]{\begin{array}{ll} \maximize_{#1} & {#2} \end{array}} \newcommand{\MAXone}[3]{\begin{array}{ll} \maximize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}} \newcommand{\vlambda}{\vecalt{\lambda}}$

CS 31400 Syllabus

Course information

Fall 2016
MWF 9:30am-10:20am
HAAS G66
http://www.cs.purdue.edu/homes/dgleich/cs314-2016

Instructor

David F. Gleich
Lawson 1207
dgleich@purdue.edu
http://www.cs.purdue.edu/homes/dgleich

Office hours

3:30-4:30pm on Thursday in my office

Teaching Assistant

Vishwanath Singh
singh350@purdue.edu

Office hours

Wednesday 10:30-11:30 HAAS G050
Thursday 5-6pm HAAS G050

Description

Numerical methods is a class that will introduce you to one of the ways that computers were first used: to solve problems and equations arising from mathematics and physics. It will also feature modern topics such as web-ranking algorithms and how they are all tied together via a set of numerical computing primitives.

Prerequisites

See the course catalog.

Goals and objectives

This course is an introduction to numerical methods, which is a rich and deep field. This course only scratches the surface to show how to use these methods to solve problems, and peeks at the details of more advanced methods.

When we reach the end of the class, you, the student, will:

• Understand numerical computing languages like Julia
• Understand the floating point number representation on computers
• Understand how to take a verbal description and construct a mathematical model that the computer can solve
• Understand why numerical accuracy, stability, and round-off errors are important
• Understand many of the fundamentals of numerical computing: Monte Carlo algorithms, Matrix methods, Interpolation, Integration, Numerical differentiation, ODEs and PDEs, and basic optimization.

Requirements

The formal requirements and percentage of the total course grade are:

• Pop quizzes + Participation -- 5%
• Homeworks -- 30%
• Midterms -- 40% (20% each) - Drop 1
• Quizzes -- 20% (5% each) - Drop 1

Within the first week We will decide on the remaining 5% of the course grade by picking between the following

• Choice 1 - Final on Dec 2 Attend topics: 8% (up to 3% extra credit)

• Choice 2 - Final regularly scheduled
Participation: goes to 10%

We are using Choice 1 based on the class poll.

Homeworks

Homeworks will be due on Friday's. There are 6 homeworks in total. See below for the policy on late assignments.

Midterms

There will be three midterms, one at the end of each unit that covers the material of that unit.

Quizzes

There will be 5 20-30 minute in class quizzes throughout the semester. These will cover material from the past two weeks and should serve as prep-work for the midterm.

Participation

Throughout class, I will regularly use "pop" quizzes that are not graded. However, they do count towards your participation grade. You should expect one in each lecture. Students can miss up to 4 quizzes with no penalty. Make sure you contact the instructor (David) if you anticipate missing more than 4 quizzes due to any circumstances. Note that this is an all-or-nothing grade.

References

The required text book is:

Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms Anne Greenbaum and Timothy P. Chartier 2012, Princeton Press, ISBN:9780691151229 Amazon link

Policies

Conduct and Courtesy

Students are expected to maintain a professional and respectful classroom environment. In particular, this includes:

• silencing personal electronics
• arriving on time and remaining throughout the class
• do not insult or deride others for any reason (even in jest)
• be on time for class
• please leave class promptly and wait to ask me questions in the hall, unless they pertain to material on the blackboard.

You may use any non-disruptive personal electronics during class. One exception is during in-class quizzes, midterms, and pop-quizzes, for which personal electronics are prohibited.

Annoucements

There will be announcements relevant to the course made through the ITaP course email list. This will send an email message to your purdue email address and you are expected to check this account for information related to the class. We will verify that everyone in the class is receiving these messages early on.

Correspondence

The best way to correspond in this class is to post a note on Piazza.

Please feel free to email me with any questions, but please prefix all email titles with the string CS-31400: to aid in filtering email. Also, consider using Piazza instead.

I will make every effort to respond promptly, however, replies could be delayed due to circumstances outside of my control. In particular, do not rely on a response between the hours of 8pm and 8am.

Please do not attempt to call, google chat, skype, facebook, or tweet with me without prior arrangement.

Assignment clarity

I expect all assignments to be legible and well-written in English; mathematical derivations alone are insufficient and you must explain your reasoning in sentences.

For this purpose, I will suggest using a computer with LaTeX to prepare all submitted materials.

For handwritten assignment solutions, the TA has broad discretion to give a zero to any answer that is not legible or if the TA cannot understand what you have done,

For computer-prepared assignments, the TA is encouraged to spend more time trying to understand a solution.

Also, using LaTeX can increase the temptation to share answers. All LaTeX must be written individually.

Missing or late work

Except as discussed below, and or by prior arrangement, missing or late work will be counted as a zero.

I am considering a refinement of this policy

Collaboration

Collaboration on homework is allowed. However, sudents must prepare solutions individually.As an example of the ideal scenario, the following situation is permissible:

A group of students meets to develop the solution to a problem on a white board. Each student records individual notes from this problem solving meeting. All students then prepare solutions individually and without further collaboration. These solutions list the names of all members in the initial group.

The final assignments must contain a list of all collaborators, regardless of if they are in the class or not. Failure to list collaborators will result in a zero on any homework, you must write I did not collaborate with anyone on this homework'' if you worked on the homework entirely alone.

Examples of collaborations that are not allowed include, but are not limited to:

• Sharing pieces of any written solution
• Sharing source code or any other computer programs
• Reviewing final written solutions

Computer codes

The assignments will involve producing computer codes. These need to be documented and written in accordance with best software engineering practices. Failure to follow this advice may result in solutions receiving zero points. Moreover, these should be prepared individually. Groups may discuss implementation strategies, algorithms, and approaches; but codes, like written homework solutions, must be prepared separately.

Debugging

What to do about debugging? That's right, you've gotten the ideas down. You think you have the algorithm right, you coded it. And yet, it still doesn't work. But you can't ask a friend because you can't share code, right? Here is what you should do. Spend 30 minutes working with that code to try and make it work. Write down what you did. If, after that, it still doesn't work. Then spend 15 minutes explaining what your problem is to a friend without looking at the code. If that still didn't help, you may show your code to your friend, provided that you send the TA + Prof an email with your names, and with the code before debugging and the code after debugging.

• A -- 87-100%
• B -- 70-86%
• C -- 55-69%
• D -- 40-55%
• F -- 0-40%

These may be adjusted downward by up to 10% to achieve a reasonable grade distribution. They also may be minor upward adjustments.

Behavior consistent with cheating, copying, and academic dishonesty is not tolerated. Depending on the severity, this may result in a zero score on the assignment or exam, and could result in a failing grade for the class.

Purdue prohibits "dishonesty in connection with any University activity. Cheating, plagiarism, or knowingly furnishing false information to the University are examples of dishonesty." (Part 5, Section III-B-2-a, University Regulations) Furthermore, the University Senate has stipulated that "the commitment of acts of cheating, lying, and deceit in any of their diverse forms (such as the use of substitutes for taking examinations, the use of illegal cribs, plagiarism, and copying during examinations) is dishonest and must not be tolerated. Moreover, knowingly to aid and abet, directly or indirectly, other parties in committing dishonest acts is in itself dishonest." (University Senate Document 72-18, December 15, 1972)

You are expected to read both Purdue's guide to academic integrety and Prof. Gene's Spafford's guide as well. You are responsible for understanding their contents and how it applies to this class.

Attendance

Students are expected to be present for every meeting of the classes in which they are enrolled. Only the instructor can excuse a student from a course requirement or responsibility. When conflicts or absences can be anticipated, such as for many University sponsored activities and religious observations, the student should inform the instructor of the situation as far in advance as possible. For unanticipated or emergency absences when advance notification to an instructor is not possible, the student should contact the instructor as soon as possible by email, or by contacting the main office that offers the course. When the student is unable to make direct contact with the instructor and is unable to leave word with the instructor's department because of circumstances beyond the student's control, and in cases of bereavement, the student or the student's representative should contact the Office of the Dean of Students.

Grief Absence Policy

Purdue University recognizes that a time of bereavement is very difficult for a student. The University therefore provides the following rights to students facing the loss of a family member through the Grief Absence Policy for Students (GAPS). GAPS Policy: Students will be excused for funeral leave and given the opportunity to earn equivalent credit and to demonstrate evidence of meeting the learning outcomes for misses assignments or assessments in the event of the death of a member of the student's family.

Violent Behavior Policy

Purdue University is committed to providing a safe and secure campus environment for members of the university community. Purdue strives to create an educational environment for students and a work environment for employees that promote educational and career goals. Violent Behavior impedes such goals. Therefore, Violent Behavior is prohibited in or on any University Facility or while participating in any university activity.

Students with Disabilities

Purdue University is required to respond to the needs of the students with disabilities as outlined in both the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1990 through the provision of auxiliary aids and services that allow a student with a disability to fully access and participate in the programs, services, and activities at Purdue University. If you have a disability that requires special academic accommodation, please make an appointment to speak with me within the first three (3) weeks of the semester in order to discuss any adjustments. It is important that we talk about this at the beginning of the semester. It is the student's responsibility to notify the Disability Resource Center (http://www.purdue.edu/drc) of an impairment/condition that may require accommodations and/or classroom modifications.

Emergencies

In the event of a major campus emergency, course requirements, deadlines and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances beyond the instructorâ€™s control. Relevant changes to this course will be posted onto the course website or can be obtained by contacting the instructors or TAs via email. You are expected to read your @purdue.edu email on a frequent basis.

Emergency Preparedness

Emergency notification procedures are based on a simple concept:

if you hear a alarm inside, proceed outside.
if you hear a siren outside, proceed inside.

Indoor Fire Alarms are mean to stop class or research and immediately evacuate the building. Proceed to your Emergency Assembly Area away from building doors. Remain outside until police, fire, or other emergency response personnel provide additional guidance or tell you it is safe to leave.

All Hazards Outdoor Emergency Warning sirens mean to immediately seek shelter (Shelter in Place) in a safe location within the closest building. "Shelter in place" means seeking immediate shelter inside a building or University residence. This course of action may need to be taken during a tornado, a civil disturbance including a shooting or release of hazardous materials in the outside air. Once safely inside, find out more details about the emergency. Remain in place until police, fire, or other emergency response personnel provide additional guidance or tell you it is safe to leave.

Nondiscrimination

Purdue University is committed to maintaining a community which recognizes and values the inherent worth and dignity of every person; fosters tolerance, sensitivity, understanding, and mutual respect among its members; and encourages each individual to strive to reach his or her own potential. In pursuit of its goal of academic excellence, the University seeks to develop and nurture diversity. The University believes that diversity among its many members strengthens the institution, stimulates creativity, promotes the exchange of ideas, and enriches campus life.

Purdue University prohibits discrimination against any member of the University community on the basis of race, religion, color, sex, age, national origin or ancestry, marital status, parental status, sexual orientation, disability, or status as a veteran. The University will conduct its programs, services and activities consistent with applicable federal, state and local laws, regulations and orders and in conformance with the procedures and limitations as set forth in Executive Memorandum No. D-1, which provides specific contractual rights and remedies.

Schedule

A tentative list of lectures follows. See the web-page for an up-to-date list of lectures, under the "readings" section.

Unit 1

• Reading: Chapter 1, 2, 3, 5

• Aug 22 - Review Syllabus, Course Intro, Math Modeling (1) (Chapter 1)

• Aug 24 - Math Modeling (2) (Chapter 1)
• Aug 26 Quiz 1 on Math Modeling - then Julia (Chapter 2)
• Aug 29 - More Julia (Chapter 2)
• Aug 31 - More Julia (Chapter 2)
• Sep 2 HW due on Julia - Floating point (Chapter 5) Sep 5 - no class
• Sep 7 - Floating point (Chapter 5)
• Sep 9 Quiz 2 More floating point (Chapter 5)
• Sep 12 - Monte Carlo methods (review of probability, 3.2)
• Sep 14 - Monte Carlo methods (games + integrals, 3.1, 3.3)
• Sep 16 HW due - Monte Carlo (ranking, 3.4))
• Sep 19 - Catchup and Review
• Sep 21 Midterm 1

Unit 2

• Reading: Chapter 6, 7, 12

• Sep 23 - Fun with Matrix Multiply

• Sep 26 - Implementations of MatMul (7.1)
• Sep 28 - Solving linear systems - Gaussian Elimination (7.2)
• Sep 30 HW due - Solving linear systems (7.2)
• Oct 3 - Solving linear systems (7.2) and (7.3)
• Oct 5 - The QR factorization and least squares.
• Oct 7 Quiz - Iterative methods for linear systems (12.2)
Oct 10 - no class (Fall Break)
• Oct 12 Conditioning (Chapter 6)
• Oct 14 HW due Conditioning (Chapter 6)
• Oct 17 Eigenvalue problems (12.1.1, 12.1.5)
• Oct 19 Catchup and Review
• Oct 21 Midterm

Unit 3

• Reading Chapter 4, 8, 9, 10, 11, and a little bit of 13, 14

• These dates may be shifted slightly to extend Unit 2 by one class in which case the midterm would be on Oct.

• Oct 24 - Applied Math Intro, Polynomial fitting (8.1), Chebfun (8.5)

• Oct 26 - Lagrange polynomials, Barycentric, Newton (8.2)
• Oct 28 - Quiz Piecewise polynomials (8.6.2)
• Oct 31 - Truncation error or discretization error (9.1) Chapter 9
• Nov 2 - Richardson extrapolation (9.2)
• Nov 4 - HW due Numerical integration intro
• Nov 7 - Chapter 10, piecewise integration, gaussian quadrature, high-dimensions
• Nov 9 - Pending
• Nov 11 - Quiz
• Nov 14 - Chapter 11, 13, 14: Forward euler, Backwards Euler, consistency,
• Nov 16 - Truncation error / accuracy, convergence, stability
• Nov 18 - HW due Hyperbolic equations, elliptic equations
• Nov 21 - Chapter 4: Newton's method for rootfinding, optimization, bisection search
Nov 23 - no class
Nov 25 - no class
• Nov 28 - Review and catchup
• Nov 30 - Review and catchup
• Dec 2 Midterm
• Dec 5 - Required Topic 1
• Dec 7 - Required Topic 2
• Dec 9 Required Topic 3

Makeup classes

If we need to reschedule additional classes, we will do so on an as-needed basis. Our plan is to use video lectures to supplement for any missing class periods.

Changes

This syllabus is subject to change. Updates will be posted on the course website. Changes will be noted in this section

• Initial version: 2016-08-21
• Correction: 2016-08-22 - Fixed date of final in Choice 1 for the exam
• Updated with office hours: 2016-08-30
• Updated with choice of final example (Choice 1, final early): 2016-08-30