Data Structures and Performance | Week 6
Course Name: Data Structures and Performance
Course Link: Data Structures and Performance
These are Data Structures and Performance Week 6 Coursera Answers
Programming Assignment: Spelling Suggestions
Steps: Create two java files of same name NearbyWords.java, one for column one i.e., Mutations and another for column second i.e., Suggestions and upload in respective columns.
Mutations(NearbyWords.java):
package spelling;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
public class NearbyWords implements SpellingSuggest {
private static final int THRESHOLD = 1000;
Dictionary dict;
public NearbyWords (Dictionary dict)
{
this.dict = dict;
}
public List<String> distanceOne(String s, boolean wordsOnly ) {
List<String> retList = new ArrayList<String>();
insertions(s, retList, wordsOnly);
substitution(s, retList, wordsOnly);
deletions(s, retList, wordsOnly);
return retList;
}
public void substitution(String s, List<String> currentList, boolean wordsOnly) {
for(int index = 0; index < s.length(); index++){
for(int charCode = (int)'a'; charCode <= (int)'z'; charCode++) {
StringBuffer sb = new StringBuffer(s);
sb.setCharAt(index, (char)charCode);
if(!currentList.contains(sb.toString()) &&
(!wordsOnly||dict.isWord(sb.toString())) &&
!s.equals(sb.toString())) {
currentList.add(sb.toString());
}
}
}
}
public void insertions(String s, List<String> currentList, boolean wordsOnly ) {
for(int index = 0; index < s.length() + 1; index++){
for(int charCode = (int)'a'; charCode <= (int)'z'; charCode++) {
String[] strs = s.split("");
LinkedList<String> sList = new LinkedList(Arrays.asList(strs));
sList.add(index, Character.toString((char)charCode));
String newWord = listToString(sList);
if(!currentList.contains(newWord) &&
(!wordsOnly||dict.isWord(newWord)) &&
!s.equals(newWord)) {
currentList.add(newWord);
}
}
}
}
private String listToString(List<String> list) {
String ret = "";
for(String c: list) {
ret += c;
}
return ret;
}
public void deletions(String s, List<String> currentList, boolean wordsOnly ) {
for(int index = 0; index < s.length(); index++){
String[] strs = s.split("");
LinkedList<String> sList = new LinkedList(Arrays.asList(strs));
sList.remove(index);
String newWord = listToString(sList);
if(!currentList.contains(newWord) &&
(!wordsOnly||dict.isWord(newWord)) &&
!s.equals(newWord)) {
currentList.add(newWord);
}
}
}
@Override
public List<String> suggestions(String word, int numSuggestions) {
List<String> queue = new LinkedList<String>();
HashSet<String> visited = new HashSet<String>();
List<String> retList = new LinkedList<String>();
queue.add(word);
String curWord = queue.remove(0);
while(curWord != null && retList.size() < numSuggestions) {
if(visited.contains(curWord)) {
curWord = queue.remove(0);
} else {
visited.add(curWord);
List<String> words = distanceOne(curWord, true);
retList.addAll(words);
queue.addAll(words);
curWord = queue.remove(0);
}
}
return retList.subList(0, numSuggestions);
}
public static void main(String[] args) {
String word = "i";
Dictionary d = new DictionaryHashSet();
DictionaryLoader.loadDictionary(d, "data/dict.txt");
NearbyWords w = new NearbyWords(d);
List<String> l = w.distanceOne(word, true);
System.out.println("One away word Strings for for \""+word+"\" are:");
System.out.println(l+"\n");
word = "tailo";
List<String> suggest = w.suggestions(word, 10);
System.out.println("Spelling Suggestions for \""+word+"\" are:");
System.out.println(suggest);
}
}
These are Data Structures and Performance Week 6 Coursera Answers
Suggestions(NearbyWords.java):
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Week 6: Programming Assignment and Content Quiz
Q1. Which of the following is a reason why hash tables are a good choice for storing and retrieving data?
- They store data in sorted order so it is easy to find the minimum and maximum element
- They are very fast in practice for finding items in a set
- They are very space efficient compared to binary search trees and linked lists
Answer: They are very fast in practice for finding items in a set
These are Data Structures and Performance Week 6 Coursera Answers
Q2. What is a “collision” in a hash table?
- When the hash function for two different items returns the same value (i.e., h(x) == h(y) for x!=y)
- When you insert the same item twice into a hash table
- When the value returned by the hash function is the same as the item you are inserting (i.e. h(x)=x)
Answer: When the hash function for two different items returns the same value (i.e., h(x) == h(y) for x!=y)
These are Data Structures and Performance Week 6 Coursera Answers
Q3. Which of the following is true of searching for an element in a Hash Table that is implemented using linear probing (you may assume a Hash Table that is ~70% full)?
- Worst case is O(1)
- Average case is log(n)
- Average case is O(1)
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q4. When a hash table becomes too full, which of the following is required to resize the table?
- Create a new table which is larger than the original table. Then bulk copy keys from one table to the other (i.e. if a key is in location X in the original table, it remains in position X in the new table).
- Create a new table which is larger than the original table. Then individually reinsert each key from the old table into the new table (i.e. if a key is in location X in the original table, it may or may not be in position X in the new table).
- Add extra space at the end of the existing hash table and leave the old keys in place.
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q5. In the algorithm for spelling suggestions in this week’s assignment, there was a hash set to mark Strings as visited. What is the BEST ANSWER for why we used the visited set?
- So that our exploration was of a tree of words, and if we had a word repeated, it wouldn’t be a tree anymore.
- To avoid exploring all the possible String mutations for an individual String more than once.
- To avoid testing to see if a mutated String was a real word (and hence a spelling suggestion) more than once.
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q6. Which of these is an invalid word path (assume all words below are valid dictionary words)?
- From cake to stake: cake -> sake -> stake
- From broom to mop: broom -> boom -> boo -> moo -> mop
- From shy to chime: shy -> she -> he -> hide -> chide -> chime
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q7. How much time did you spend on the programming project this week (include time spent on the optional WordPath assignment if you did it)?
- <1 hour
- 1-2 hours
- 2-3 hours
- 3-4 hours
- 4+ hours
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q8. How difficult did you find the project this week?
- Very easy
- Easy
- Somewhat easy
- Somewhat difficult
- Difficult
- Very difficult
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q9. Thinking of this COURSE OVERALL. Which assignment did you enjoy the most?
- Week 1: Flesch Score
- Week 2: Efficient Flesch Score
- Week 3: MyLinkedList
- Week 3: Markov Text Generation
- Week 4: Spell Checking and Autocomplete
- Week 5: Spelling Suggestions
- Week 5: Word Paths
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q10. Thinking of this COURSE OVERALL. Which assignment are you most proud of completing?
- Week 1: Flesch Score
- Week 2: Efficient Flesch Score
- Week 3: MyLinkedList
- Week 3: Markov Text Generation
- Week 4: Spell Check and Autocomplete
- Week 5: Spelling Suggestions
- Week 5: Word Path
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q11. What is the one thing you liked most about this course?
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
Q12. What is the one thing you would have liked to see changed about this course?
Answer: Please login to see answer.
These are Data Structures and Performance Week 6 Coursera Answers
More Weeks of the course: Click Here
More Coursera courses: https://progiez.com/coursera
![Data Structures and Performance | Week 6 1 Data Structures and Performance Week 6 Coursera Answers](https://progiez.com/wp-content/uploads/2023/01/cropped-3-progiez-logo.png-1.png)