Algorithms and Data Structures: COMPSCI 220 Semester 2, City Campus

COMPSCI220 assumes that you are familiar with a number of notations and concepts from mathematics. Usually these are taught at school, but depending on your schooling background, you may have missed out on one or the other. Appendix E of the textbook is a place where help is at hand. Here is a quick refresher with a checklist that will let you assess whether you need to fill gaps.

This is what we expect students to be familiar with:

• Set notation: { }, |, ∈, ∪, ∩, ⊂, ⊆, ⊃, ⊇, |...|, etc. A set X is simply an unordered collection of zero or more elements. For example, the integers from 3 to 7 form a set, which we can denote as, say, X={3, 4, 5, 6, 7}, but also as X={3, 5, 6, 7, 4}, or as X={x | x is an integer and x ≥ 3 and x ≤ 7} (read "the set of all x such that x is an integer and x is greater than or equal to 3 and x is less than or equal to 7". That is, we read "{x|...}" as "the set of all x for which [some condition applies]".
  
  To indicate that something is an element of a set, we say ∈, e.g., as in "if x=4 then x ∈ X".
  The number of elements in a set X is also called the set's cardinality and is denoted as |X| or sometimes also as #X.
  
  If we have a set Y whose elements are all also elements in X, then we call Y a subset of X and write Y⊂X if |Y|<|X| and Y⊆X if |Y|≤|X|. E.g., {4, 5, 7} ⊂ {3, 4, 5, 6, 7}. When Y⊂X, we also say that Y is a "true" subset of X.
  
  The subset notation can also be used the other way around: If Y⊂X then X⊃Y, and if Y⊆X then X⊇Y, and we call X a superset of Y.
  
  To indicate that Y has elements that are not also elements in X, i.e., that Y is not a subset of X, we write Y ⊄ X. For example, for Y= {2, 5, 7}, Y⊄ X.
  
  If we have two sets X and Y, the set that contains the elements of X and the elements of Y is called the union of X and Y, denoted as X ∪ Y. For example, for X={3, 5, 6, 7, 4} and Y= {2, 5, 7}, X ∪ Y = {2, 3, 4, 5, 6, 7} = {x|x ∈ X or x ∈ Y}.
  
  The set that contains the elements that are in both X and Y is called the intersection of X and Y and is denoted as X ∩ Y. For X={3, 5, 6, 7, 4} and Y= {2, 5, 7}, X ∩ Y = {5, 7}.
  
  If Y is a subset of X, the set Y that contains all elements of X that are not in Y is called the complement of Y and denoted as Y=X\Y.
  
  A set with no elements is called the emtpy set and is denoted as ∅.
  
  If X and Y have no common elements, i.e., X ∩ Y = ∅, then X and Y are said to be disjoint.
  
  To see whether you are ready, test yourself by checking the statements below. Which ones are wrong?
  1. If Y⊂X, then X ∩ Y = Y.
  2. If |Y|>|X|, then |X ∩ Y| < |X|.
  3. If |Y|>|X|, then Y ⊄ X.
  4. If Y⊇X, then |X ∪ Y| ≤ 2|X|.
  If you found this easy, then you should be fine on this point. If you found this difficult, you will need help.
  
  (see also Appendix E.1 of the textbook)
• Mathematical notation, in particular that for sums. A sum is denoted by Σ, the uppercase Greek letter for "sigma". It usually comes with (at least) a subscript, which can be either below the Σ or to the lower right of the Σ (this is a formatting issue, but there is no mathematical difference, e.g.:
  
  If there is only a subscript, it's generally a variable such as i or j and then it means "sum up the term after the Σ for all values of i (or j)". It should then usually be obvious from the context which values i or j can take.
  Or it could be something like "x ∈ X", in which case we sum up over all elements x in X, e.g., for X={2, 3, 5, 7, 11}:
  
  If there are a subscript and a superscript, like in the first example above, then the subscript gives the starting value for the variable, and the superscript the end value, and the variable increments by 1 for each term of the sum. Simple as that. Think of it as the mathematical version of a for-loop where you add a term to a sum in each iteration.
  
  To see whether you are ready, convert the following Java-style for-loop into a sum using the above notation (you do not worry about type conversion or integer division issues here):
  
  

  for (int i=0; i<=n; i++) { 1/(i+1) };
  

  
  If you found this easy, then you should be fine on this point. If you found this difficult, you will need help.
  
  
• Floor and ceil notation: ⌈ x ⌉ rounds up to the nearest integer larger than or equal to x, e.g., ⌈ 3.2 ⌉ = 4. Similarly, ⌊ x ⌋ rounds down: ⌊ 3.2 ⌋ = 3.
• Exponential functions. For integers i and any other real number a, aⁱ is equal to a multiplied i times. E.g., 3⁵ = 3 * 3 * 3 * 3 * 3 = 243. However, i does not need to be an integer and, in fact, often is not. The value a is called the base and i is called the exponent.
  
  Some simple rules that apply to exponential functions are:
  
  
  1. a^-i = 1/aⁱ.
  2. a^i+j = aⁱ * a^j and a^i-j = aⁱ / a^j.
  3. (aⁱ)^j = a^i*j.
  
  You will need to know how to use these.
  
  Another thing that is very important to know is that exponential functions aⁱ with a>1 grow very quickly in value as i increases.
  
  A special case of exponential functions is the exponential function e^x, where e is Euler's (pronounced "Oil-ah") constant (approximately 2.718...). It is special because e^x is its own derivative and, with the help of the natural logarithm ln (see below) all other exponential functions aⁱ can be transformed into e^x by setting x=i ln a.
  
  To see whether you are ready, figure out which of the following statements are true:
  
  
  1. e^i-j = 1/e^j-i.
  2. a^k(i+j) > a^k*i*a^k*j.
  3. aⁱ > a*i for a>1 and all or almost all i>0.
• 
  If you found this easy, then you should be fine on this point. If you found this difficult, you will need help.
  
  
• Logarithms. Logarithms are the inverse of exponential functions. So if a^x = y, we write log_ay = x and say that "x is the logarithm to base a of y". Often we write log, without a subscript defining the base. Commonly used logarithms are "logarithm to base 2" (which is used a lot in computing), "logarithm to base 10" (which is used a lot in engineering), or even "logarithm to base e (natural logarithm)". However, these only differ by a multiplicative constant, which we will often be able to neglect in COMPSCI220.
  If you see ln x, then that always means log_ex (the "natural logarithm").
  
  The simple rules that apply to logarithms result from those for exponential functions (and why don't we use lg here just to get you used to it?):
  
  
  1. lg (x*y) = lg x + lg y.
  2. lg (x/y) = lg x - lg y.
  3. lg (x^y) = y * lg x.
  
  Again, you will need to know how to use these.
  To see whether you are ready, figure out which of the following statements are true:
  
  
  1. lg (x+y) = lg x / lg y.
  2. lg (a^x+y) = x * lg a + y * lg a.
  3. a^k(i+j) > a^k*i*a^k*j.
  4. aⁱ > a*i for a > 1 and all or almost all i>0.
  
  If you found this easy, then you should be fine on this point. If you found this difficult, you will need help.
  
  (see also Appendix E.4 of the textbook)
• Proof by induction. Sometimes we'll want to prove that something (a mathematical statement) is true for all (typically non-negative) integers n, or at least for all integers n greater than or equal to some integer n₀ (if it's meant to be true for all non-negative or all positive integers, then we choose n₀=0 or n₀=1, respectively). A common technique to prove this is called mathematical induction or simply induction. It involves proving first that the statement is true for n₀ (sometimes called the basis). Then, one proves that if the statement is true for some n (the induction hypothesis), it must also be true for the next integer n+1 (the inductive step from n to n+1). This then completes the proof.
  
  Confused? Think of it as the mathematical equivalent of the domino effect (like this). If you can show that if domino number n falls over, domino number n+1 must also fall over, then your chain of dominos may or may not fall over - because one domino (domino n₀) must make the start. If both these conditions are met, you know that all dominos for n greater than or equal to n₀ will fall over.
  
  OK, but how does it work in maths? Example: Take Gauss's formula for the sum S_n of all integers from 1 to n: S_n=(n+1)n/2. How do we show that it's true? Choose n₀=1. Then we know that S₁=1, but we can also see that (n₀+1)n₀/2 = (1+1)1/2 = 1. So clearly the formula is correct for n=n₀=1. That's our first domino falling over. Now comes the next step. To get from the sum S_n for all integers up to n to the sum S_n+1 of all integers up to n+1, all we need to do is add n+1 to S_n: S_n+1 = S_n + n+1. But our hypothesis says we know the formula for S_n: S_n=(n+1)n/2. So we can plug that in in place of S_n and get:
  
  S_n+1=(n+1)n/2 + n+1 = (n+2)(n+1)/2.
  
  which is the same formula, just for n+1 instead of n. So we've shown that if the formula gives the correct result for n, it also gives the correct result for n+1. That's our proof that the next domino will always fall over, and completes our proof of the formula.

This doesn't take long to grasp but makes life a lot easier when it comes to reading and understanding formulas!

In some contexts, we will also extend our insights systematically step-by-step using the established mathematical tools of definitions, lemmas, and theorems. A definitions is used to make it clear what a certain term means, what we are going to call something, or how we will be using a certain notation. A theorem is a statement we claim to be true, and it always requires a proof. A lemma is like a small theorem that we prove to lead us up to the proof of a more extensive theorem. As a general rule, we don't claim that something is true unless we can also prove it.

Appendix E of the textbook contains additional mathematical concepts that you need to know for the course: look at E.3, E.5, E.6, and E.7 - the tools above should help you understand most of it.

That's all, really.