Course Review: MATH 321

Real Variables II

“And now we have the tools the derive the Fundamental Theorem of Calculus, the formula you’ve been using since you were children.”

Text: Principles of Mathematical Analysis by Walter Rudin (3rd Edition)

Prof:  Dr. Gordon Slade

Dr. Slade was an engaging professor. He was clear while also motivating the content well. Once in a while, he would drop a wry joke, which brought a small amount of necessary levity to the class. One thing that stood out to me is that he would welcome clarifications and inquiries/corrections on the smallest details, especially on Piazza, rather than dismissing them which I think is helpful in such a class. Students’ often lack confidence in their first few serious proof courses and sometimes misunderstandings on seemingly small details can exacerbate that.


Difficulty

I found the course content more manageable than MATH 320, as it felt more well-motivated and we were applying a lot more of the theorems learnt in MATH 320. On the other hand, the homework was slightly harder as the proofs became more lengthy. Sometimes what was an entire proof question in MATH 320 is just a minor trick as part of proving some larger theorem. The midterms and final were all mostly doable, though I believe I made several trivial errors in the final. The final grades appeared to be scaled.


Key Concepts

Riemann-Stieltjes integral

Sequences of functions

Equicontinuity

Stone-Weierstrass Theorem

Arzela-Ascoli Theorem

Power Series

Fourier Series

 Hard Concepts

Metric space of functions: Takes a while getting used to discussing metric spaces where points are functions. Need to understand what neighbourhoods and open and closed sets refer to in this context.  Then you can apply a lot of the theorems already learnt to this metric space.

Inequalities: It may seem ridiculous to mention this, but some of the hardest questions involve finding tight bounds on functions using simple tricks such as triangle inequality, Cauchy, tangent lines, sums of squares in clever ways.

Examples: Coming up with examples (e.g. a point or a sequence) is not only useful in questions that explicitly ask for them, it can also be applied in conjunction with certain theorems taught in the course to show a certain object does not have a certain property. It is also a useful thing to practice before an exam as it helps you remember the conditions for certain theorems.  They can be really tricky to come up with on the spot sometimes.

Conclusion

Rewarding continuation of Real Variables I. Content was well motivated and homework was challenging.

Course Review: CPSC 311

Definition of Programming Languages

I prefer the word ‘thunk’ to expression closures.

Text: Programming Languages: Application and Interpretation by Shriram Krishnamurthi

Prof: Dr. Steve Wolfman

Wolfman was slightly less flipped in CPSC311, especially as the term progressed. His lectures were pretty entertaining and included a lot of live modification of the interpreter. Instead of sticking to textbook examples of dynamic scope and laziness, we often worked on languages in assignments and midterms where exotic adaptations and variants of these concepts were incorporated into a language in mind-bending ways.

Difficulty

I expected this to be an easy course. It ended up taking a lot of time. A lot of the programming languages concepts were completely new to me and combined with Wolfman’s avant-garde presentation of the material, I spent a great deal of time preparing for midterms and understanding the readings. The project we selected was in Elixir, and it was also very time-consuming as we had to learn distributed systems concepts in a new language with little guidance. That said, I feel the project was kind of a ‘choose-your-on-adventure’. You could do very well in the project with far less work if you chose wisely initially. Overall, the average was quite hight (around 77%) even though the midterm averages were quite low.


Key Concepts

Scoping

Deferred evaluation

Recursion

Continuations

Functional programming

SKI combinator

Interpreters

 Hard Concepts

Dynamic scope: Really messes with your brain, helps to write out the context.

Continuations: Odd concept. Helps to think of what function the continuation is bound to and apply it.

SKI combinator: Takes practice to get used to ‘algebraic’ manipulations of functions.

Conclusion

Learnt a lot. Enjoyed the project. Challenging course.

Course Review: CPSC 313

Computer Hardware and Operating Systems

“Virtual memory is one of the greatest ideas in the history of computer science.”

Text: Computer Systems: A Programmer’s Perspective by Randal Bryant, David O’Hallaron 3rd Edition

