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:
package document;
import java.util.List;
public class EfficientDocument extends Document {
private int numWords;
private int numSentences;
private int numSyllables;
public EfficientDocument(String text) {
super(text);
processText();
}
private boolean isWord(String tok) {
return tok.matches("[a-zA-Z]+");
}
protected int countSyllables(String word) {
word = word.replaceAll("[^a-zA-Z]", "");
int syllables = 0;
boolean prevVowel = false;
for (int i = 0; i < word.length(); i++) {
char c = Character.toLowerCase(word.charAt(i));
boolean isVowel = c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y';
if (isVowel && !prevVowel) {
syllables++;
}
prevVowel = isVowel;
}
if (word.endsWith("e") && syllables > 1) {
char secondLastChar = word.charAt(word.length() - 2);
boolean secondLastCharIsVowel = "aeiouy".indexOf(Character.toLowerCase(secondLastChar)) != -1;
if (!secondLastCharIsVowel) {
syllables--;
}
}
if (syllables == 0) {
syllables = 1;
}
return syllables;
}
private void processText() {
List<String> tokens = getTokens("[!?.]+|[a-zA-Z]+");
numWords = 0;
numSentences = 0;
numSyllables = 0;
for (int i = 0; i < tokens.size(); i++) {
if (isWord(tokens.get(i))) {
numWords++;
numSyllables += countSyllables(tokens.get(i));
if (i == tokens.size() - 1) {
numSentences++;
}
} else {
numSentences++;
}
}
}
@Override
public int getNumSentences() {
return numSentences;
}
@Override
public int getNumWords() {
return numWords;
}
@Override
public int getNumSyllables() {
return numSyllables;
}
public static void main(String[] args) {
testCase(new EfficientDocument("This is a test. How many??? "
+ "Senteeeeeeeeeences are here... there should be 5! Right?"),
16, 13, 5);
testCase(new EfficientDocument(""), 0, 0, 0);
testCase(new EfficientDocument("sentence, with, lots, of, commas.! "
+ "(And some poaren)). The output is: 7.5."), 15, 11, 4);
testCase(new EfficientDocument("many??? Senteeeeeeeeeences are"), 6, 3, 2);
testCase(new EfficientDocument("Here is a series of test sentences. Your program should "
+ "find 3 sentences, 33 words, and 49 syllables. Not every word will have "
+ "the correct amount of syllables (example, for example), "
+ "but most of them will."), 49, 33, 3);
testCase(new EfficientDocument("Segue"), 2, 1, 1);
testCase(new EfficientDocument("Sentence"), 2, 1, 1);
testCase(new EfficientDocument("Sentences?!"), 3, 1, 1);
testCase(new EfficientDocument("Lorem ipsum dolor sit amet, qui ex choro quodsi moderatius, nam dolores explicari forensibus ad."),
32, 15, 1);
}
}
These are Data Structures and Performance Week 3 Coursera Answers
BasicDocument.java:
package document;
import java.util.List;
public class BasicDocument extends Document {
public BasicDocument(String text) {
super(text);
}
@Override
public int getNumWords() {
String pattern = "[a-zA-Z]+";
List<String> tokenizeByWords = getTokens(pattern);
return tokenizeByWords.size();
}
@Override
public int getNumSentences() {
String pattern = "[^!.?]+";
List<String> tokenizeBySentence = getTokens(pattern);
return tokenizeBySentence.size();
}
@Override
public int getNumSyllables() {
String pattern = "[a-zA-Z]+";
List<String> tokenizeByWords = getTokens(pattern);
int numSyllables = 0;
for(int i = 0; i < tokenizeByWords.size(); i++){
String lowerCase = tokenizeByWords.get(i).toLowerCase();
numSyllables += countSyllables(lowerCase);
}
return numSyllables;
}
public static void main(String[] args) {
testCase(new BasicDocument("This is a test. How many??? "
+ "Senteeeeeeeeeences are here... there should be 5! Right?"),
16, 13, 5);
testCase(new BasicDocument(""), 0, 0, 0);
testCase(new BasicDocument("sentence, with, lots, of, commas.! "
+ "(And some poaren)). The output is: 7.5."), 15, 11, 4);
testCase(new BasicDocument("many??? Senteeeeeeeeeences are"), 6, 3, 2);
testCase(new BasicDocument("Here is a series of test sentences. Your program should "
+ "find 3 sentences, 33 words, and 49 syllables. Not every word will have "
+ "the correct amount of syllables (example, for example), "
+ "but most of them will."), 49, 33, 3);
testCase(new BasicDocument("Segue"), 2, 1, 1);
testCase(new BasicDocument("Sentence"), 2, 1, 1);
testCase(new BasicDocument("Sentences?!"), 3, 1, 1);
testCase(new BasicDocument("Lorem ipsum dolor sit amet, qui ex choro quodsi moderatius, nam dolores explicari forensibus ad."),
32, 15, 1);
}
}
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)
Answer: O(nlog(n))
Q2. Does the following equality give the tightest Big-O equivalence class?
log10(n)+25log5(n)=O(log2(n))
- Yes
- No
Answer: Yes
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))
Answer: O(n^2)
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)
Answer: O(nlog(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
Answer: 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
Answer: 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)
Answer: O(n)
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)
Answer: O(n)
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)
Answer: O(1)
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
Answer: <1 hour
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
Answer: Somewhat Easy
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
Answer: I enjoyed 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
