While the specifics vary from term to term, PMATH 333 largely exists to help fill in the ideas from MATH 137/138/237 which were left imprecise or unproven. That said, the ideas covered in this course are extremely interesting and deeply interconnected.
Depending on your offering, the course may begin with an introduction of \(\mathbb{R}\) as the unique "complete, ordered field", the implications of this characterization on \(\mathbb{R}\), and the reasons why other commonly seen sets, like \(\mathbb{Q}\) or \(\mathbb{Z}\), might or might not share the same properties as \(\mathbb{R}\).
Regardless of offering, PMATH 333 will provide an introduction to basic point-set topology. We start by looking at open and closed intervals in \(\mathbb{R}\), and the big ideas to follow come from a desire to generalise and extend our ideas about what it means for a set to be "open" or "closed" to a general normed vector space setting (where a "norm" represents a consistent measure of "size" for all elements in a vector space). A common theme that emerges is that many properties like openness, compactness, and continuity have many seemingly different characterisations that, by some wild magic, end up being equivalent!
Earlier on — maybe without realising it right away — you'll be working with infinite dimensional vector spaces like \(C([0,1])\), the set of real-valued functions continuous on the interval \([0,1]\), or spaces where all of the elements are infinite sequences of elements in another space! Within each of these spaces, you'll play with different notions of what it means for a sequence to converge to an element, and hence different notions of what it means for a function in that space to be continuous. Sequences and ideas about convergence appear constantly in this course, because they're so central to answering questions about the basic properties of the spaces we're working in. Different stronger and weaker forms of continuity and convergence are also introduced in this context. Depending on your offering, you might also spend some time investigating ideas of connectedness and path connectedness, which can be used to describe some sense of "disjointness" and "separatedness" in subsets of vector spaces.
The latter half of the course focuses less on topology and more on things that feel more "calculus" — power series and Taylor's Theorem, Riemann integrability, Fubini's Theorem, and so on. A lot of the content in this section will be rigorous proofs of the theorems left un-proven in MATH 237. The highlight of this section is generalising Riemann integration to real-valued functions of multiple variables by generalising the "limiting rectangles (2-cubes)" idea to "limiting n-cubes" in a way that's airtight.
One of the core practices of pure math is to find patterns between similar objects, and abstract away the specifics, so you can ask general questions and prove theorems that apply to many different objects at the same time. In abstract algebra, we do this with familiar algebraic operations. We know lots of different objects that you can add and multiply — integers, rational/real/complex numbers, matrices, polynomials, functions — and in abstract algebra, we unify all of these. Informally speaking, a ring is a set where you can add elements and you can multiply elements, where addition and multiplication behave as they do in the above examples.
By proving things about rings in general, we can learn about all of those objects individually. A lot of the theorems from elementary number theory in MATH 135/145 or linear algebra in 136/235/146/245 will be special cases of theorems proven in PMATH 347.
The other major object of study in PMATH 347 is called a group, which has even less structure than a ring. It’s a set that has a single invertible operation, which we generally denote it the same way we denote multiplication, but sometimes we'll use \(+\). The integers under addition form a group; the set of invertible linear transformations under composition form a group; the set of nonzero real numbers under multiplication forms a group (you can’t divide by 0); the set of permutations of n elements forms a group, again with the operation being composition. In PMATH 347, you focus on developing a lot of the general theory of groups, which gives you facts you can apply to any of these examples (any many more!) There are some really deep connections between the idea of symmetry and group theory, and so it shows up all over the place in pure and applied math, and even physics and chemistry. See the PMATH 445 description for a little more elaboration on this!
Almost everyone can recite the quadratic formula — it’s a clean, nice way to get the roots of any quadratic. It turns out there’s also a cubic formula! Given any cubic, you can express the roots in terms of the coefficients, but that formula is a bit of a monster. There’s also a quartic formula which solves degree 4 polynomials, but writing it in terms of the original coefficients with no substitutions takes several pages.
Given that there was a linear, quadratic, cubic and quartic formula, mathematicians naturally assumed that we could keep finding these formulas, and searched fruitlessly for one starting in the 16th century. However, in the early 19th century, a complete proof was given that there is no quintic formula! There is no way to express the roots of an arbitrary quintic in terms of \(n^{\text{th}}\) roots, multiplication, division, addition, and subtraction of the coefficients. The proof of this fact relies heavily on some very interesting group theory, and a slightly more sophisticated version of the proof in fact implies that there are quntics which have a root that isn't expressible in terms of the above operations.
Galois Theory provides a relatively elementary, very elegant proof of the above fact, but it gives us far more power. Galois theory allows us to look at a specific polynomial and determine whether its roots can be expressed in terms of the operations listed in the previous paragraph. Not only that, Galois theory also provides many algebraic and number theoretic insights about fields.
A field is a set with addition and multiplication, where you can divide by nonzero elements. The integers are not a field since \(\frac12\) is not an integer, but the rational numbers are. Galois theory is fundamentally about turning questions about infinite fields into questions about finite, easily understood groups. The facts stated above about polynomials are proven by considering the structure of a field containing the rational numbers and the roots of the polynomial; but this technique allows many more interesting proofs, including the impossibility of trisecting an angle with a compass and straight-edge.
Galois theory provides a variety of incredibly beautiful and interesting applications of the group theory ideas from PMATH 347, and has applications across number theory, cryptography, abstract algebra, and it even has some deep connections with algebraic geometry and algebraic topology.
One of the major goals of the first year calculus courses is to develop the theory of continuity, limits, approximations, sequences, and the real numbers in general. What is a precise definition of a limit? How do we know when a function is continuous? The answer is the very clever epsilon-delta definition, which allows us to define ideas like limits in terms of a distance; for the real numbers, the distance between two numbers is measured using the absolute value function. In second year, you do something analogous with vectors, measuring distance with a norm instead of the absolute value function. In PMATH 351, you’ll generalize this even further. A set with some notion of distance is called a metric space, and the distance function is called a metric. Using a metric, you can define all the ideas from first and second year in a much more general setting, which gives rise to some extremely interesting examples. This idea of a metric space has applications in areas as diverse as geometry, number theory, and even abstract algebra, and PMATH 351 introduces a ton of interesting examples of these spaces.
Using the general theory the course develops, you can then go back and prove some very powerful theorems about the real numbers, and continuous functions on the real numbers. Just for a sneak peak:
Welcome to the world of complex numbers, where everything you'd ever want Just Works. Complex analysis is often described as black magic, and for good reason. To elucidate, here are a few statements that sound like utterly deranged, wishful thinking gone unchecked:
As it turns out, these statements are all true! How could this happen? Well, differentiability is actually an extremely strong condition in the complex numbers. In this course, you'll learn why all of these things are true, and you'll use them to solve interesting problems.
You'll also spend a lot time looking into the idea of a contour integral, which you can think of as taking the "complex area" between a function and some curve drawn on the input \(x,y\) plane. Consistent with the themes of the course, there turn out to be some other wild, unbelievable results about these contour integrals too:
You will finish this course bitterly regretting the weakness and unpredictability of the real numbers. Alas. That said, there are also many problems of real functions on a real domain which can be solved much easier by using a bit of complex analysis. You'll see some of these problems near the end of the course. Complex analysis has plenty of applications in applied math and physics, and it regularly appears in more "pure" contexts, ranging from number theory to real analysis!
Riemann integration is quite messy. For example, there are sequences of functions where every function in the sequence has Riemann integral 0, but the limit function isn't integrable at all. That’s awful! In general, there are very few functions which are Riemann integrable, and so a natural question to ask is whether or not there’s a better integral we can define, that works nicer with limits of function sequences, but which agrees with the Riemann integral on normal functions. The answer is yes! The core insight is to develop what’s called a measure on the real numbers. A measure is a way of assigning length to an arbitrary subset of the real numbers - we know that an interval like \([0,1]\) should have length 1, or more generally, an interval \([a,b]\) should have length \(b-a\). If we take two disjoint sets, the length of their union should be the sum of their lengths, and length should be translation invariant, in that if we shift the whole set left/right, its length shouldn’t change. These rules by themselves actually turn out to be enough to uniquely define a measure on the real numbers, called the Lebesgue measure!
With the ability to determine the lengths of arbitrary subsets of \(\mathbb{R}\), not just intervals, we can develop a much more general integral; instead of doing a Riemann sum with just rectangles, we chop up an interval in a much cleverer way, which might result in some weird shapes, but we can still measure the length, and so we can still calculate \(\text{length}\times\text{height}\). If you do this properly, you can integrate many more functions, and your integral will behave much more nicely with limits. Once you have this, you can develop a lot of very interesting theory surrounding these integrable functions. Note that you won’t be stuck computing integrals! This course is much more about developing a nicer theory.
One of the applications of this nicer theory is the development of Fourier series. A major result of the course is that almost any function you’d ever run into can be written as \(\sum_{k=-\infty}^{\infty}a_ke^{-ikx}\), where each \(a_k\in\mathbb{C}\). This is useful for theory, since exponential functions are very nice, but it also helps to solve many practical problems in signal processing, electrical engineering and differential equations. The theory is developed fully in this course, and enough examples are done to prepare you for theoretical applications.
In PMATH 450, we developed a theory of integration on the real numbers using a measure — some way of assigning length to subsets of the real numbers. In PMATH 451, this is generalized to a much wider class of space. First, you can do integration on \(n\)-dimensional space by developing measures on \(\mathbb{R}^n\). A measure on \(\mathbb{R}^2\) should be thought of as area, on \(\mathbb{R}^3\) a measure is volume, and so on. However, a measure can be put on any set, and a corresponding theory of integration can be developed, and many of the theorems from PMATH 450 will be proven in full generality, and some new theory will be developed.
In PMATH 450, some theory of \(L^p\) spaces is developed; the space \(L^p([a,b])\) is the set of functions from \([a,b]\to\mathbb{R}\) whose \(p^{\text{th}}\) power is integrable. In PMATH 451, you begin to develop some more analysis on those spaces, and consider their structure as vector spaces. Further, since the course develops integrals on a much larger class of space, we can consider \(L^p(X)\) where \(X\) is any space that has some notion of integration. The ideas developed here connect beautifully with linear algebra and analysis, and provide some very important examples for functional analysis.
Finite dimensional linear algebra is, as a whole, really well understood. Part of this comes from the fact that, in the finite dimensional case, linear algebra doesn't require much analysis. Recall that a norm on a vector space is a way of measuring length, and using a norm, you can define continuous functions on vector spaces. A major theorem of PMATH 333 is that, no matter what norm you put on a finite dimensional vector space, the same functions will be continuous. So, while I might be able to find 2 or 100 or infinitely many different norms, a function is continuous under one of them if and only if it is continuous under all of them. Further, every linear transformation on a finite dimensional vector space is continuous. This means that almost all the interesting questions in finite dimensional linear algebra are purely algebraic, since we get continuity for free, and there’s never really a need to specify which norm/metric we're working with. Additionally, no matter what norm we pick, the space is complete, which essentially means that there are no "missing" elements.
In the infinite dimensional case, this becomes incredibly false. There are spaces which are isomorphic as vector spaces, but equipped with dramatically different norms and so "feel" completely different (for example, the space of continuous functions on \(\mathbb{R}\) and the space of sequences with real entries are isomorphic as vector spaces, but come on, they're clearly different). There are infinite dimensional vector spaces which are not complete, and there are infinite dimensional spaces that are complete under one norm but incomplete under another. A complete vector space with a norm is called a Banach space.
All of the above means that, in the infinite dimensional case, we can do interesting analysis! We start to ask about transformations which aren’t linear, but also continuous, and instead of just thinking about dual spaces, we think about the dual space of continuous linear transformations to our base field.
One of the most common vector spaces that you'll examine is the vector space of continuous linear transformations between two Banach spaces. This turns out to itself be a Banach space, and it has a really interesting structure; studying it is interesting in its own right, but can also give insight into the original spaces. There are also many beautiful results about continuous linear operators in general which can be proven by looking at the structure of these operator spaces.
Finally, in this course, you’ll see some point-set topology, which is sort of the most general way to talk about continuity (no need for a distance function!). Putting an interesting topology on a vector space instead of a norm can lead to some incredibly deep results about it and its dual space.
There's nothing here! If you can offer a good high-level, well-motivated description for a course you've taken, kindly get in touch with a club exec! :)
Did you enjoy graph theory in MATH 239/249? Then this course is for you!
We'll start by looking at connectedness in graphs, and introduce a very powerful set of theorem. The Menger's Theorem and their corollaries will be used throughout the course to prove and categorize lots of graphs when the connectedness is known or bounded.
Then there will be a simple introduction to algebraic graph theory, giving us the fundamental cycle space and fundamental cut space. This will give us tools to prove 2 parts of the Kuratowski's theorem for planar graphs.
The final bit of the course will be on matchings, in 239, only the bipartite cases were considered, but in 342, we will see Tutte's Theorem and the results it leads to that will give us conditions for graphs to have a perfect matching.
The fact that CS majors can use this course to fulfill degree requirements should give you some clue as to what to expect - this course is a high-level look at cryptography (the process of building secure systems to hide, verify, or sign data) and cryptanalysis (the process of trying to expose weaknesses in said systems).
When building secure systems, there may be a number of properties that we look for - confidentiality (keep data secret unless you’re authorized to see it), integrity (prove that data has not been tampered with), origin authentication (verify that data came from a trusted source), etc. The way to do this is to build “cryptographic primitives” that let you do one basic thing really well - for example, an encryption algorithm is a cryptographic primitive to ensure confidentiality, since you can’t read the data until you have the encryption key. In CO487 we focus on building these cryptographic primitives using the mathematical tools that we have, and seeing how these primitives are used (correctly or incorrectly) to enforce these properties that we are looking for. For a deeper dive on the mathematical tools, consider looking at CO 485.
We start by covering simple encryption algorithms like the one-time pad and the Vigenère cipher, discuss the limitations of these algorithms (key length and security respectively), and then move on to progressively newer algorithms to solve these problems better.
Symmetric-key encryption schemes like DES (Data Encryption Standard) and AES (Advanced Encryption Standard) are discussed. A symmetric-key encryption scheme is one that uses the same encryption key to encrypt and decrypt the ciphertext. Techniques are discussed to break these encryption protocols, and in assignments you will be required to use these techniques to decode simplified versions of these protocols. Finally, techniques are discussed to make breaking these encryption schemes harder - you will also be required to design new encryption algorithms.
We also discuss hash functions and message authentication codes (MACs). A hash function is a function that returns a fixed-size output for any arbitrary-size input, and a cryptographic hash function can be used for checking data integrity. A MAC is similar but also ensures integrity of the data source. We cover MACs very similarly to the symmetric-key encryption algorithms above - we learn how these algorithms work, then try to break them, and then try to see how to design stronger algorithms that are harder to break.
Next, we discuss public-key encryption and signature schemes like RSA and DSA. Different algorithms are discussed to efficiently compute these functions on a standard computer, which rely on increasingly large polynomials and prime numbers. Public-key cryptography is also used to share secrets to facilitate symmetric-key cryptography, using algorithms like Diffie-Hellman key exchange.
The final part of this course covered quantum computing and how we may be able to break a lot of the algorithms discussed above using quantum techniques. Assignments cover applying these techniques to break algorithms like RSA, given a quantum computer. Finally, some algorithms for post-quantum cryptography - cryptographic algorithms that are resilient to attacks by quantum computers - were discussed at the end, but not tested.
This is not in a course in C; neither is it a course in Racket. This course is pretty special in that it shifts focus very frequently, but a common throughline is the comparison of functional and imperative paradigms. It's also a course in interrogating the convenient lies of functional languages. Questions are asked about the nature of programs with respect to their state and representation. As you learn about certain imperative features in C, you'll learn about similar features in Racket that were previously hidden, and how imperative language features can actually be totally mimicked in functional languages. In fact, a huge section of this course (along with the tutorials) focuses on building interpreters, in both Racket and C, for various subsets of Racket.
Fair warning: the material about interpreters is generally taught in the Haskell language, which is another functional language (although with a very un-Racket-like syntax) that you'll gain a basic understanding of through the tutorials.
In this course, you will learn to thoroughly reason about your programs and their states; you'll learn how to design efficient, well-designed programs through your assignments (which are typically reasonably short); and you'll learn a lot of really cute things about both C and Racket. CS 146 covers about double the content of CS 136, but instead of C being the learning objective, C is used as a means to greater, much less tedious ends. Don't let that intimidate you; it's a really fun course that will expose you to a lot of interesting computer science. No prior experience required, except for CS 135/145.
Want a job in CS? This is the big course you'll need. Although C++ is its language of choice, CS 246 isn't a course in C++; it's a course that's fundamentally about software architecture and design, especially as it relates to modern object-oriented languages like C++ (you will be taught C++ very thoroughly though; don't worry).
The big difference between C and C++ is that C++ supports classes, which are basically structs from C which, in addition to having data members, can have member functions (also called methods) which you can call "on" a particular instance/object of that class. Classes also support visibility on members, so you can "hide" certain members from the public eye in your code. This is motivated by a discussion of encapsulation, in which you play a very long game of "How Much Can We Trust The Client?", and lower the trust at every turn. The addition of classes, along with other special C++ machinery like overload resolution, runtime polymorphism, and templates, will let you write code that's infinitely more readable, reusable, and resilient to change. It's not about what you do; it's about how you do it.
In this course, you'll spend a lot of time studying and using several design patterns: generic, widely-used solutions to common types of problems encountered in software design. Your job will be to figure out which design patterns are appropriate to apply in certain situations, and how to specialise them for the specific context.
There's nothing here! If you can offer a good high-level, well-motivated description for a course you've taken, kindly get in touch with a club exec! :)
There's nothing here! If you can offer a good high-level, well-motivated description for a course you've taken, kindly get in touch with a club exec! :)