Homework Assignments

Homework 0 (Not graded)
- Question 1 (Matrices, vectors and eigen values refresher).
Homework 1 (Assigned [Sep 9, 2011]; Due [Sep 20, 2011]--in hard copy, in class)
1. Question 1 (Precision/recall).
2. Question 2 Vector space ranking, relevance feedback. [Multi-part Question]
3. 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"
4. 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).
5. Solutions
Homework 2 (Assigned starting [Sep 20, 2011])(Due 4th October)

Homework 3 (Assigned starting [Mar 7, 2013] Due: [March 28th, 2013]
Homework on Social Networks (for those who viewed the social network lectures). [Due by the last day of the class: 12/6--in class]
1. A question from an old mid-term on social networks
2. (a) Give a social network over 4 nodes that has (i) the maximum diameter (ii) the minimum diameter
  (b) Give a social network over N nodes where all nodes have the same centrality except one node which has significantly higher centrality. What is its diameter? Is there a node in this network which also has a much higher between-ness centrality than any other node?
  (c) Can you think of a use for between-ness centrality in web-applications?
3. The page http://academic.research.microsoft.com/CSDirectory/Author_category_5.htm ranks the top 5,000 most cited authors in Artificial Intelligence. Analyze the data to see if the "num cites = f(rank)" distrubtion follows a power law. If it is a power law, what is the approximate "power" (r in k^-r ) that the distribution follows? (You can use excel etc of course)
4. Solutions
Homework 3 part b
("Reading Comprehension") Read the paper "Anatomy of a large-scale hyper-textual search engine" which constains a description of Google search engine circa 1998 (i.e., before it became a company). Answer the following questions:
1. What are Fancy hits?
2. Why are there two types of barrels--the short and the long?
3. How is indexing parallelized?
4. How does Google show that it doesn't quite care about recall?
5. How does Google avoid crawling the same URL multiple times?
6. What are some of the memory saving things they do?
7. Do they use TF/IDF directly or indirectly?
8. Do they normalize the vectors? (why not?)
9. Can they support proximity queries?
10. How are "page synopses" made?
11. List some of the parameters that need to be initialized for their search engine. Are the default values they pick reasonable?

Homework 4 (assigned: [Apr 8, 2013]; Due: [Apr 18, 2013])

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 2: Do hierarchical agglomerative clustering on the data in question 1 (use single link measure for inter-cluster distance)
Question 3: Text classification using NBC classifier.
Question 4: Collaborative Filtering
Solutions

Subbarao Kambhampati

Last modified: Wed Dec 7 11:55:46 MST 2011