Posts Issued in August, 2014

In this assignment, you will be designing and implementing MapReduce algorithms for a variety of common data processing tasks. Problem 3: Consider a simple social network dataset consisting of key-value pairs where each key is a person and each value is a friend of that person. Describe a MapReduce algorithm to count he number of friends each person has.

Map Input

The input is a 2 element list: [personA, personB]

personA: Name of a person formatted as a string

personB: Name of one of personA’s friends formatted as a string

This implies that personB is a friend of personA, but it does not imply that personA is a friend of personB. Reduce Output

The output should be a (person, friend count) tuple.

person is a string and friend count is an integer describing the number of friends ‘person’ has.

You can test your solution to this problem using friends.json:

    python friend_count.py friends.json

You can verify your solution against friend_count.json.

import MapReduce
import sys
 
"""
Word Count Example in the Simple Python MapReduce Framework
"""
 
mr = MapReduce.MapReduce()
 
# =============================
# Do not modify above this line
def mapper(record):
    # key: document identifier
    # value: document contents
    person = record[0]
    mr.emit_intermediate(person,1)
 
def reducer(person, list_of_values):
    # key: word
    # value: list of occurrence counts
    mr.emit((person,len(list_of_values)) )
 
# Do not modify below this line
# =============================
if __name__ == '__main__':
  inputdata = open(sys.argv[1])
  mr.e xecute(inputdata, mapper, reducer)

Problem 2 Implement a relational join as a MapReduce query Consider the query:

S E LECT * FROM Orders, LineItem WHERE Order.order_id = LineItem.order_id

Your MapReduce query should produce the same information as this SQL query. You can consider the two input tables, Order and LineItem, as one big concatenated bag of records which gets fed into the map function record by record.

Map Input

The input will be database records formatted as lists of Strings.

Every list element corresponds to a different field in it’s corresponding record.

The first item(index 0) in each record is a string that identifies which table the record originates from. This field has two possible values:

    ‘line_item’ indicates that the record is a line item.

    ‘order’ indicates that the record is an order.

The second element(index 1) in each record is the order_id.

LineItem records have 17 elements including the identifier string.

Order records have 10 elements including the identifier string. Reduce Output

The output should be a joined record.

The result should be a single list of length 27 that contains the fields from the order record followed by the fields from the line item record. Each list element should be a string.

You can test your solution to this problem using records.json:

    python join.py records.json

You can verify your solution against join.json.

import MapReduce
import sys
 
"""
Word Count Example in the Simple Python MapReduce Framework
"""
 
mr = MapReduce.MapReduce()
 
# =============================
# Do not modify above this line
TABLE_1_NAME = 'order'
TABLE_2_NAME = 'line_item'
 
def mapper(record):
    # key: document identifier
    # value: document contents
#    key = record[0]
#    value = record[1]
#    words = value.split()
#    for w in words:
#      mr.emit_intermediate(w, key)
    table_name = record[0]
    order_id = record[1]
    table_fields = record[2:]
 
    mr.emit_intermediate(order_id,[table_name,table_fields] )
 
def reducer(key, list_of_values):
    # key: word
    # value: list of occurrence counts
#    result = []
#    total = 0
#    for v in list_of_values:
#      total += v
#    mr.emit((key, total))
#
#    for ID in list_of_values:
#        if ID not in result:
#            result.append(ID)
#    mr.emit( (key,result) )
    table1 = [table[1] for table in list_of_values if table[0] == TABLE_1_NAME ]
    table2 = [table[1] for table in list_of_values if table[0] == TABLE_2_NAME ]
 
    for record1 in table1:
        for record2 in table2:
            res = []
 
            res.append(TABLE_1_NAME)
            res.append(key)
            res.extend(record1)
            res.append(TABLE_2_NAME)
            res.append(key)
            res.extend(record2)
 
            mr.emit(res)
 
 
 
