Chapter 0: Introduction

[marikaswanberg]

Chapter name: Introduction

List of bugs/typos Before any sections

1. “This means that someone that thinks of numbers…” should be “This means that someone who thinks of numbers…”
2. The last sentence of the first paragraph has a capitalization typo; it says: “How much faster would 4n^2 operations be than n*y? and would this make any…”.
3. In the sentence “...the vast increase in our ability to measure, store, and communicate data has led to a much higher demand on developing better…”, I think you might mean to use “demand for” instead, but it depends on your exact meaning here (either way makes sense).
4. “The digit-by-digit standard algorithm is vastly better than iterated addition regardless if the technology implementing it is a silicon based chip or a third grader with pen and paper.” could be changed to “The digit-by-digit standard algorithm is vastly better than iterated addition regardless of whether a silicon-based chip or third grader is implementing the algorithm.”
5. “Theoretical computer science is largely about studying the inherent properties of algorithms and computation, that are independent of current technology. This sentence shouldn’t have a comma in it because of your use of “that.”
6. There are a few punctuation issues in the following passage: We ask questions that already pondered by the Babylonians, such as “what is the best way to multiply two numbers?” as well as those that rely on cutting-edge science such as “could we use the effects of quantum entanglement to factor numbers faster” and many in between.” I would change this to: We ask some of the same questions that the Babylonians pondered, such as, “What is the best way to multiply two numbers?” In addition, we ask questions that rely on cutting-edge science, such as, “Could we use the effects of quantum entanglement to factor numbers faster?” I think splitting this up into two sentences makes it easier to understand.

0.1 Extended Example: A faster way to multiply