Prof: Dr. Donald Acton

Dr. Acton is a nice person and a passionate lecturer. His assignments are interesting and he adds a historical angle to the material. Unfortunately, certain administrative mishaps greatly hindered the delivery of the course. If the readings and online quizzes for each week were clearly outlined, assignments were screened by TA’s for errors and more TA’s staffed with monitoring piazza the course would have been a lot more enjoyable.

Difficulty

After returning from a systems heavy co-op, I found the material much less intimidating then CPSC 213. The assignments were lengthy but very doable and had a high average. The quizzes were more challenging, but if you practiced the exercises from the book and practice quizzes you should be fine. Readings are really important to get the most out of this course, especially as the slides are not amenable to self-study.


Key Concepts

Pipelining

Caching

Virtual Memory

Locality

File Systems

Exceptions

 Hard Concepts

Calculating cache miss rate for C code: Need to clearly visualize the cache and how the data structure fits into it.

Assembly implementation: Need to remember how the stack and registers can be used to pass parameters and store stack pointers and return addresses.

Conclusion

Somewhat interesting course. I found it a lot more detailed and less mind-blowing then CPSC213.

Course Review: MATH 302

Introduction to Probability

“Donald claims that he won the popular vote if you subtract the 3 million illegal voters. Assuming that 3 million people did vote illegally, compute the probability that Donald is correct.”

Text: Introduction to Probability by David F. Anderson, Timo Seppalainen, and Benedek Valko

Prof:  Dr. Martin Lohmann

Dr. Lohmann’s lectures largely consisted of (usually) interesting examples. Some students found his accent and his handwriting a bit challenging to follow. This, combined with the fact that he defers posting of lecture notes, made the course harder than necessary for such students. I did not have any difficulty understanding what was being said, and the few times I found his handwriting became hard to read, he clarified immediately. Also, if you ask a stupid question, expect some deft sarcasm in response!

Difficulty

While I find probability counter-intuitive, the assignments were all quite doable. Occasionally, harder questions marked with a star were provided. The first midterm was quite tricky, however, we were given a practice midterm beforehand that was conceptually quite similar to the actual exam. The second midterm and final were both significantly easier and we also were given similar practice material.


Key Concepts

Counting

Sets

Discrete vs Continuous Probability Distributions

Mean, Variance and Covariance

Joint Distribution

Convergence in Probability/Distribution

Conditional Probability

Moment-generating functions

 Hard Concepts

Counting: I always make incorrect assumptions w/regard to counting. I think the key to easier problems is to identify whether you are using replacement/no replacement and order/no order. For harder problems, it is often necessary to construct a bijection of sorts or use a symmetry argument.

Conclusion

Good to get some practice with counting and probability. About as much theory as you would expect from such a class.

Course Review: CPSC 320

Intermediate Algorithm Design and Analysis

“In this course, we mostly just do a high-level analysis of algorithms which are heavily used in the real-world. Today, we do the opposite. We actually implement an algorithm that is utterly useless.”

Text: Algorithm Design by Jon Kleinberg and Eva Tardos

Prof:  Dr. Steve Wolfman

Wolfman is really entertaining. He is also a big believer in ‘flipped classroom’ approach, so the lectures are mostly problem-solving. I like the practice, but others may not like the lack of highly structured lectures and the necessity to do readings ahead of the class. He thinks deeply about his students’ education, so few pedagogical decisions are arbitrary though they may appear so.

Difficulty

The assignments were initially easy but became increasingly lengthy and time-consuming. A background with mathematical proofs might help. I found the level of rigor required for the proofs lower than in CPSC 221, but the concepts were definitely more complex. The midterms were closely linked to the assignments and tested generic problem-solving skills rather than accumulated knowledge (though you probably need to know your definitions and the high-level idea of important algorithms). The tutorial and pre-reading quizzes were hit and miss, but they were more for familiarizing yourself with the topic than an actual assessment.The final was a bit longer than I expected, but all the questions were definitely doable if I had ~20 more minutes.


