CS257 Fall 2020Practice Final

For the final I would suggest you:

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

The practice final is below. Here are some facts about the actual final:

1. It is open book, open notes, open internet, however, you are not allowed to discuss problems on the final with classmates or other people until after the final submission period is over.
2. The final will have 10 problems.
3. It will be posted as one of the links on the side of the class homepage.
4. You submit the final for grading using the same mechanism as to submit homeworks.
5. It is designed to take an 2h15m, however, it will be posted by 12:15pm on Dec 15 and you can submit it up until Dec 16 at 11:59pm.
6. Some problems will be dependent on some personal information about you such as your ID, and you will not receive credit if you don't make use of this information correctly.
7. One problem will be off the practice midterm and two problems will be off the practice final.
8. Six problems will be on material after the midterm, four will be one material before.

On practice final day, please post your problem solutions to the Practice Final Thread. Make sure to include the names of all your group's members.

1. Define each of the following record formats and give an example for each making use of your name: (a) relative location, (b) embedded identification, (c) pointers and lists.
2. Suppose R had 2,000,000 tuples and 8 fit into a block of (last digit of your id +1)*1024 bytes. (a) How many blocks and bytes does R take to store? (b) If the key is 16 bytes long and the record pointer 8 bytes long, approximately how many index records can fit in a block? (c) If we have a sparse index on R, how many blocks and bytes would the index file take?
3. Define and give an example of the following terms: (a) inverted file, (b) `Delta`-list, (c) Gap-compression.
4. Give an example situations framed in terms of a databases where: (a) you would use a bitmap index over a Bloom filter (b) you would use a Bloom Filter over a Bitmap index.
5. Show step-by-step (with intermediate drawings) what would happen if you inserted 14 + the fifth digit of your student ID into the following B-tree:
6. Give a two pass algorithm for duplicate elimination using disk-based sorting. Give an example. Estimate the total number of block I/Os for this operation.
7. Define the following concepts: (a) log structured merge tree, (b) stable storage, (c) RAID 4.
8. Give an example query which makes use of the cube operator and one that makes use of the rollup operator and explain what each would do.
9. Write down the urls of five web sites, some of which have links to each other. Describe the OPIC algorithm, use the five urls as seed sites to give a concrete example of how OPIC would crawl from these sites.
10. Briefly explain the following concepts: (a) Total Data Quality Management (b) the 5 V's of Big Data, (c) Resilient Distributed Dataset.