# Do not modify below this line
# =============================
if __name__ == '__main__':
  inputdata = o p e n(sys.argv[1])
  mr.e x e c u t e(inputdata, mapper, reducer)

In this assignment, you will be designing and implementing MapReduce algorithms for a variety of common data processing tasks.

Algorithms in MapReduce: Instructions Help

In this assignment, you will be designing and implementing MapReduce algorithms for a variety of common data processing tasks.

The MapReduce programming model (and a corresponding system) was proposed in a 2004 paper from a team at Google as a simpler abstraction for processing very large datasets in parallel. The goal of this assignment is to give you experience “thinking in MapReduce.” We will be using small datasets that you can inspect directly to determine the correctness of your results and to internalize how MapReduce works. In the next assignment, you will have the opportunity to use a MapReduce-based system to process the very large datasets for which is was designed.

As always, the first thing to do is to update your provided course materials using git pull. These resources may have changed since the last time you interacted with the datasci_course_materials repository. Github Instructions.

Next, review the lectures to make sure you understand the programming model.

You may also want to experiment running your queries on the JSMapReduce service for this assignment to see what it would be like to run a MapReduce query on a cluster of machines.

Python MapReduce Framework

You will be provided with a python library called MapReduce.py that implements the MapReduce programming model. The framework faithfully implements the MapReduce programming model, but it executes entirely on a single machine -- it does not involve parallel computation.

Here is the word count example discussed in class implemented as a MapReduce program using the framework:

# Part 1
mr = MapReduce.MapReduce()
 
# Part 2
def mapper(record):
    # key: document identifier
    # value: document contents
    key = record[0]
    value = record[1]
    words = value.split()
    for w in words:
      mr.emit_intermediate(w, 1)
 
# Part 3
def reducer(key, list_of_values):
    # key: word
    # value: list of occurrence counts
    total = 0
    for v in list_of_values:
      total += v
    mr.emit((key, total))
 
# Part 4
inputdata = o p e n (sys.argv[1])
mr.e x e c u t e (inputdata, mapper, reducer)

In Part 1, we create a MapReduce object that is used to pass data between the map function and the reduce function; you won’t need to use this object directly.

In Part 2, the mapper function tokenizes each document and emits a key-value pair. The key is a word formatted as a string and the value is the integer 1 to indicate an occurrence of word.

In Part 3, the reducer function sums up the list of occurrence counts and emits a count for word. Since the mapper function emits the integer 1 for each word, each element in the list_of_values is the integer 1.

The list of occurrence counts is summed and a (word, total) tuple is emitted where word is a string and total is an integer.

In Part 4, the code loads the json file and executes the MapReduce query which prints the result to stdout.

Create an Inverted index. Given a set of documents, an inverted index is a dictionary
where each word is associated with a list of the document identifiers in which that word appears.
''''
import MapReduce
import sys
 
mr = MapReduce.MapReduce()
 
 
def mapper(record):
    ''''
The input is a 2 element list: [document_id, text]
document_id: document identifier formatted as a string
text: text of the document formatted as a string
''''
    key = record[0]
    value = record[1]
 
    for word in value.split():
       mr.emit_intermediate(word,key)
 
def reducer(key, list_of_values):
    ''''
