László Babai's Summer 2017 Math REU page
Apprentice program: Linear Algebra and Combinatorics
(June 19 - July 21, weeks 1 - 5)
What is NEW?
Press your browser's
"REFRESH" button to get the current
version of this page.
Material covered during last class, Friday, July 21
- Proof of Singular Value Decomposition
- Low-rank approximation theorem proved
(cool applied math!)
- AI: machine learning, recommender systems, etc.
- Finite Markov Chains. Evolution, stationary distribution.
Perron-Frobenius Theorem: nonnegative matrix has nonnegative
eigenvector. (Stated, not proved.) Corollary: Every finite
MC has a stationary distribution.
- Convergence rate of naive random walk on regular graph
estimated via eigenvalue gap (stated, proved).
- Hoffmann-Singleton Theorem: If $k$-regular graph of girth
$\ge 5$ has $n=k^2+1$ vertices then $k\in\{1,2,3,7,57\}$
(cool math!)
- 11:30 pizza, discussion about the road to grad school.
Panelists: your TAs Dylan Quintana, Karen Butt, Peter Xu,
Ben Lowe.
As of 7-14, classes moved to Ryerson 251!
Attention! Read instructor's
comments next to the link to the Tue, June 27 class notes.
"Chromatic polynomial" problem due Monday, July 3.
Text
Online text by instructor:
Discover Linear Algebra
Note: our point of view will be quite different from that taken
in Math 19620 -- Linear Algebra. Nevertheless, I recommend the
text used in that course, by Otto Bretscher, as a helpful supplement.
For graph theory, consult the
“Graph Theory” notes
by Angela Wu
Course information
Instructor: László Babai
Office: Ry 164
Email: laci@cs.uwaukeegan.edu
(Oops! wrong town - to be eligible, you must guess the right one.
Oh, you are just a poor little bot? I am sooo sorry.)
Schedule: Every day 9:30 - 12:00, Ry-251 [was Eck-133 until 7-13]
Peter
May's REU 2017 website has all the schedules for the REU
TAs:
Dylan Quintana dlastname at XX
Yulun Wang
firstname at XX
Karen Butt
firstnamelastname at XX
Peter Xu
firstnamex at XX
(XX means uwaukeegan.edu --- fix the town)
Ben Lowe
lastnameb24 at geemail (fix spelling of mail service)
Amanda Burcroff
lastname at umich.eedduu (fix spelling)
TAs' office hours: 4-5pm in Ry-162 ("Theory lounge")
each day of lectures, starting Tue June 20. The dates are:
Tue June 20 (Yulun), Thu June 22 (Dylan), Fri June 23 (Yulun),
Wed June 28 (Peter), Thu June 29 (Karen), Fri June 30 (Yulun),
Wed July 5 (Karen), Fri July 7 (Yulun), Mon July 10 (Peter),
Wed July 12 (Dylan), Fri July 14 (Dylan), Mon July 17 (Yulun),
Wed July 19 (Karen)
Schedule of problem sessions (during scheduled class time):
Wed June 21 (Dylan, Peter), Mon June 26 (Peter, Yulun),
Tue June 27 (Peter, Dylan), Fri June 30 (Dylan, Karen),
Thu July 6 (Karen, Yulun), Tue July 11 (Yulun, Peter),
Thu July 13 (Yulun, Dylan), Tue July 18 (Dylan, Amanda),
Thu July 20 (Amanda, Peter)
Links
Feel free to contact the instructor regarding the problems
assigned. If you like solving simple but challenging problems,
check out the instructor's REU problem sets for earlier years,
including
Additional links:
Homework policy
Homework is required for the Apprentice program!
Most linear algebra problems assigned will be from the
instructor's "Discover Linear Algebra" text and will be
identified like "DLA 8.3.6" for problem 8.3.6 from the text.
Three types of homework will be assigned.
- 'DO' exercises help you understand the basic concepts. As
their name suggests, you are expected to solve them, typically
by the next day, but DO NOT HAND THEM IN; rather, be
prepared to discuss your solution in class.
- 'HW' problems are to be handed in, typeset in Latex,
at the beginning of the next class unless another deadlines
has been announced. Most problems have brief, elegant solutions.
Clarity and elegance matter. The instructor will attempt to
give you feedback, but overly complicated, lengthy solutions
will be ignored for lack of grader capacity.
- Self-grading experiment. Once the solution to a HW problem
has been discussed in class, please submit a sheet at the beginning of
the next class, stating your rating of your solution on the following
scale.
- correct, simple -- is it essentially the same or is it
significantly different from the solution stated in class?
- correct but could be simplified (please briefly elaborate)
- minor error, easy to fix (please briefly elaborate)
- major error (please briefly elaborate)
- solution incomplete -- please briefly specify what was done right
and what was missing or in error
- cannot decide (please explain briefly)
- Challenge problems (CH) may or may not have a deadline,
but they expire once discussed in class. Unlike the HW problems,
they carry no point value, but they will earn you the attention of
the instructor (in addition to earning you the satisfaction at having
solved them). This may come in handy, e.g., if you need a letter of
reference in the future.
- Policy on collaboration. Collaboration on DO exercises
is encouraged. For HW problems, collaboration is neither encouraged
nor prohibited; please name your collaborators on your solution.
- Policy on web sources.
You are welcome to study web resources to augment your knowledge
of the subject. However, use of the web with the specific aim to
solve problems is discouraged and self-defeating. On today's
internet you can find virtually everything. We learn by
creative problem solving, and you will deprive yourself
of this experience if you keep looking up solutions on the web.
In any case, if you do hand in a solution inspired by something
you found on the web, please name the source. Describe the solution
in your own words, do not copy from the web.
Back to top