CS267 Spring 2022Practice Final

To study for the final I would suggest you:

1. Know how to do (by heart) all the practice problems.
2. Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
3. Go over the homework problems.
4. Try to create your own problems similar to the ones I have given and solve them.
5. Skim the relevant sections from the book.
6. If you want to study in groups, at this point you are ready to quiz each other.

Here are some facts about the actual final:

1. It is comprehensive.
2. It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test.
3. You should bring photo ID.
4. There will be more than one version of the test. Each version will be of comparable difficulty.
5. It is 10 problems (3pts each), 6 problems will be on materials since the second midterm, 4 problems will be from the topics of the midterm.
6. Two problems will be exactly (less typos) off of the practice final, and one will be off of the practice midterm.

The practice final is below:

1. Prove there is an upper bound that a single term's BM25 score for a single document can contributed to the overall BM25 score for that document with respect to a query.
2. Give the context in which one might use accumulator pruning for ranking. Then explain and give an example of how the accumulator pruning algorithm from class works.
3. Express the following as region algebra queries: (a) Your first name within 8 terms of your last name. (b) Your zip code in a
   tags before the phrase "doxing is fun".
4. Give a concrete example involving your name of how a Canonical Huffman code might be written as a preamble to encoding a string.
5. Briefly describe how each of the following coding schemes for compression lists work: (a) `gamma`-code, (b) LLRUN, (c) Rice code.
6. Give a situation with numbers where it would make sense to rebuild an index rather than remerge.
7. Suppose there is a 1,000,000 word corpus. Document `d` is 450 words long. The terms blue and suede occur 800, 100 times respectively. In document `d` blue occurs twice and suede once. Let `mu=1000`. What is the LMD score for d for the query "blue suede"?
8. Distinguish intra-query and inter-query parallelism as far as information retrieval goes. What bottlenecks exists to intra-query parallelism if partition-by-document is used.
9. Explain how hub and authority scores are calculated in SALSA.
10. Briefly define aggregate P@k and aggregate AP and explain why they might be used.