Key Concepts

Reductions

Divide and Conquer

Greedy Algorithms

Dynamic Programming

 Hard Concepts

NP-Completeness: Some reductions are very sophisticated, but they rarely expect us to come up with complex reductions.

Counterexamples: Sometimes it can take a lot of time to come up with a counterexample. Sometimes it’s better to list some constraints your counter-example must satisfy before diving into a brute-force search.

Conclusion

Enjoyable, useful sequel to CPSC221.

Course Review: MATH 320

Real Variables I

“You don’t really need a metric. All you need is the open sets.”

Text: Principles of Mathematical Analysis by Walter Rudin (3rd Edition)

Prof:  Dr Joshua Zahl

Dr Zahl was a structured, clear professor. He also provided useful insights into the ideas behind various proofs. I don’t think he has taught this course many times before, so he is probably still in the process of fine-tuning his delivery. Also, his surname literally means ‘number’ in German!


Difficulty

While the readings are pretty dense, the homework was quite doable by honours mathematics standards. I found the first midterm surprisingly easy. The second midterm was significantly harder, and I had not fully understood the concept of compact sets, so I did not do well at all. The class also got wrecked so there was a lot of scaling. The final was very reasonable.


Key Concepts

Properties of Real Numbers

Metric Spaces

Open Sets

Sequences

Continuous Functions

The Derivative

 Hard Concepts

Compact Sets: This concept has a deceptively Byzantine definition but is actually really fundamental to the course. Reading the history of the concept from Wikipedia and understanding many examples/counter-examples of sets that are or are not compact gave me a better intuition.

Sequences: Not a hard concept to understand, however an invaluable tool in certain seemingly intractable problems. Many times, it’s helpful to construct a sequence of points or even intervals and then use properties of such sequences in that space to prove the theorem.


Conclusion

Tough though doable class, if you have any background in mathematical proofs. One of the key learnings I took out this class, was the importance of spending time understanding complex definitions.

Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 3)

As was derived in Part 2, |c_{m,n}|= {n-(m-1)}\choose{m} where c_{m,n} denotes the set of binary strings of length n with exactly m non-adjacent ones.

Today we will analyze c_{n} the set of binary strings of length n with any number of non-adjacent ones. We will need some additional notation.

  • c_{n,0} denote the the subset of c_{n} ending with 0
  • c_{n,1} denote the the subset of c_{n} ending with 1

After some thought, we realize that c_{n,0} =c_{n-1} and c_{n-2}. We can then derive the recurrence |c_{n}| = |c_{n,0}|+|c_{n,1}|=|c_{n-1}|+|c_{n-2}|. After verifying the base case, we can conclude |c_{n}| = F_{n+2}, the Fibonacci Numbers!

Another way to compute |c_{n}| is |c_{n}| = \sum_{m=0}^{\infty} {n-(m-1)}\choose{m}.

Therefore F_{n+2} = \sum_{m=0}^{\infty} {n-(m-1)}\choose{m}.

With some shifting, we can solve for the n^{th} Fibonnaci number :

F_{n} = \sum_{m=0}^{\infty} {n-m-1}\choose{m}

While this formula can be quite easily verified inductively, its nice to construct it explicitly.

 

Mathematical Aside: Golden Mean Shift and Pascal’s Triangle (Part 2)

As we discussed in Part 1, we noticed a common pattern in the the m^{th} element in the n^{th} diagonal, d_{m,n},  of Pascal’s Triangle and the function c_{m,n}, denoting the set of binary strings of length n with exactly m non-adjacent ones. Today we derive an explicit formula for c_{m,n} in two ways.

Firstly, some more notation. The element in r^{th} row and k^{th} column in Pascal’s Triangle is denoted by {r}\choose{k}. Then we can see d_{m,n} = {n+m-1,m}. Unfortunately, c_{m,n} is at a slight shift. To see this, we think about how long the string needs to be just so can fit in m ones. The answer is 2(m-1). While the d_{m,n} is non-zero straight away, it takes c_{m,n} 2(m-1) increments to the length before it is non-zero. Therefore, |c_{m,n}|=d_{m,n-2(m-1)}= {n-(m-1)}\choose{m}.