1. “Amazingly, Karatsuba’s algorithm is based on a faster way to multiply two digit numbers.” (should be two-digit)
2. “The gradeschool algorithm works by transforming the task of multiplying a pair of two digit number” (should be “grade school” and two-digit).
3. “Of course if all we wanted to was to multiply two digit numbers,”
4. “If we used the gradeschool based approach then our cost for doubling the number of digits would be to quadruple the number of multiplications, which for n= 2^l digits would result in about 4^l = n^2 operations.” (I also have a suggestion about introducing the concept of the value of a number vs the length/representation of the number, but I'll post that in the other thread since it's not so much a bug or typo)
5. In the Karatsuba Multiplication algorithm, in the input line, “non negative” should be “nonnegative” with no space.
6. “If ≤ 2 then return ⋅ (using a constant number of single digit multiplications)” should be “single-digit”
7. Right under equation (4), “which equals to the value”
8. “Eq. (4) reduces computing the product of two n digit numbers to computing three products of floor(n/2) digit numbers” I’m improvising with mathematical notation here, but either way, it should read “two n-digit numbers” and “three products of floor(n/2)-digit numbers.” I suspect this is a recurring problem in the text, so I’ll keep noting where I see it for your convenience.
9. “For example, the natural way to describe Karatsuba’s algorithm’s running time is as following the recursive equation” I would change this to “For example, the natural way to describe Karatsuba’s algorithm’s running time is with the following recursive equation”
10. "However, this will not make much difference when we don’t worry about constant factors, since its not hard” (should be it's or "it is")
11. There is a formatting error in the same paragraph in the inequality: “Another way to show that this doesn’t hurt us is to note that for every number, we can find n′≤ 2 such”
12. Another formatting error: the yellow box from the previous page is awkwardly interrupted by Figure 4 (the figure explaining Karatsuba's algorithm for n-bit multiplication).

0.1.1 Beyond Karatsuba's Algorithm

1. There’s a formatting error about 10 lines from the top. It says “nxn” but it’s spaced very wide and looks like “n x n”
2. “In 1969 Volker Strassen noted that we can compute the product of a pair of two by two matrices” I think this should be “two-by-two matrices” but I’m not totally sure.
3. In the part with the equations for t1, t2, etc, I think it would be easier to read if each one were on its own line, and I think it would make some of the formatting better, but that’s just a matter of taste.
4. “This implies an algorithm with factor 7 increased cost” I think what you mean here is “This describes an algorithm with a factor of 7 increased computational cost”.
5. The following sentence is a little awkward because of the insertion of the “in the matrix size” “Unlike the case of integer multiplication, at the moment we don’t know of a nearly linear in the matrix size (ie O(n^2 polylog(n)) time) algorithm for matrix multiplication.” One way to fix this: “Unlike integer multiplication, we currently don’t know of any algorithms for matrix multiplication that are anywhere near linear in the matrix size (ie O(n^2polylog(n))time).”

0.2 Algorithms Beyond Arithmetic

1. “The backpropagation algorithm, that computes partial derivatives” There are two ways to fix this. 1) keep the comma and replace “that” with “which” 2) lose the comma and keep “that”. Based on the rest of the sentence, the first approach seems most natural.
2. “For the basic task, already of importance to the Greeks, of discovering whether an integer is prime or composite,” You are splitting up the phrase “task of discovering”, and it’s a little confusing to use the word “already” when talking about ancient Greeks. Also, you may want to say “Ancient Greeks” to indicate that you are not talking about modern-day Greeks. In addition, I think the word “discovering” is not quite correct. Overall, here is my suggested revision “For example, consider the problem of ‘primality testing,’ which is the the problem of calculating whether an integer is prime or composite. Despite efforts spanning back to the Ancient Greeks, efficient probabilistic algorithms for primality testing were only discovered in the 1970s, while the first deterministic polynomial-time algorithm was only found in 2002.”
3. Two periods at the end of the last sentence in this section: “But at least we now know the right way to ask it..” 0.3 On the Importance of Negative Results
4. Slightly awkward wording: “Another reason to study impossibility results is that they correspond to the fundamental limits of our world or in other words to laws of nature.” I would simply remove the bolded words and add a comma: “Another reason to study impossibility results is that they correspond to the fundamental limits of our world, to laws of nature.”
5. Also slightly awkward wording, and the period at the end of the sentence should go inside the quotation: “In his 300 B.C. book The Elements, the Greek mathematician Euclid based geometry on five “axioms” or “postulates”. I would change this to “Euclid, the Ancient Greek mathematician, wrote about geometry based on five axioms, or postulates, in The Elements in 300 B.C.E.” (also note that BC stands for Before Christ while BCE stands for Before Common Era and is thus secular).
6. Footnote 11: “Indeed, some exciting recent research has been trying to use computational complexity to shed light on fundamental questions in physics such understanding black holes and reconciling general relativity with quantum mechanics.” 1) it’s not the research that’s trying to use complexity, it’s the researchers, and 2) you’re missing the “as” in “such as”, and it needs a comma. I would change this to: “In recent exciting research, scientists have been trying to use computational complexity to shed light on fundamental questions in physics, such as understanding black holes and reconciling general relativity with quantum mechanics.”
7. “For example, much of modern Internet traffic is encrypted using the RSA encryption scheme, which relies on its security on the (conjectured) non existence of an efficient algorithm to perform the inverse operation for multiplication— namely, factor large integers.” 1) The first part is grammatically incorrect, and “non existence” should be “non-existence”. Also you may want to change the wording to “conjectured impossibility of efficient factoring” rather than “non-existence” since you use “impossibility” in other places in this chapter 2) the end of the sentence is awkward, and I think you don’t have to say the bit about “inverse operation for multiplication” because students will know what factoring is. I would just say “efficient algorithm to factor large numbers.”
8. Formatting error: the pink lecture recap box is split up between two pages
9. In the lecture recap: “Algorithms’ history goes back thousands of years and were essential for much of human progress.” I’m not sure if Algorithms’ is grammatically correct, but either way it’s a little awkward. I would instead say “The history of algorithms goes back thousands of years; they have been essential for much of human progress” 0.4 Roadmap to the Rest of This Course
10. Awkward wording: “There can be several different algorithms to achieve the same computational task.” One idea for changing this that, I think, gives the same message: “There is rarely only one algorithm to complete a given computational task.”
11. Awkward wording: “One of the main topics of this course is studying the question of what is the most efficient algorithm for a given problem.” I would change this to “A main topic of this course will be studying the most efficient algorithms for given computational problems.”
12. I also think the last two bullet points should be combined into one point. Maybe something like “A main topic of this course will be studying the most efficient algorithms for given computational problems using lower bound proofs, or proofs of the minimum amount of computational resources needed to solve the given problems.” You may also consider inverting the order of these two points by talking about lower bound proofs, and then saying that we can use them to prove that an algorithm is the most efficient.
13. Grammatical errors: “(1) define exactly what does it mean to solve P , and (2) define exactly what is an algorithm.” should be “(1) define exactly what it means to solve P, and (2) define exactly what an algorithm is.”
14. Grammatical error: “reasonable” approaches for computing” should be “approaches to computing”

Overall, this chapter is great. There's just some typos and grammar issues that I found. Also, my suggestions are by no means the only way to rewrite the problem areas.

[marikaswanberg]

If you're curious about a full list of grammar, punctuation, and style rules, I suggest The Elements of Style by Strunk and White. It's only about 80 pages of very systematic and clear explanations. I've found it extremely helpful for all kinds of writing.

[boazbk]

Thank you so much! This is great, especially given that I'm a non native speaker of English. I've read Strunk and White about 20 years ago, but maybe it's time to read it again..

[marikaswanberg]

You are welcome! I'm glad my edits were helpful

[akelser]

I think the definitions of B and C are mixed up in the Karatsuba Multiplication section