The output should be a (word, document ID list) tuple where word is a String and document ID list is a list of Strings.
''''
    result = []
 
    #want to remove duplicates
    #might use set(), but got some bug which did not want to solve
    for document_ID in list_of_values:
        if document_ID not in result:
            result.append(document_ID)
    mr.emit( (key,result) )
 
 
inputdata = o p e n(sys.argv[1])
mr.e x e c u t e(inputdata, mapper, reducer)

Series of programming assignments from "Introduction to Data Science" course - Join the data revolution by University of Washington

Problem 6: Top ten hash tags

Write a Python script, top_ten.py, that computes the ten most frequently occurring hash tags from the data you gathered in Problem 1.

top_ten.py should take a file of tweets as an input and be usable in the following way: $ python top_ten.py Assume the tweet file contains data formatted the same way as the livestream data.

In the tweet file, each line is a Tweet object, as described in the twitter documentation. You should not be parsing the “text” field.

Your script should print to stdout each hashtag-count pair, one per line, in the following format:

      <hashtag:string> <count:float>



For example, if you have the pair (baz, 30) it should appear in the output as:

      baz 30.0



Remember your output must contain floats, not ints.

import sys
import json
 
 
def test (tf):
    tweets = []
    decodedText=[]
    for x in tf.readlines():
        y= json.loads(x)
            #uncoded.append(y["text
        if y.has_key("entities") and y["entities"]["hashtags"] != []:
            for x in  y["entities"]["hashtags"]:
                if x["text"].isalnum():
                    tweets.append((x["text"]))
    newTweets ={}
    for i in tweets:
        if i in newTweets:
            newTweets[i] += 1
        else:
            newTweets[i] = 1
    topTen = []
    for w in sorted(newTweets, key=newTweets.get, reverse=True):
        topTen.append((w, newTweets[w]))
    topTen = topTen[0:10]
    for (x,y) in topTen:
        print x + " " + str(y)
    #for x in uncoded:
    #
    #    decodedText.append((x.encode("utf-8")))
    #    
    #return decodedText
def sfDict(sf):
    #x = {}
    #for s in sf.readlines():
    #    y= s.split()
    #    x["pair"] = {
    #        "word" : y[0],
    #        "val" : y[1]
    #    }
    x = []
    for s in sf.readlines():
            y = s .split("\t")
            x.append((y[0], y[1]))
    return x
def check(decodedText):
    states={}
    for (tweet, st) in decodedText:
        val= 0.0
        for (x,y) in op:
            if ((x + " " )  or (" " + x)) in tweet:
                val= val + float(y)
                if st in states:
                    states[st] += val
                else:
                    states[st] = val
    x= 0.0
    finalState = ""
    for key, value in states.iteritems():
        if value > x:
            finalState = key
            x= value
    print finalState
 
def main():
 
    tweet_file = open(sys.argv[1])
    test(tweet_file)
 
if __name__ == '__main__':
    main()

Series of programming assignments from "Introduction to Data Science" course - Join the data revolution by University of Washington

Problem 5: Which State is happiest?

Write a Python script, happiest_state.py, that returns the name of the happiest state as a string.

happiest_state.py should take a file of tweets as an input and be usable in the following way:

      $ python happiest_state.py <sentiment_file> <tweet_file>



The file AFINN-111.txt contains a list of pre-computed sentiment score.

Assume the tweet file contains data formatted the same way as the livestream data.

We recommend that you build on your solution to Problem 2.

There are three different objects within the tweet that you can use to determine it’s origin.

1 The coordinates object

2 The place object

3 The user object

You are free to develop your own strategy for determining the state that each tweet originates from.

Limit the tweets you analyze to those in the United States.

The live stream has a slightly different format from the response to the query you used in Problem 0. In this file, each line is a Tweet object, as described in the twitter documentation.

Note: Not every tweet dictionary will have a text key -- real data is dirty. Be prepared to debug, and feel free to throw out tweets that your code can't handle to get something working. For example, non-English tweets.

import sys
import json
 
 
def test (sf, tf):
    uncoded = []
    decodedText=[]
    for x in tf.readlines():
        y= json.loads(x)
        if y.has_key("place"):
            #uncoded.append(y["text
            if y["place"] != None and y["place"]["country"] == "United States" and y["place"]["country_code"] == "US":
                #decodedText.append((y["text"].encode("utf-8")), ((y["place"]["full_name"]).split(",")[1]))
               state= (y["place"]["full_name"]).split(",")[1]
               text = y["text"].encode("utf-8")
               decodedText.append((text,state))
 
    return decodedText
    #for x in uncoded:
    #
    #    decodedText.append((x.encode("utf-8")))
    #    
    #return decodedText
def sfDict(sf):
    #x = {}
    #for s in sf.readlines():
    #    y= s.split()
    #    x["pair"] = {
    #        "word" : y[0],
    #        "val" : y[1]
    #    }
    x = []
    for s in sf.readlines():
            y = s .split("\t")
            x.append((y[0], y[1]))
    return x
def check(decodedText, op):
    states={}
    for (tweet, st) in decodedText:
        val= 0.0
        for (x,y) in op:
            if ((x + " " )  or (" " + x)) in tweet:
                val= val + float(y)
                if st in states:
                    states[st] += val
                else:
                    states[st] = val
    x= 0.0
    finalState = ""
    for key, value in states.iteritems():
        if value > x:
            finalState = key
            x= value
    print finalState
 
def main():
    sent_file = open(sys.argv[1])
    tweet_file = open(sys.argv[2])
    x =test(sent_file, tweet_file)
    y= sfDict(sent_file)
    check (x,y)
 
if __name__ == '__main__':
    main()

Series of programming assignments from "Introduction to Data Science" course - Join the data revolution by University of Washington

Problem 4: Compute Term Frequency

Write a Python script, frequency.py, to compute the term frequency histogram of the livestream data you harvested from Problem 1. The frequency of a term can be calculate with the following formula: [# of occurrences of the term in all tweets]/[# of occurrences of all terms in all tweets]

frequency.py should take a file of tweets as an input and be usable in the following way:

      $ python frequency.py <tweet_file>



Assume the tweet file contains data formatted the same way as the livestream data.

Your script should print to stdout each term-frequency pair, one pair per line, in the following format:

      <term:string> <frequency:float>



For example, if you have the pair (bar, 0.1245) it should appear in the output as:

      bar 0.1245



Frequency measurements may take phrases into account, but this is not required. We only ask that you compute frequencies for individual tokens.

Depending on your method of parsing, you may end up with frequencies for hashtags, links, stop words, phrases, etc. Some noise is acceptable for the sake of keeping parsing simple.

import sys
import json
 
 
def test (tf):
    uncoded = []
    decodedText=[]
    for x in tf.readlines():
        y= json.loads(x)
        if y.has_key("text"):
            uncoded.append(y["text"])
 
    for x in uncoded:
 
        decodedText.append((x.encode("utf-8")))
 
    return decodedText
 
def calc (decodedText):
    totalWords = 0.0
    words = {}
    for x in decodedText:
 
        for word in x.split():
            totalWords += 1
            if word in words:
                x = (words)[word] + 1.0
                words[word] = x
            elif word.isalnum() or "," in word:
                words[word] = 1.0
 
    for x in range(len(words)):
        print words.keys()[x] + " " + str(words.values()[x] / totalWords)
def main():
    sent_file = open(sys.argv[1])
    x= test(sent_file)
    calc(x)
if __name__ == '__main__':
    main()

Series of programming assignments from "Introduction to Data Science" course - Join the data revolution by University of Washington

Problem 3: Derive the sentiment of new terms In this part you will be creating a script that computes the sentiment for the terms that do not appear in the file AFINN-111.txt.

Here's how you might think about the problem: We know we can use certain words to deduce the sentiment of a tweet. Once you know the sentiment of the tweets that contain some term, you can assign a sentiment to the term itself.

Don't feel obligated to use it, but the following paper may be helpful for developing a sentiment metric. Look at the Opinion Estimation subsection of the Text Analysis section in particular. O'Connor, B., Balasubramanyan, R., Routedge, B., & Smith, N. From Tweets to Polls: Linking Text Sentiment to Public Opinion Time Series. (ICWSM), May 2010.

You are provided with a skeleton file, term_sentiment.py, which can be executed using the following command: $ python term_sentiment.py Your script should print to stdout each term-sentiment pair, one pair per line, in the following format:

For example, if you have the pair (“foo”, 103.256) it should appear in the output as: foo 103.256 The order of your output does not matter.

import sys
import json
def hw():
    print 'Hello, world!'
 
def lines(fp):
    print str(len(fp.readlines()))
 
def test (sf, tf):
    uncoded = []
    decodedText=[]
    for x in tf.readlines():
        y= json.loads(x)
        if y.has_key("text"):
            uncoded.append(y["text"])
 
    for x in uncoded:
 
        decodedText.append((x.encode("utf-8")))
 
    return decodedText
def sfDict(sf):
    #x = {}
    #for s in sf.readlines():
    #    y= s.split()
    #    x["pair"] = {
    #        "word" : y[0],
    #        "val" : y[1]
    #    }
    x = []
    for s in sf.readlines():
            y = s .split("\t")
            x.append((y[0], y[1]))
    return x
 
def check(decodedText, op):
    for z in decodedText:
        val= 0.0
        for (x,y) in op:
            if ((x + " " )  or (" " + x)) in z:
                val= val + float(y)
        #print z + "  : " + str(val)
        return (z, val)
 
def check2(decodedText, op):
    for z in decodedText:
        val = 0.0
        for word in z.split():
            w = []
            for (x,y) in op:
                if word not in x:
                    w.append(word)
                elif word in x:
                    val = val + float(y)
            print word + " " + str(val)
 
def main():
    sent_file = open(sys.argv[1])
    tweet_file = open(sys.argv[2])
    x =test(sent_file, tweet_file)
    y= sfDict(sent_file)
    check(x,y)
    check2 (x,y)
 
if __name__ == '__main__':
    main()

Series of programming assignments from "Introduction to Data Science" course - Join the data revolution by University of Washington

  • Problem 0: Query Twitter with Python
  • Problem 1: Get Twitter Data
  • Problem 2: Derive the sentiment of EACH tweet

Problem 0: Query Twitter with Python To retrieve recent tweets associated with the term “microsoft,” you use this url:

http://search.twitter.com/search.json?q=microsoft

To access this url in Python and parse the response, you can use the following snippet:

import urllib import json

response = urllib.urlopen("http://search.twitter.com/search.json?q=microsoft") print json.load(response)

The format of the result is JSON, which stands for JavaScript Object Notation. It is a simple format for representing nested structures of data --- lists of lists of dictionaries of lists of .... you get the idea. As you might imagine, it is fairly straightforward to convert JSON data into a Python data structure. Indeed, there is a convenient library to do so, called json, which we will use.

Twitter provides only partial documentation for understanding this data format, but it's not difficult to deduce the structure.

Using this library, the json data is parsed and converted to a Python dictionary representing the entire result set. (If needed, take a moment to read the documentation for Python dictionaries). The "results" key of this dictionary corresponds holds the actual tweets; each tweet is itself another dictionary.

a) Write a program, print.py, to print out the text of each tweet in the result.

b) Generalize your program, print.py, to fetch and print 10 pages of results. Note that you can return a different page of results by passing an additional argument in the url:

http://search.twitter.com/search.json?q=microsoft&page=2

print.py should be executable in the following way:

      $ python print.py



When executed, the script should print each tweet on an individual line to stdout. What to turn in: Nothing. This is a warmup exercise.

Problem 1: Get Twitter Data

To access the live stream, you will need to install the oauth2 library so you can properly authenticate.

This library is already installed on the class virtual machine. Or you can install it yourself in your Python environment.

The steps below will help you set up your twitter account to be able to access the live 1% stream.

● Create a twitter account if you do not already have one.

● Go to https://dev.twitter.com/apps and log in with your twitter credentials.

● Click "create an application"

● Fill out the form and agree to the terms. Put in a dummy website if you don't have one you want to use.

● On the next page, scroll down and click "Create my access token"

● Copy your "Consumer key" and your "Consumer secret" into twitterstream.py

● Click "Create my access token." You can Read more about Oauth authorization.

● Open twitterstream.py and set the variables corresponding to the consumer key, consumer secret, access token, and access secret.

access_token_key = ""

access_token_secret = ""

consumer_key = ""

consumer_secret = ""

● Run the following and make sure you see data flowing and that no errors occur. Stop the program with Ctrl-C once you are satisfied. $ python twitterstream.py

You can pipe the output to a file, wait a few minutes, then terminate the program to generate a sample. Use the following command:

$ python twitterstream.py > output.txt

Let this script run for a minimum of 10 minutes. Keep the file output.txt for the duration of the assignment, we will be reusing it in later problems.

Don’t use someone else’s file; we will check for uniqueness in other parts of the assignment. What to turn in: The first 20 lines of your file. You can get the first 20 lines by using the following command:

$ head -n 20 output.txt

Problem 2: Derive the sentiment of each tweet

For this part, you will compute the sentiment of each tweet based on the sentiment scores of the terms in the tweet. The sentiment of a tweet is equivalent to the sum of the sentiment scores for each term in the tweet. You are provided with a skeleton file, tweet_sentiment.py, which can be executed using the following command: $ python tweet_sentiment.py The file AFINN-111.txt contains a list of pre-computed sentiment scores. Each line in the file contains a word or phrase followed by a sentiment score. Each word or phrase found in a tweet, but not in AFINN-111.txt should be given a sentiment score of 0. See the file AFINN-README.txt for more information. To use the data in the AFINN-111.txt file, you may find it useful to build a dictionary. Note that the AFINN-111.txt file format is tab-delimited, meaning that the term and the score are separated by a tab character. A tab character can be identified a "\t".The following snippet may be useful: afinnfile = open("AFINN-111.txt") scores = {} # initialize an empty dictionary for line in afinnfile: term, score = line.split("\t") # The file is tab-delimited. "\t" means "tab character" scores[term] = int(score) # Convert the score to an integer.

print scores.items() # Print every (term, score) pair in the dictionary

Assume the tweet file contains data formatted the same way as the livestream data.

Your script should print to stdout the sentiment of each tweet in the file, one sentiment per line:

      <sentiment:float>



NOTE: You must provide a score for every tweet in the sample file, even if that score is zero. However the sample file will only include English tweets

The first sentiment corresponds to the first tweet in the input file, the second sentiment corresponds to the second tweet in the input file, and so on.

Hints: The json.loads function parses a string to JSON.

Refer to the twitter documentation in order to determine what field to parse.

import sys
import json
def hw():
    print 'Hello, world!'
 
def lines(fp):
    print str(len(fp.readlines()))
 
def test (sf, tf):
    uncoded = []
    decodedText=[]
    for x in tf.readlines():
        y= json.loads(x)
        if y.has_key("text"):
            uncoded.append(y["text"])
 
    for x in uncoded:
 
        decodedText.append((x.encode("utf-8")))
 
    return decodedText
def sfDict(sf):
    #x = {}
    #for s in sf.readlines():
    #    y= s.split()
    #    x["pair"] = {
    #        "word" : y[0],
    #        "val" : y[1]
    #    }
    x = []
    for s in sf.readlines():
            y = s .split("\t")
            x.append((y[0], y[1]))
    return x
def check(decodedText, op):
    for z in decodedText:
        val= 0.0
        for (x,y) in op:
            if ((x + " " )  or (" " + x)) in z:
                val= val + float(y)
        print z + "  : " + str(val)
 
def main():
    sent_file = open(sys.argv[1])
    tweet_file = open(sys.argv[2])
    x =test(sent_file, tweet_file)
    y= sfDict(sent_file)
    check (x,y)
 
if __name__ == '__main__':
    main()

week 6 covered topics:

  • HASHING: THE BASICS
  • UNIVERSAL HASHING
  • BLOOM FILTERS

Two programming assignments:

  • The goal is to implement a variant of the 2-SUM algorithm (covered in the Week 6 lecture on hash table applications)
  • The goal is to implement the "Median Maintenance" algorithm (covered in the Week 5 lecture on heap applications).

The goal of this problem is to implement a variant of the 2-SUM algorithm (covered in the Week 6 lecture on hash table applications).

The file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.

Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t. (NOTE: ensuring distinctness requires a one-line addition to the algorithm from lecture.)

Write your numeric answer (an integer between 0 and 20001) in the space provided.

OPTIONAL CHALLENGE: If this problem is too easy for you, try implementing your own hash table for it. For example, you could compare performance under the chaining and open addressing approaches to resolving collisions. Implementation 1

import sys
filename = "algo6_2sum.txt"
numbers = [int(l) for l in open(filename)]
targets = range(-10000,10001)
H = {}
answers = {}
 
for i in numbers:
  H[i] = True
 
for i in numbers:
  for t in targets:
    if t - i in H:
      if i == t - i:
        continue
      if t not in answers:
        answers[t] = set([tuple(sorted([i, t - i]))])
      else:
        answers[t].add(tuple(sorted([i, t - i])))
 
print len(answers)

Implementation 2

hash = {}
    count = 0
    input_file = open('HashInt.txt')
    for line in input_file:
            num = int(line.rstrip('\n'))
            hash[num] = 1
    input_file.close()
 
    def target_sum (t):
            for element in hash:
                    t_el = t-element
                    if t_el in hash and t_el != element:
                            return 1
            return 0
 
    for i in range(2500,4001):
            if target_sum(i):
                    count += 1
    print count

Question 2 Download the text file here.

The goal of this problem is to implement the "Median Maintenance" algorithm (covered in the Week 5 lecture on heap applications). The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,…,xk. (So, if k is odd, then mk is ((k+1)/2)th smallest number among x1,…,xk; if k is even, then mk is the (k/2)th smallest number among x1,…,xk.)

In the box below you should type the sum of these 10000 medians, modulo 10000 (i.e., only the last 4 digits). That is, you should compute (m1+m2+m3+⋯+m10000)mod10000.

OPTIONAL EXERCISE: Compare the performance achieved by heap-based and search-tree-based implementations of the algorithm.

Implementation 1

import heapq
import sys
filename = "algo6_median.txt"
X = [int(l) for l in open(filename)]
H_low = []
H_high = []
 
sum = 0
for x_i in X:
  if len(H_low) > 0:
    if x_i > -H_low[0]:
      heapq.heappush(H_high, x_i)
    else:
      heapq.heappush(H_low, -x_i)
  else:
    heapq.heappush(H_low, -x_i)
 
  if len(H_low) > len(H_high) + 1:
    heapq.heappush(H_high, -(heapq.heappop(H_low)))
  elif len(H_high) > len(H_low):
    heapq.heappush(H_low, -(heapq.heappop(H_high)))
 
  sum += -H_low[0]
 
print sum % 10000

Implementation 2

def read_file(filename):
        l_input = []
        myfile = open(filename)
        print 'file open'
        for line in myfile:
            num = int(line.rstrip('\n'))
            l_input.append(num)
        myfile.close()
        print 'file closed'
        return l_input
 
    def get_median(k1, k2):
        if (k1 + k2) % 2 != 0: return (k1 + k2 - 1) / 2
        else: return (k1 + k2) / 2
 
    def sort_insert(e, slist):
        n = len(slist)
        if n == 0:
            slist.append(e)
        else:
            k1 = 1
            k2 = n
            k = get_median(k1, k2)
            while k2 - k1 > 1:
                if e >= slist[k-1]: k1 = k
                elif e < slist[k-1]: k2 = k
                k = get_median(k1, k2)
            if k1 == k2:            
                if e >= slist[k-1]: slist.insert(k, e)
                else: slist.insert(k-1, e)
            elif k2 == k1 +1:
                if e <= slist[k1-1]: slist.insert(k1-1, e)
                elif e >= slist[k2-1]: slist.insert(k2, e)
                elif e <= slist[k-1]: slist.insert(k-1, e)
                elif e > slist[k-1]: slist.insert(k2-1, e)
        return slist
 
    def sort_median(mylist):
        slist = []
        medianlist = []
        n = len(mylist)
        for i in range (0, n):
            sort_insert(mylist[i],slist)
            medianlist.append(slist[get_median(0,len(slist)-1)])               
        return medianlist
 
    myfile = 'E://Median.txt'
    mylist = read_file(myfile)
    medianlist=sort_median(mylist)
    print 'answer:', sum(medianlist) % 10000

week 5 covered:

  • DIJKSTRA'S SHORTEST-PATH ALGORITHM
  • HEAPS
  • BALANCED BINARY SEARCH TREES

Programming assignment: In this programming problem you'll code up Dijkstra's shortest-path algorithm. The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200. Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. Your task is to run Dijkstra's shortest-path algorithm on this graph, using 1 (the first vertex) as the source vertex, and to compute the shortest-path distances between 1 and every other vertex of the graph. If there is no path between a vertex v and vertex 1, we'll define the shortest-path distance between 1 and v to be 1000000.

In this programming problem you'll code up Dijkstra's shortest-path algorithm. Download the text file here. (Right click and save link as). The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200. Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. For example, the 6th row has 6 as the first entry indicating that this row corresponds to the vertex labeled 6. The next entry of this row "141,8200" indicates that there is an edge between vertex 6 and vertex 141 that has length 8200. The rest of the pairs of this row indicate the other vertices adjacent to vertex 6 and the lengths of the corresponding edges.

Your task is to run Dijkstra's shortest-path algorithm on this graph, using 1 (the first vertex) as the source vertex, and to compute the shortest-path distances between 1 and every other vertex of the graph. If there is no path between a vertex v and vertex 1, we'll define the shortest-path distance between 1 and v to be 1000000.

You should report the shortest-path distances to the following ten vertices, in order: 7,37,59,82,99,115,133,165,188,197. You should encode the distances as a comma-separated string of integers. So if you find that all ten of these vertices except 115 are at distance 1000 away from vertex 1 and 115 is 2000 distance away, then your answer should be 1000,1000,1000,1000,1000,2000,1000,1000,1000,1000. Remember the order of reporting DOES MATTER, and the string should be in the same order in which the above ten vertices are given. Please type your answer in the space provided.

IMPLEMENTATION NOTES: This graph is small enough that the straightforward O(mn) time implementation of Dijkstra's algorithm should work fine. OPTIONAL: For those of you seeking an additional challenge, try implementing the heap-based version. Note this requires a heap that supports deletions, and you'll probably need to maintain some kind of mapping between vertices and their positions in the heap.

import sys
 
def ParseGraph(filename):
  """Parse a graph into adjacency list format per programming Q.5
 
Args:
- filename: the on-disk graph representation
Returns:
- vertices = {vertex_1: [(vertex_2, weight), ...]}
"""
  vertices = {}
 
  for l in open(filename):
    fields = [f for f in l.split()]
    vertex = int(fields.pop(0))
    edges = [tuple([int(t) for t in f.split(',')]) for f in fields]
    vertices[vertex] = edges
 
  return vertices
 
targets = [7, 37, 59, 82, 99, 115, 133, 165, 188, 197]
#          7, 37, 59, 82, 99, 115, 133 ,165, 188, 197
V = ParseGraph("algo5_DiJKSTRA.txt")
X = {1: True}
A = {1: 0}
 
while len(X) != len(V):
  min_src = 0
  min_dst = 0
  min_weight = sys.maxint
  for u in X:
    for v, l_uv in V[u]:
      if v in X:
        continue
      if A[u] + l_uv < min_weight:
        min_src, min_dst = u, v
        min_weight = A[u] + l_uv
  if min_src == 0:
    print 'Found nothing to match the greedy criterion! X = %s' % X
    sys.exit(1)
  X[min_dst] = True
  A[min_dst] = min_weight
 
print [A[t] for t in targets]

Go to page: