Interesting Information: Back Home Schedule Assignments Class Syllabus

Assignment Number 2 The second assignment is available online here in postscript form. Programming Assignment Programming Assignment News! Due date postponed!!! The original due date for the programming assignment was Friday, Feb. 21, at 23:59:59.999. There is the possibility to turn in the assignment late without penalty. The new due data hasn't been decided yet, and will be announced officially tuesday on class. It will be sometimes next week. Main file available Template main programs for the assignment will be available during this weekend in the directory public/template under the class umbrella. There will be two programs: build.cxx reads the records from the file data22 and asks your Index class to insert them in an index with a specified name. search.cxx takes the name of an index and a key and searches the key in the index. If you follow the specifications given in the handout, these main programs should compile and run with your class flawlessly. You can decide to use them or not. It is finally here! You have been waiting for this moment so long that now that it is here you almost can't believe it. The excitement and expectation are palpable, electricity is in the air. The Programming Assignment is out! Here you have a postscript version of the assignment handout. I will post an html version as soon as my lazy ancestry will allow me to. The assignment is due February 21 And also for you... The advice Corner The group-making billboard The advice corner If you have a problem with the assignment, come to see me or write me an email. If I think that the problem you have might be of interest to other people, I will post a brief description of the problem and of my advice here. So, keep an eye on this page... Q: How do I organize the primary and secondary pages into files? A: There is no golden rule here, neither is there a single way to do it. The way I did it is to have the primary pages in a file and the secondary pages in another. The reason for doing this is that the primary pages are pretty easy to manage, since they are never erased. So, the file with the primary pages will only grow. You can have a header (which can be loaded and saves to/from memory as a structure) and then the pages (which can also be other structures). If the header contains h bytes, and each page contains p bytes, then the i-th pages starts at byte h + pi. The secondary pages, on the other hand, can be created and deleted. You need some kind of linked structure for them. Each primary page can contain the location (in the secondary pages file) of the first page of its overflow chain (or aero if it has no overflow chain), and then every secondary page can contain a pointer to the next page in the chain. Since secondary pages can be erased, but it is impractical to physically erase them from disk, you might want to keep a list of free pages, with a pointer to the first page of the list in the header of the secondary pages file. Whenever you need a new secondary page, you will check in the list if there is any available and, if there is some, use one of those instead of allocating a new one at the end of the file. Q: How should my main programs work? A: I am going to prepare two model main programs that should be compatible with the Index class required by the assignment and post them in the public/template directory. Anyway, the search program should take as arguments the name of the index and a key and search the key in the index. If the key is found, the program should retrieve the pointer from the index, open the file data22, and read the record at the position specified by the address. This record should contain the same key as the key searched. For instance, if your index is called MyIndex, typical calls could be: % search MyIndex FOO Found FOO --> Pos(12563), FOO %search MyIndex BAR BAR Not found Have a look at the main program as soon as i post it. Q: What size should I use for the primary and secondary pages? Is 10 elements in the primary pages and 5 in the secondary OK? A: 10 items in the primary page and 5 in the overflow is very little. I suggest to parametrize the whole thing with a couple of "#define". Small values (like the one you mention, and smaller) are very useful for debugging (you create a lot of pages with few elements, and you can easily print them to understand what's going on), but for the final version you might want to use much larger number (I'd say that a page should be at least 512 bytes) Q: Where do I find information about the C I/O functions? I tried looking at the handout, but I am still confused. A: use the UNIX "man" command. For instance, % man fseek will tell you everything you might want to know about the fseek function: what it does, how to use it, what parameters to use, etc. People who need people For this programming assignment you are allowed to work in group of two people if you prefer so. If you would like to join forces with somebody but you don't know with whom, write me a message (ssantini@cs.ucsd.edu) and I will post here your name and your email address. Adam Lassy alassy@ieng9.ucsd.edu Midterm Topics In a few words: the midterm will cover everything up to RAID (but not including RAID. That is: B trees and B+ trees. What are they, and why would you want to use them. R trees. What kind of data do you address with R trees? Are data at the leaves only or at the nodes? How an internal node is organized. Search algorithm (you should be able to do a manual search on a simple tree following the algorithm). Generalities of the insertion algorithm (in particular, what kind of split-node algorithms are proposed in the paper, and what are their characteristics) Linear Hashing. Why do we need linear hashing (as opposed to regular hashing methods). Primary pages and secondary pages. What are they? Insertion and split. The meaning of the various parameters: N, level, next, alpha... Be sure you know how to insert data in a linear hashing table (there are some problems in the practice questions, but you can create your own) The way in which the systems of contrapposed alliances in the early XX century Europe, fostered by accidental circumstances, led to the first world war. (OK, you don't really need to know this.... :) IBIM indexing. Why do you need it, as opposed to linear hashing? What are the region numbers and the bucket numbers, and how are the two related? Know how to insert and retrieve things. Practice Questions Practice Questions for the Midterm Here are the practice questions for the midterm. We have a postscript version that you can print, and an html version that you can have a look at Practice Answers: for these questions there is an answer sheet available. Postscript only.... sorry! These practice questions are mainly on R-trees. Here are more questions for you, this time on linear hashing and IBIM. These also are available in postscript form and html form. Have fun! (what I mean is not: have fun working on your pracice questions. I mean: don't just work on the practice questions, have some fun too. But I certainly don't need to tell you that... :)

Web page designed by Simone Santini, (ssantini@cs.ucsd.edu)