Another way to see this requires knowledge of combinations.  If we consider the unconstrained system, the clearly we have u_{m,n} {n}\choose{m} options. We can construct a bijection from u_{m,n-(m-1)} to c_{m,n} as follows:

  • For every element in u_{m,n-(m-1)}, we can add append a 0 to all but the rightmost 1 and construct a unique element in c_{m,n}
  • For every element in c_{m,n}, we can add delete a 0 from the right side of all but the rightmost 1 and construct a unique element in u_{m,n-(m-1)}

Thus |c_{m,n}| = |u_{m,n-(m-1)}|= {n-(m-1)}\choose{m} as required.

We will use this to find an intriguing connection to the Fibonacci numbers in Part 3!

Course Review: MATH 316

Elementary Differential Equations II

“Even after that manipulation we still have some work left. We can’t get away with no work, we are not politicians.”

Text: Diffy Qs: Differential Equations for Engineer by J. Lebl

Prof:  Dr. Ian Frigaard

Dr. Frigaard was a humorous prof who had a lot of practical insights from an engineering perspective. The teaching was largely focused on examples, though a bit of theory was chucked in now and then for good measure. He was willing to humor a theoretical question if he had a bit of time.


Difficulty

I took it in the summer, so the material was probably simplified. The material is mainly straight-forward: we mostly practice lengthy manipulations involving Fourier Series. We had a quiz a week after the first week and he said he chucked the lowest quiz. All homework was optional, which was good because the homework was really lengthy (I am guessing the homework is mandatory during winter). While the quizzes generally tested basic questions on each topic, the final had slightly more complex questions.


Key Concepts

Fourier Series

Partial Differential Equations

Series Solutions

Separation of Variables

 Hard Concepts

D’Alembert’s Solution: Requires drawing of graphs, something I am not very efficient at.

Messy Algebra: The algebra on the final was a mess, with horrid fractions in each question, so get some practice.

Sturm-Liouville Theory: Slightly confusing until you realize you are not trying to solve the general Sturm-Liouville problem.


Conclusion

Very example heavy class. Mainly learned about 5 equations which had very similar solutions involving Fourier series and separation of variables. Would prefer a class where we learn more techniques and are exposed to a wide variety of equations instead. The algebra is also really gross.

Mathematical Aside: Golden Mean Shift and Pascal’s Triangle

I noticed something curious when I was working on my summer project last year. Basically, you consider the set c_n of binary strings (strings of length n where each symbol is either a 1 or a 0 and 1‘s are non-adjacent).  So we construct a table like

 

Length 1 2 3 4 5 6
Strings 0;1 00;01;10 000;001;010;100;101 0000;0001;0010;0100;0101;1000;1001;1010

And then count the number of elements of length n with m ones.

Number of ones [m] (below) Number of strings (below)
Length of string [n] (right) 1 2 3 4 5 6
0 1 1 1 1 1 1
1 1 2 3 4 5 6
2 0 0 1 3 6 10
3 0 0 1 4
4 0 0

 

Do you see Pascal’s Triangle hiding inside? Starting from the top left and diagonally down to the left. First one is 1,2,1, then is 1,3,3,1 etcThe explanation is simple enough. We are using the fact that the subset of  c_n composed of strings with m ones (lets call this c_{n,m}) can be made by taking an element in c_{n-1,m} and appending a zero to it or an element in c_{n-2,m-1} and appending a zero-one to it. We end up with the recurrence c_{n,m}= c_{n-1,m}+ c_{n-2,m-1}. If we consider d_{n,m} as the n^{th} element in the m^{th} diagonal, then we realize that d_{n.m} follows the same recurrence. This reccurence is well documented in the literature for calculating |c_n|, here we are just using this idea for subsets of c_n with exactly m ones to connect it with Pascal’s Triangle.

The adventure continues in Part 2!