CS561-FoundationsofArtificialIntelligence-SvenKoenig

webmaster: Sven Koenig

Math

In general, as graduate student in computer science, you should have good undergraduate knowledge of computer science because otherwise the material in graduate classes might confuse you. Fortunately, CS561 only makes very few assumptions about your background knowledge, as outlined in the syllabus.The selftest below is a 6-question background evaluation that can help you to evaluate your background knowledge but does not test the recommended preparation of the course completely. It tests only knowledge of programming in C/C++ and (for the most part) high-school mathematics. The questions are chosen so that they relate to CS561:

1) On a calculator that can calculate only the ln function, how do you calculate the logarithm of 10 to base 2?

This is a question about logarithms. We will use logarithms, for example, in the context of decision trees.

Possible readings:

2) Differentiate exp(2x) with respect to x, where exp() is the exponential function.

This is a question about derivatives. We will use derivatives, for example, in the context of gradient descent and perceptrons.

Possible readings:

3) Can you program fluently in C or C++? Possible answers are "yes", "no" or "I am not sure".

This is a question about C/C++. We will use C/C++ in at least one of the three projects.

4) When you roll 2 fair dice, how likely is it that the combined total is 4?

This is a question about probabilities. We will use probabilities, for example, in the context of Bayes' rule, Bayesian networks and Markov decision processes.

Possible readings:

5) How many x's does the following pseudo code print?

int i, j;
for (i=1; i<100; ++i) /* i ranges from 1 to 99 */
  for (j=i; j<100; ++j) /* j ranges from i to 99 */
    printf("x"); /* print an "x" */
printf("\n"); /* advance to the next line */

This is a question about C/C++ and finite sums. We will use finite and infinite sums, for example, in the context of Markov decision processes.

Possible readings:

6) If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is immortal or a mammal, then it is horned. Is the unicorn horned? Possible answers are: "yes", "no", "neither yes nor no", "both yes and no" and "this is unknown".

This is a question about propositional logic and commonsense reasoning. We will use propositional logic, for example, in the context of knowledge representation, discuss how to use resolution to reason with propositional logic and generalize it to first-order logic.

Possible readings:

The 6-question background evaluation is so short that it cannot cover all important topics. We suggest that you look into the textbook to understand better the importance of the topics (some topics we will need in only one lecture, others we will need in several lectures), which level of understanding of these topics is required and how your background knowledge compares to it. We believe that a good understanding of elementary mathematics is not just important because you need to use that knowledge from time to time (and certainly in the exams) but also because it helps you to think clearly about new computer science material.

You will need to understand the material in CS561 sufficiently well to be able to solve difficult new problems with it. Some students have asked us how they can catch up on the subjects. It turns out that, due to the basic nature of the material, neither the computer science department nor the mathematics department offer a single refresher course that covers all of the material. For every single topic, there exist early undergraduate classes at USC that cover it but, it seems, they typically cover much more advanced material as well. Therefore, the TAs have compiled a list of freely available reading material that covers the topics covered by the 6-question background evaluation, except for C/C++. These are the links given above.

If you would like to exercise your math skills beyond what is needed for CS561, the chair of the math department recommends the following classes: Probability (407 or 505a), Foundations of Discrete Mathematics (400), Applied Algebra (370 or 574) and/or Numerical Analysis (458 or 501). The prerequisites for these classes are not much beyond elementary calculus and maybe some linear algebra.


Powered by PmWiki