Homeworks

HW# 1: For the below schema:

student (studentid,name,dob)
course (courseid,name,description,departmentid,credits)
department(departmentid,name,room)
faculty (facultyid,name,dob)
registration(studentid,sectionid,semesterid,grade)
semester(semesterid,name)
section(sectionid,courseid,facultyid,time)

Find faculty members with below average grades.

HW# 2 (this is more of a `project #1'; lets see whether anyone finishes this by next week): Load the ``Stock Ordrs'' data (ie: stockdata.zip) file into a database of your choice. Oracle recommended. There are two files in the data, "ordr", and "cxl", which represent stock orders and stock order cancelations. The column details for these are in the file. The file also has an `explanation.txt' file; which has a short example of how to pick out trades/quotes from the data.

Using select SQL query (no PL/SQL or T-SQL), create a trades table that represents trades between incoming orders. If the orders really came in at the times they came in, what would be the trading activity?

Obviously you'd do: create table trades as select ... from ...etc. and something similar for quotes.

Trade table columns: tdate symbol tim seq tid oid price qty, where tid is a unique trade id, oid is order id, seq is the sequence of the incoming order that's causing the trade, price is the price at which the trade took place (price of quote, usually), qty is the traded quantity for oid.

Similarly, create a quotes table, that represents a bid, bifqty, ofr, ofrqty (ie: bid and offer) at any given time (after a trade, or order arrival/cancelation).

Feel free to use analytical functions. Google for "oracle analytical functions".

I have an idea of how to attack this problem---so there's a chance it is possible to do using SQL.

If for some reason you are unable to do this homework, write a 2 page paper explaining exactly what difficulty is preventing you from doing it. The explanation must clearly explain the problem in first paragraph (so we can maybe resolve it), and why none of the common SQL solutions resolve it. Email me if you're planning this route, maybe I can provide some hints.

Submit the SQL queries, and the first 1000 records for trades and quotes tables (note that you can compare the results, everyone's output should be exactly the same).

For the few adventurous students, you can modify the gendata.pl file (in stockdata.zip), to increase volume (set it to ~1000000; and set number of symbols to ~3000). That will generate relatively realistic data sizes---run your query on that data set.

HW# 3: Write a stored procedure, in PL/SQL or T-SQL, that accepts an argument N, and populates table N with the first N prime numbers. Prime numbers are integers that are 2 or greater, divisible only by themselves and 1. The N table schema is: create table N (N int).

Test your algorithm on numbers going upto 1000000 (anyone can write a stupid prime number check---try to write an efficient one).

HW# 4: In any language of your choice, write a B-Tree implementation (or B+Tree). Your code will need to create and store data in a file. Your code should be command line based, with a command to insert an entry into the tree, and another command to look it up. Also support range lookup.

HW# 5: In any language of your choice, build a web application with authentication and authorization. Users need to be able to login, and your application needs to determine whether users are allowed or not allowed to do things. You should have some notion of `groups'. Note that the pages don't have to be pretty; the funtionality is what counts. If you've never written a web application... well, now is your chance to learn.

HW# 6: You have a representation of a 3D world in a database, with a billion or more objects. For every object you have:
thing(thingid, name, x,y,z, radius)
Write a SQL query to find all intersecting objects. Assuming that objects can't intersect with everything at the same time, setup your query such that finding intersections doesn't take O(N^2) time. Things you can assume: you have access to 100000 servers (you need to pick the distribution method to use).

HW# 7: Using Apache Hadoop (hadoop.apache.org) MapReduce, implement HW# 6 (you can run it on 1 computer---the point is that everyone gets to play with MapReduce).