Data Structures and Performance | Week 5

Course Name: Data Structures and Performance

Course Link: Data Structures and Performance

These are Data Structures and Performance Week 5 Coursera Answers

Programming Assignment: Spell Checking and Autocomplete

Steps: Create two zip files: mod4part1.zip(Spell Checking) and mod4part2.zip(Autocomplete), mod4part1.zip(Spell Checking) consists two java files DictionaryBST.java and DictionaryLL.java, create zip of these two files and upload in first column, mod4part2.zip(Autocomplete) consists one java file AutoCompleteDictionaryTrie.java, create zip file of this and upload in second column.

mod4part1.zip(Spell Checking):

DictionaryBST.java:

package spelling;

import java.util.TreeSet;

public class DictionaryBST implements Dictionary {
   private TreeSet<String> dict;
   
   public DictionaryBST() {
       dict = new TreeSet<String>();
   }
   
   public boolean addWord(String word) {
       return dict.add(word.toLowerCase());
   }

   public int size() {
       return dict.size();
   }

   public boolean isWord(String s) {
       return dict.contains(s.toLowerCase());
   }
}

DictionaryLL.java:

package spelling;

import java.util.LinkedList;

public class DictionaryLL implements Dictionary {

  private LinkedList<String> dict;

  DictionaryLL() {
    dict = new LinkedList<String>();
  }

    public boolean addWord(String word) {
      String lowercaseWord = word.toLowerCase();
      if (!dict.contains(lowercaseWord)) {
        dict.add(lowercaseWord);
        return true;
      } else {
        return false;
      }
    }

    public int size() {
        return dict.size();
    }

    public boolean isWord(String s) {
        return dict.contains(s.toLowerCase());
    }

}

These are Data Structures and Performance Week 5 Coursera Answers

mod4part2.zip(Autocomplete):

AutoCompleteDictionaryTrie.java:

package spelling;

import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;

public class AutoCompleteDictionaryTrie implements Dictionary, AutoComplete {

    private TrieNode root;
    private int size;
    

    public AutoCompleteDictionaryTrie() {
        root = new TrieNode();
    }

