DSA
MapReduce
Skip To Content
Dashboard
  • Login
  • Dashboard
  • Calendar
  • Inbox
  • History
  • BYU Canvas Info & Help
Close
  • My Dashboard
  • DSA
  • Assignments
  • MapReduce
  • Home
  • Modules
  • Syllabus
  • Assignments
  • Collaborations
  • Class Notebook
  • Google Drive
  • Office 365
  • Gradescope
  • Microsoft Teams meetings
  • Lucid (Whiteboard)

MapReduce

  • Due No Due Date
  • Points 13
  • Submitting a file upload
  • Available after Jan 21, 2021 at 12am

MapReduce Exercise

Roles

  • master--class instructor
  • groupers--five or more students
  • mappers--twenty two students who need a laptop, tablet or phone and a pencil or pen. Each mapper will have a number between 1 and 22. 
  • reducers--five or more students who need a pencil or pen

Notes for Smaller Classes and Online Students

Try to get as many people to participate as possible to work on this assignment together. Get some volunteers who are not in the class if you can.

You can reduce the number of chapters you process to fit the number of mappers, but doing at lease five in parallel will give you the best idea of how MapReduce achieves parallel computation. Students can serve more than one role if there are fewer students than are needed. Just be sure to keep track of what work *could* have happened in parallel if sufficient resources were available. 

Algorithm

  • Mapper N will
    1. Find the text for First Nephi Chapter N online
    2. Find all occurrences of the following words in First Nephi Chapter N.
      • Egypt
      • God
      • Jacob
      • Joseph
      • Judah
      • Laban
      • Laman
      • Lehi
      • Lemuel
      • Moses
      • Nephi
    3. Write each proper noun on an index card. One word per card. I.e. If Nephi occurs 20 times in your chapter, you will have 20 index cards with Nephi written on them.
  • The Grouper will
    1. Get cards from the mappers
    2. Collate the cards into piles, one pile per proper noun. I.e. a pile for Nephi, a pile for Lehi, etc. 
    3. Distribute complete piles to reducers. All piles for a given noun go to same reducer. 
    4. No need to wait for all cards before distributing.
  • Reducers are responsible or words in certain range (e.g. A-E, F-J, K-O, P-T, U-Z)
    1. Count the cards in each pile
    2. Produce one card with a list of the words and the count of each
    3. Give final card to the Master

Questions

In a group that includes mappers and at least one reducer and one groups, answer the following questions:

  1. What is the role of the master?
  2. What is the role of the mapper?
  3. How does the mapper role differ from the role of the reducer?
  4. Why is the work of the grouper tough in this exercise?
  5. What work happened independently?
  6. What work was dependent on other work?
  7. How much longer would it take to count all the occurrences of every proper noun in the Book of Mormon, assuming you had enough workers to assign a chapter to each and increase the reducers proportionally?
  8. How would you apply this method to
    1. Grouping words by length
    2. Find all verses that mention a specific word
    3. Count URL accesses for a large Web site with 1000s of servers
0
Please include a description
Additional Comments:
Rating max score to > pts
Please include a rating title

Rubric

Find Rubric
Please include a title
Find a Rubric
Title
You've already rated students with this rubric. Any major changes could affect their assessment results.
 
 
 
 
 
 
 
     
Can't change a rubric once you've started using it.  
Title
Criteria Ratings Pts
This criterion is linked to a Learning Outcome Description of criterion
threshold: 5 pts
Edit criterion description Delete criterion row
5 to >0 pts Full Marks blank
0 to >0 pts No Marks blank_2
This area will be used by the assessor to leave comments related to this criterion.
pts
  / 5 pts
--
Additional Comments
This criterion is linked to a Learning Outcome Description of criterion
threshold: 5 pts
Edit criterion description Delete criterion row
5 to >0 pts Full Marks blank
0 to >0 pts No Marks blank_2
This area will be used by the assessor to leave comments related to this criterion.
pts
  / 5 pts
--
Additional Comments
Total Points: 5 out of 5
Previous
Next
Parallel Architectures QuizNext Module:
Failure and Consensus