AM 106: Applied Algebra

Semester: Fall
|
Year offered: 2018

Lecturer: Salil Vadhan (gender pronouns: he, him, his)
Teaching Fellows: Wael Alghamdi and Jason Ma
Schedule, lecture notes & assignments: go to site
Canvas: https://canvas.harvard.edu/courses/42508 (for submitting assignments and accessing solutions and section notes)
Piazza: http://piazza.com/harvard/fall2018/am106 (for Q&A, announcements, and communication with course staff)
Time & Place: TuTh 9-10:15, Maxwell Dworkin G-125

Summary

Algebra is the study of operations (such as addition, multiplication, composition) on sets of objects (such as numbers, polynomials, matrices, permutations). In addition to studying specific operations on specific sets, we also abstract properties that such operations commonly satisfy and the implications of these properties, thereby unifying the study of a wide variety of mathematical objects. In addition to being a beautiful subfield of mathematics, algebra has numerous applications in science and engineering. It is extremely useful for studying symmetries of physical objects, and for encoding data and computations to provide properties such as error-correction and privacy.

In this course, we will cover:

  • The basics of abstract algebra (groups, rings, fields)
  • Algorithmic aspects of algebra: which algebraic problems have (efficient) algorithms, and which do not.
  • Applications of algebra to science and engineering
     

Topics

  1. Introduction (1 lecture)
  2. The Integers (2 lectures)
    • General Theory (Gallian Ch. 0): induction, gcds, prime factorization, modular arithmetic
    • Algorithmic Aspects: O notation, complexity of arithmetic, factorization, Euclidean algorithm
  3. Group Theory (10 lectures)
    • General Theory (Gallian Chs. 1-10): groups, subgroups, cyclic groups, permutation groups, isomorphisms, cosets, products, quotients, homomorphisms
    • Algorithmic Aspects: exponentiation vs. discrete logarithms, computational group theory
    • Applications: symmetry groups in crystallography, public-key cryptography
  4. Rings and Fields (10 lectures)
    • General Theory (Gallian Chs. 12-17, 19-22): rings, integral domains, ideals and quotients, ring homomorphisms, polynomial rings, vector spaces, extension fields, finite fields.
    • Algorithmic aspects: polynomial arithmetic, finite field arithmetic.
    • Applications: error-correcting codes

Prerequisites

The formal prerequisite for the course is (Applied) Math 21b or equivalent, but general "mathematical maturity" is more important than the specific material in this course.� At times, we will assume familiarity with basic linear algebra as covered in Math 21b, but students who have instead taken a prior proof-based course on a different topic (such as CS 20, AM 107, or Math 101) should be adequately prepared.

 

This course is more abstract and proof-based than most Applied Math classes. If you are doing proofs for the first time, it is particularly important that you invest sufficient effort at the start of the course to gain comfort, for example by attending the section on doing proofs, coming to office hours, and completing and turning in ps0.

 

Although we will be adding some computer exercises to the problem sets, they will not require substantial programming and we will not assume prior programming experience.
 

Grading

AM 106 students:

  • Weekly problem sets: 50%� (lowest score dropped)
  • Two in-class quizzes: 10% each
  • Final exam: 25%
  • Class participation: 5%

Your class participation grade is based on participation in lecture, but can also be boosted by participation in section, Piazza, and office hours, especially with questions or comments aimed at learning (not just at solving the homework problems). There are no "stupid" questions!

Problem Sets

The course will have weekly problem sets, due Fridays at 5pm sharp electronically via Canvas. You have 6 late days for the semester, of which at most 3 can be used on any problem set. The late days are meant to accommodate minor illnesses, interviews, athletic or extra-curricular events, etc. Exceptions will be granted only under extenuating circumstances and require a note from your resident dean (or academic advisor, in the case of graduate students). You are strongly encouraged to start problem sets early, as mathematical problem-solving often requires allowing time for ideas to "simmer".

Collaboration Policy

Students are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people).   Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem.  In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around. While working on your problem sets, you should not refer to existing solutions, whether from other students, past offerings of this course, materials available on the internet, or elsewhere.  All sources of ideas, including the names of any collaborators, must be listed on your submitted homework.

In general, I expect all students to abide by the Harvard College Honor Code. I view us all (teaching staff and students) as engaged in a shared mission of learning and discovery, not an adversarial process. The assignments we give and the rules we set for them (such as the collaboration policy) are designed with the aim of maximizing what you take away from the course. I trust that you will follow these rules, as doing so will maximize your own learning (and thus performance on exams) and will maintain a positive educational environment for everyone in the class. I welcome and will solicit feedback from you about what more we can do to support your learning.

Sections

There will be weekly sections, which will be used primarily for practice solving problems of a similar nature to those on the homeworks and exams. Having digested the week's problem set and thought about possible approaches beforehand will enable you to get the most benefit out of section. 

Readings

In addition to the lecture notes, the required text for the course is:

 

�        Joseph A. Gallian.� Contemporary Abstract Algebra, 9th edition. �It has been ordered at the Coop, and for reserve in the libraries.

 

However, we will also be covering some material (particularly applications and algorithmic discussions) that is not in Gallian, so it is important that you also attend lecture. Some other books that may be helpful:

Related Courses at Harvard

  • Math 122 &123: Algebra I & II. A full-year course in abstract algebra. Because it is longer and assumes more background, Math 122-123 covers a number of topics that we cannot fit in AM 106, such as group representations, modules, and Galois theory. On the other hand, it usually does not include the algorithmic aspects and applications of algebra that we will cover in AM 106.
  • Math 152: Discrete Mathematics. A seminar-style course covering a variety of related topics in abstract algebra and discrete mathematics. It seems to have significant but not complete overlap with the "general theory" we cover, but that it has not much overlap with the applications and algorithmic issues we cover.

Changes in 2018

  • Computer Exercises: To allow exploration of more interesting examples, particularly around algorithmic issues and applications, we plan to include a number of computer exercises on the problem sets.
     
  • EthiCS Module: Like many computer science classes have been doing in recent years, we plan to include an ethics module in AM106 this semester, to be led by philosophy TF Kate Vredenburgh.

Diversity and Inclusion

I would like to create a learning environment in our class that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, ability, etc.). I (like many people) am still in the process of learning about diverse perspectives and identities. If something was said in class (by anyone) that made you feel uncomfortable, please talk to me about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please don’t hesitate to come and talk with me. As a participant in course discussions, you should also strive to honor the diversity of your classmates. (Statement extracted from one by Dr. Monica Linden at Brown University.)

Accomodations for Disabilities

If you have a health condition that affects your learning or classroom experience, please let me know as soon as possible. I will, of course, provide all the accommodations listed in your AEO letter (if you have one), but sometimes we can do even better if a student helps me understand what really matters to them. (Statement adapted from one by Prof. Krzysztof Gajos.)