Data Structures and Performance | Week 3

Course Name: Data Structures and Performance

Course Link: Data Structures and Performance

These are Data Structures and Performance Week 3 Coursera Answers

---

Programming Assignment: Making Flesch Score Calculation More Efficient

Steps: Create three java files Document.java, EfficientDocument.java and BasicDocument.java, create a zip file of three documents and upload in same zip file in both columns

Document.java:

package document;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public abstract class Document {

  private String text;

  protected Document(String text)
  {
    this.text = text;
  }
  
  protected List<String> getTokens(String pattern)
  {
    ArrayList<String> tokens = new ArrayList<String>();
    Pattern tokSplitter = Pattern.compile(pattern);
    Matcher m = tokSplitter.matcher(text);
    
    while (m.find()) {
      tokens.add(m.group());
    }
    
    return tokens;
  }
  
  protected int countSyllables(String word)
  {
      return 0;
  }
  
  public static boolean testCase(Document doc, int syllables, int words, int sentences)
  {
    System.out.println("Testing text: ");
    System.out.print(doc.getText() + "\n....");
    boolean passed = true;
    int syllFound = doc.getNumSyllables();
    int wordsFound = doc.getNumWords();
    int sentFound = doc.getNumSentences();
    if (syllFound != syllables) {
      System.out.println("\nIncorrect number of syllables.  Found " + syllFound 
          + ", expected " + syllables);
      passed = false;
    }
    if (wordsFound != words) {
      System.out.println("\nIncorrect number of words.  Found " + wordsFound 
          + ", expected " + words);
      passed = false;
    }
    if (sentFound != sentences) {
      System.out.println("\nIncorrect number of sentences.  Found " + sentFound 
          + ", expected " + sentences);
      passed = false;
    }
    
    if (passed) {
      System.out.println("passed.\n");
    }
    else {
      System.out.println("FAILED.\n");
    }
    return passed;
  }
  
  public abstract int getNumWords();
  
  public abstract int getNumSentences();
  
  public abstract int getNumSyllables();
  
  public String getText()
  {
    return this.text;
  }
  
  public double getFleschScore()
  {
    double score = 0.0;
    double term1 = 1.015 * getNumWords() * 1.0 / getNumSentences();
    double term2 = 84.6 * getNumSyllables() * 1.0 / getNumWords();
    score = 206.835 - term1 - term2;
    return score;
  }
}

---

These are Data Structures and Performance Week 3 Coursera Answers

---

EfficientDocument.java:

---

These are Data Structures and Performance Week 3 Coursera Answers

---

BasicDocument.java:

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Module and After Programming Assignment Quiz

Q1. Consider the function f(n)=3nlog2(n)+100log2(n). What is the tightest Big-O class for f(n)?

• O(n)
• O(nlog(n))
• O(log(n))
• O(n^2)

---

Q2. Does the following equality give the tightest Big-O equivalence class?
log10​(n)+25log5​(n)=O(log2​(n))

• Yes
• No

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q3. Consider the following code:

int sumSome(int[] arr){
   int sum = 0;
   for (int i=0; i<arr.length;  i++) {
      for (int j=0; j<arr.length; j+=2) {
         if (arr[i] > arr[j])
            sum += arr[i];
      }
   }
   return sum;
}

What is the tightest Big-O running time for this code in terms of the length of the array, n?

• O(nlog(n))
• O(n^2)
• O(n)
• O(log(n))

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q4. Consider the following code:

int sumSome(int[] arr){
   int sum = 0;
   for (int i=0; i<arr.length;  i++) {
      for (int j=1; j<arr.length; j = j*2) {
         if (arr[i] > arr[j])
            sum += arr[i];
      }
   }
   return sum;
}

What is the tightest Big-O running time of this code in terms of the length of the array, n?

• O(n^2)
• O(nlog(n))
• O(n)

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q5. You have two programs, program A and program B, that do the same thing. Program A runs in O(n) (tightest bound) and program B runs in O(n^2) (tightest bound) in the best, worst and average cases. A graph representing each program’s behavior is shown below. This graph is an approximation of the real values.

True or false: if you give both programs the same input, program A will always run faster than program B no matter what the input was.

• True
• False

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q6. You have two programs, program A and program B, that do the same thing, but may or may not contain exactly the same instructions. Both programs run in O(n) (tightest bound) in the best, worst and average cases.
True or false: If you give both programs the same input, you can be sure they will take the same amount of time to complete no matter what the input was.

• True
• False

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q7. What is the tightest Big-O running time to calculate the Flesch readability score for the BasicDocument class, where n is the length of the document?

• O(n^2)
• O(n)
• O(1)
• O(n^3)

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q8. What is the tightest Big-O running time to calculate the Flesch readability score the first time in the EfficientDocument class, where n is the length of the document, assuming you include the time it takes to initialize the numSyllables, numWords, and numSentences variables?
Note that this is not necessarily the running time that you saw when you plotted the graph of your EfficientDocument running time when you did your benchmarking. That time included the time to initialize the numSyllables, numWords and numSentences variables.

• O(1)
• O(n)
• O(n^2)

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q9. What is the tightest Big-O running time to calculate the Flesch readability score in the EfficientDocument class, where n is the length of the document, assuming you DO NOT include the time it takes to initialize the numSyllables, numWords, and numSentences variables (i.e. do not include the time taken by processText)?

• O(1)
• O(n)
• O(n^2)

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q10. Which of the following graphs looks most like the graph you (should have) produced in part 2 of the programming assignment? We are looking for you to compare the shapes of the functions only–these graphs are much smoother than what you would have seen. Also, ignore the specific numbers, and concentrate on the shapes and the relationship between the two lines. Note that the correct answer assumes that you have correctly implemented your two Document classes and your DocumentBenchmarking class.

Answer:

---

Q11. How much time did you spend on the programming assignment?

• <1 hour
• 1-2 hours
• 2-3 hours
• 3-4 hours
• 4-5 hours
• 5+ hours

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q12. How difficult did you find the programming assignment?

• Very Easy
• Easy
• Somewhat Easy
• Somewhat Difficult
• Difficult
• Very Difficult

---

These are Data Structures and Performance Week 3 Coursera Answers

---

Q13. How much did you enjoy the programming assignment?

• I really enjoyed the programming assignment
• I enjoyed the programming assignment
• I’m neutral about the programming assignment
• I did not enjoy the programming assignment
• I really did not enjoy the programming assignment

---

These are Data Structures and Performance Week 3 Coursera Answers

---

More Weeks of the course: Click Here

More Coursera courses: https://progiez.com/coursera