    public boolean addWord(String word) {
        TrieNode preNode = root;
        word = word.toLowerCase();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (preNode.getChild(c) == null) {
                preNode = preNode.insert(chars[i]);
            } else {
                preNode = preNode.getChild(c);
            }
            if (i == (chars.length - 1) && !preNode.endsWord()) {
                preNode.setEndsWord(true);
                this.size++;
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    public boolean isWord(String s) {
        s = s.toLowerCase();
        char[] chars = s.toCharArray();
        TrieNode preNode = root;
        for (int i = 0; i < chars.length; i++) {
            preNode = preNode.getChild(chars[i]);
            if (preNode == null)
                return false;
        }
        return preNode.endsWord();
    }

    @Override
    public List<String> predictCompletions(String prefix, int numCompletions) {
        List<String> completions = new LinkedList<String>();
        char[] chars = prefix.toCharArray();
        TrieNode preNode = root;
        for (char c : chars) {
            preNode = preNode.getChild(c);
            if (preNode == null) {
                return completions;
            }
        }
        LinkedList<TrieNode> queue = new LinkedList<TrieNode>();
        queue.add(preNode);
        while (queue.size() > 0 && completions.size() < numCompletions) {
            TrieNode node = queue.removeFirst();
            if (node.endsWord()) {
                completions.add(node.getText());
            }
            Set<Character> charSet = node.getValidNextCharacters();
            for (Character c : charSet) {
                queue.add(node.getChild(c));
            }
        }

        return completions;
    }

    public void printTree() {
        printNode(root);
    }

    public void printNode(TrieNode curr) {
        if (curr == null)
            return;

        System.out.println(curr.getText());

        TrieNode next = null;
        for (Character c : curr.getValidNextCharacters()) {
            next = curr.getChild(c);
            printNode(next);
        }
    }

}

These are Data Structures and Performance Week 5 Coursera Answers

See also  Data Structures and Performance | Week 1

Week 5 Content and Programming Assignment Quiz

Q1. Which of the following structures are trees? Select all that apply.

Answer:

image 2
image 3
image 4

These are Data Structures and Performance Week 5 Coursera Answers

Q2. Which of the following are Binary Search Trees? Select all that apply.

Answer:

image 4

These are Data Structures and Performance Week 5 Coursera Answers

Q3. Which of the following statements are true about the following binary search tree? Select all that apply.

image 5

Assume that no nodes have been deleted from this tree.

  • 42 must have been inserted first.
  • 32 must have been inserted before 45
  • A different insertion order with the same values could give a different tree structure.
  • 32 must have been inserted before 12
  • There is only one insertion order that could have produced this tree.
Answer: 32 must have been inserted before 12, A different insertion order with the same values could give a different tree structure., 42 must have been inserted first.

These are Data Structures and Performance Week 5 Coursera Answers

Q4. Which of the following statements are true about the running time of binary search trees? Assume that when we use big-O notation we mean the tightest big-O bound. Select all that apply.

  • The tightest possible worst case time to find an element in an arbitrary BST is O(n)
  • The tightest possible worst case time to find an element in an arbitrary BST is O(log(n))
  • The tightest possible worst case time to find an element in a balanced BST is O(log(n))
  • Inserting sorted data into an unbalanced BST leads to the worst case BST structure (i.e. a structure where finding an element will take the longest).
  • The tightest possible worst case time to find an element in a balanced BST is O(n)
Answer: The tightest possible worst case time to find an element in an arbitrary BST is O(n), The tightest possible worst case time to find an element in a balanced BST is O(log(n)), Inserting sorted data into an unbalanced BST leads to the worst case BST structure (i.e. a structure where finding an element will take the longest).

These are Data Structures and Performance Week 5 Coursera Answers

See also  Data Structures and Performance | Week 4

Q5. From your benchmarking of the DictionaryLL and DictionaryBST structures you implemented, which structure is the better choice?

  • DictionaryBST
  • DictionaryLL
  • They are about the same
Answer: DictionaryBST

These are Data Structures and Performance Week 5 Coursera Answers

Q6. In your benchmarking of the DictionaryBST structure, you probably found that the time to find words did not significantly increase as the Dictionary got larger. Which of the following is the most likely reason for this behavior?

  • We were measuring the best case performance of the dictionary, which does not change as the dictionary size grows.
  • The running time to find an element in a balanced BST is O(1) so we would not expect the running time to get larger as the dictionary got bigger.
  • log(n) is sufficiently small and grows sufficiently slowly that other factors (e.g. memory use) had a bigger effect on the running time than the size to find the word in the dictionary.
Answer: log(n) is sufficiently small and grows sufficiently slowly that other factors (e.g. memory use) had a bigger effect on the running time than the size to find the word in the dictionary.

These are Data Structures and Performance Week 5 Coursera Answers

Q7. Did you do the optional extension in the programming assignment to take case into account when spell checking/doing auto complete.

  • Yes, and I got it working
  • Yes, but I didn’t quite finish it/didn’t quite get it completely working
  • No
Answer: Yes, and I got it working

These are Data Structures and Performance Week 5 Coursera Answers

Q8. How much time did you spend on the programming assignment this week?

  • <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 5 Coursera Answers

See also  Data Structures and Performance | Week 2

Q9. How difficult was the programming assignment for this week?

  • Very Easy
  • Easy
  • Somewhat Easy
  • Somewhat Difficult
  • Difficult
  • Very Difficult
Answer: Somewhat Easy

Q10. How much did you enjoy the programming assignment for this week?

  • I really enjoyed the assignment this week.
  • I enjoyed the assignment this week.
  • I’m neutral about the assignment this week.
  • I did not enjoy the assignment this week.
  • I really did not enjoy the assignment this week.
Answer: I enjoyed the assignment this week.

These are Data Structures and Performance Week 5 Coursera Answers

More Weeks of the course: Click Here

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

Data Structures and Performance Week 5 Coursera Answers

Similar: