5
$\begingroup$

I'm a recent Math major who switched to a double major with Computer Science.

I'm petitioning my CS Department Chair to allow me to take Real Analysis in place of Algorithms. I've already taken Data Structures & Algorithms, and from a cursory read of the Algorithms textbook, it seems to be something I could learn on my own time in lieu of classroom instruction. Not only that, financial aid can only finance so many courses before it dips into my pocket.

I'm really interested in taking Real Analysis ; it is the bedrock course for any mathematical sciences. However, Real Analysis concerns topics such as limits and continuity, whereas Algorithms (except for a few cases) deals with computations in the realm of finite, discrete intervals.

Thus, I'm taking a pause and asking TCS: is my intention of taking Real Analysis in place of Algorithms short-sighted? The only justifications I can think of is

  1. Real Analysis is a core course for anyone thinking of doing mathematical sciences, especially for graduate school.
  2. Real Analysis is a staple of graduate-level Computer Science.

Basically; what is the point of Real Analysis for Computer Science? It doesn't seem to hold much value for a academic field concerned with computations in the discrete.

Thank you for your responses.

Edit; Due to the one of the responses by Clement, I should elaborate. Real Analysis presents a challenge to me in terms of self teaching. I would rather not develop faulty tricks and methods to understand what i am learning. I rather study under the guide of a math professor who knows what they are doing, and I can reach out to when facing difficulty in comprehension of the material. Algorithms does not seem to present as big a challenge.

$\endgroup$
10
  • 2
    $\begingroup$ Not quite what you're asking, but I'm curious here. What is the part of the argument for "I could learn [algorithms] on my own time" that does not apply to real analysis? Isn't the premise of that statement (for both) that the lectures, assignments, office hours, etc. provide nothing the textbook does not already offer? $\endgroup$
    – Clement C.
    Commented Feb 24 at 3:09
  • 1
    $\begingroup$ @ClementC. This is a strong argument that has not occurred to me prior. Thinking of it now, Real Analysis is very imposing in a way that Algorithms does not seem to be. Due to that, I rather be instructed by a mathematician who knows what they are talking about rather then self-teach and possibly fall into faulty methods of understanding. Algorithms just doesn't seem to be that complex to understand in comparison. $\endgroup$ Commented Feb 24 at 22:27
  • 1
    $\begingroup$ Two Qs: 1) What is the difference at your school between "Data Structures & Algorithms" vs "Algorithms"? And 2) What do you want to do with these things afterwards? (Learning-wise, career-wise, etc.) Both Qs have bearing on my potential answer. $\endgroup$ Commented Feb 26 at 16:17
  • $\begingroup$ Sometimes continuous models are easier / more amenable to solve computationally. Example: en.m.wikipedia.org/wiki/Linear_programming_relaxation -> the continuous solution is then an approximate solution for the discrete problem (ORLY!). Best to be knowledgeable in both worlds. $\endgroup$ Commented Feb 26 at 19:44
  • $\begingroup$ Many algorithms for optimization and sampling are based on discretizations of continuous processes. From this perspective, convergence of these continuous processes are necessary for convergence of the discretized processes. Insights from analysis can help design better continuous processes and discretizations. $\endgroup$
    – Holden Lee
    Commented Feb 27 at 18:24

2 Answers 2

6
$\begingroup$

[This is only partly an answer but way too long for a comment]

Real analysis is definitely relevant for computer science! It gets used all over the place in scientific computing. Take a look at any Numerical Analysis book. Concepts covered in real analysis like compactness and continuity showing up in computability theory (e.g. Turing reductions correspond to Turing functionals on Cantor space, which are continuous functions) and in the construction of oracles in complexity theory (lookup "generic oracles" e.g. An oracle builder's toolkit).

("Analysis" in general is even more widely useful, but since your Q is specifically about a Real Analysis class I will stick to that. Just some mentions: differential equations can be used to derive phase transitions in combinatorial settings such as random graphs, SAT algorithms, clique algorithms, etc. Complex analysis can be used to estimate growth rates as in the generating function approach to bounding recurrence relations in algorithms. And it shows up a lot in things like the Unique Games Conjecture, hardness of approximation, and metric embedding.)

That said, I don't think Real Analysis is a valid "substitute" for Algorithms from the point of view of a CS degree. The point of an Algorithms class is not just to have another mathematically formal/rigorous course in the CS curriculum. The point is that algorithms are a core part of computer science (maybe even "the core", but I don't want to quibble). Perhaps unfortunately given your question, I do think that the same cannot be said for Real Analysis, however useful it might be in certain parts of CS.

Personally: if I saw a CS Theory grad school applicant was missing an Algorithms class from their transcript, that would be a big question mark that needed some explaining. e.g. I'd want a really good answer to the question "How do you know you want to do TheoryCS if you haven't even taken an algorithms class?" (There can be good answers to that question! But it's a risk.)

If you think you can self-learn the Algorithms material so easily, can you propose testing out of the class? That would hopefully satisfy your department's requirement, still let you have it on your transcript, but hopefully take much less time than actually taking the class. (Unfortunately it is unlikely to help tuition-wise, as schools tend to be sticklers about "if it's on your transcript someone must have paid tuition for it".)

$\endgroup$
2
  • $\begingroup$ Interesting, when I am judging applications for a CS Theory grad school, I am looking for math classes. It doesn't matter which. A CS grad student can learn algorithms by being a TA, but that would be much harder for Real Analysis. $\endgroup$ Commented Apr 6 at 11:47
  • $\begingroup$ @JakubOpršal I also look for math classes. But, as I said, if a student hasn't taken algorithms (or, say, theory of computation) how do they know they want to do Theory? $\endgroup$ Commented Apr 6 at 14:33
1
$\begingroup$

Real Analysis is very important to certain branches of computer science. I am assuming you know the epsilon-delta definition of the limit of a function, but I would argue that the heart of limits and real analysis is sequences. In fact, the following definition is equivalent to the epsilon-delta definition:

Let $f:\mathbb{R}\to\mathbb{R}$ be a real function. Let $a, L \in\mathbb{R}$. We say the limit of $f(x)$ as $x$ approaches $a$, denoted $\lim_{x\to a} f(x)$ equals $L$ if for every sequence $(x_n)_{n\in\mathbb{N}}$ such that $x_n \to a$ the sequence $\big(f(x_n)\big)_{n\in\mathbb{N}}$ satisfies $f(x_n) \to L$.

Thus if you are analyzing a function that computes or optimizes a function by producing sequences of points, you need real analysis. Also real analysis is used in the proof of the Universal Approximation Theorem in Machine Learning.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.