Homework Assignments

• Homework 1 (Socket open [Aug 26, 2008]))(Closed 9th sep; Due in class 23rd September)

  • Question 0 Think of a world that never was and ask why not

  • Question 1 (Matrices, vectors and eigen values refresher).

  • Question 2 (Precision/recall).

  • Question 3 Vector space ranking, relevance feedback.
    • Solutions to qn 1
    • Solutions to qn 2 and 3

• Homework 2 (Socket open [Sep 12, 2008])(Socket closed [Oct 2, 2008]) (Due [Oct 9, 2008])

  • Question 1 Association clusters.

  • Question 2 Bush/Saddam and LSI.

  • Question 3 LSI (with you having to compute SVD)

  • Question 4 Effect if tf/idf on LSI

  • Question 5: Graphically illustrate, with linked lists, the inverted index you will create for the following documents:
    1. Doc 1: "Bonfire of vanities"
    2. Doc 2: "a raging bonfire"
    3. Doc 3: "stop the rage"

  • Question 6: Consider the strings "Kambhampati" and "Kambhapatti". (a) What is the Levenstein distance betweent he strings? Give the edit operations that you used in computing this distance. (b) What is the Jaccard similarity between these strings based on 3-gram distance (assume that you generate 3-grams by taking three consecutive letters at a time, and shifting by one letter each time. also assume that ^ is the special character fro beginning space and $ is the special character for ending space).

  • Question 7 Social Networks
    • Solutions
    • Solutions to 5 and 6

• Homework 3 (Socket open & closed [Nov 6, 2008] ) (due [Nov 13, 2008])

  • Question 1 A/H and Pagerank computation.

  • Question 2. K-means on documents

    The question asks you to use bag similarity (also called Jaccard
    Similarity) instead of vector similarity. The similarity measure is
    defined in terms of the ratio of  the cardinality of intersection and
    union of a bag.  The thing to note here is that the intersection of two bags
    (containing multiple instances of iterms, say e1 and e2) is
    a bag that contains as many e1 as the minimum of e1 in both bags and
    as many e2 as minimum of e2 in both bags.
    
    So B1= 2 e1, 5e2
    B2= 4 e1, 2 e2
    
    B1 .intersection B2 = 2 e1, 2 e2
    
    B1 .union. B2 = 4 e1, 5 e2
    
    Cardinality of a bag is of course the number of items in that bag.
    

  • Question 3: Do hierarchical agglomerative clustering on the data in question 2 (use single link measure for inter-cluster distance)

  • Question 4: Text classification using NBC classifier.

  • Question 5: Collaborative Filtering

    • Solutions

• Homework 4 (*Changed due date* [Dec 9, 2008])

  • Question 1. Trying Xquery queries.

  • Question 2: (Semantic Web) The URL http://139.91.183.30:9090/RDF/VRP/Examples/demo/rdf_graph.gif shows an RDF and RDF-schema specification of a "museum domain" (You can also run queries on this demo at http://139.91.183.30:3026/RQLdemo/ ) Answer the following questions with respect to the RDF/RDF-SChema fragment:
    • Write down some of the RDF triples relating the URIs &r12, &r13 and &r14 in form.
    • What class does &r12 belong to according to the example?
    • What is the RDF-schema saying regarding how &r12's class and its relation to other classes/sub-classes?
    • Does the RDF schema have any class-subclass relations among non-unary predicates? (a non-unary predicate is a predicate of more than one argument).
    • Give an example of a query that you can answer because of the presence of RDF-Schema as background knowledge.
    • Explain, briefly, in the context of this example, how RDF-Schema is different from XML-Schema.

  • Question 3. Qn data integration models. **Skip the part on bucket algorithm**

  • Question 4: Qns on query processing in data integration

  • Question 5: [Answer to this question should also be posted on the class blog]. List upto five non-trivial ideas you were able to appreciate during the course of this semester. (These cannot be "I thought pagerank was kewl" variety).