Data Structures and Performance | Week 4
Course Name: Data Structures and Performance
Course Link: Data Structures and Performance
These are Data Structures and Performance Week 4 Coursera Answers
Programming Assignment: Implement and Test a Linked List
Steps: Create two java files MyLinkedList.java and MyLinkedListTester.java, and upload both files in their respective columns.
MyLinkedList.java:
package textgen;
import java.util.AbstractList;
public class MyLinkedList<E> extends AbstractList<E> {
LLNode<E> head;
LLNode<E> tail;
int size;
public MyLinkedList() {
this.head = new LLNode<>(null);
this.tail = new LLNode<>(null);
this.head.next = tail;
this.tail.prev = head;
}
public boolean add(E element) {
if (element == null) {
throw new NullPointerException("List can't take null");
}
LLNode<E> newNode = new LLNode<>(element);
newNode.prev = tail.prev;
newNode.next = tail;
tail.prev.next = newNode;
tail.prev = newNode;
this.size++;
return true;
}
public E get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("MyLinkedList get method index outOfBound : " + index);
} else {
LLNode<E> targetNode = getNode(index);
return targetNode.data;
}
}
private LLNode<E> getNode(int index) {
LLNode<E> currentNode = head;
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
public void add(int index, E element) {
if (element == null) {
throw new NullPointerException("List can't take null");
}
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("LLNode add failed: " + index);
}
LLNode<E> newNode = new LLNode<>(element);
LLNode<E> node = getNode(index);
newNode.prev = node.prev;
newNode.next = node;
newNode.prev.next = newNode;
node.prev = newNode;
this.size++;
}
public int size() {
return size;
}
public E remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("LLNode remove outOfBound: " + index);
}
LLNode<E> targetNode = getNode(index);
targetNode.prev.next = targetNode.next;
targetNode.next.prev = targetNode.prev;
this.size--;
return targetNode.data;
}
public E set(int index, E element) {
if (element == null) {
throw new NullPointerException("List can't take null");
}
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("LLNode set failed: " + index);
}
LLNode<E> node = getNode(index);
E oldValue = node.data;
node.data = element;
return oldValue;
}
public String toString() {
String output = "";
LLNode<E> curNode = head;
while (curNode != null) {
output += curNode.toString();
curNode = curNode.next;
}
return output;
}
}
class LLNode<E> {
LLNode<E> prev;
LLNode<E> next;
E data;
public LLNode(E e, LLNode<E> prev) {
this(e);
this.prev = prev;
if (prev != null) {
prev.next = this;
}
}
public LLNode(E e) {
this.data = e;
this.prev = null;
this.next = null;
}
public String toString() {
return "prev: " + prev + " ,data = " + data + ", next" + next + "\n";
}
}These are Data Structures and Performance Week 4 Coursera Answers
MyLinkedListTesting.java:
package textgen;
import static org.junit.Assert.*;
import java.util.LinkedList;
import org.junit.Before;
import org.junit.Test;
public class MyLinkedListTester {
private static final int LONG_LIST_LENGTH =10;
MyLinkedList<String> shortList;
MyLinkedList<Integer> emptyList;
MyLinkedList<Integer> longerList;
MyLinkedList<Integer> list1;
@Before
public void setUp() throws Exception {
shortList = new MyLinkedList<String>();
shortList.add("A");
shortList.add("B");
emptyList = new MyLinkedList<Integer>();
longerList = new MyLinkedList<Integer>();
for (int i = 0; i < LONG_LIST_LENGTH; i++) {
longerList.add(i);
}
list1 = new MyLinkedList<Integer>();
list1.add(65);
list1.add(21);
list1.add(42);
}
@Test
public void testGet() {
try {
emptyList.get(0);
fail("Check out of bounds");
} catch (IndexOutOfBoundsException e) {
}
assertEquals("Check first", "A", shortList.get(0));
assertEquals("Check second", "B", shortList.get(1));
try {
shortList.get(-1);
fail("Check out of bounds");
} catch (IndexOutOfBoundsException e) {
}
try {
shortList.get(2);
fail("Check out of bounds");
} catch (IndexOutOfBoundsException e) {
}
for(int i = 0; i<LONG_LIST_LENGTH; i++ ) {
assertEquals("Check "+i+ " element", (Integer)i, longerList.get(i));
}
try {
longerList.get(-1);
fail("Check out of bounds");
} catch (IndexOutOfBoundsException e) {
}
try {
longerList.get(LONG_LIST_LENGTH);
fail("Check out of bounds");
} catch (IndexOutOfBoundsException e) {
}
}
@Test
public void testRemove() {
try {
list1.remove(-1);
fail("AddAtIndex: Add at low index");
} catch(Exception e) {
}
try {
list1.remove(11);
fail("AddAtIndex: Add at low index");
} catch(Exception e) {
}
int a = list1.remove(0);
assertEquals("Remove: check a is correct ", 65, a);
assertEquals("Remove: check element 0 is correct ", (Integer)21, list1.get(0));
assertEquals("Remove: check size is correct ", 2, list1.size());
assertEquals("remove: check link after remove", list1.head, list1.head.next.prev);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testRemoveOutOfBounds() {
list1.remove(-1);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testRemoveOutOfBounds2() {
list1.remove(11);
}
@Test
public void testAddEnd() {
try {
list1.add(null);
fail("addEnd : Can't add null");
} catch(Exception e) {
}
emptyList.add(1);
assertEquals("Add: add one element is correct", (Integer)1, emptyList.get(0));
assertEquals("Add: add one element size is correct", (int) 1, emptyList.size());
}
@Test
public void testSize() {
int size = list1.size();
assertEquals("List1 size is correct", 3, size);
list1.remove(0);
assertEquals("List1 size is 2 after remove 1 element", 2, list1.size());
list1.add(110);
assertEquals("List1 size is 3 afer add one element", 3, list1.size());
}
@Test
public void testAddAtIndex() {
try {
list1.add(-1, -111);
fail("AddAtIndex: Add at low index");
} catch(Exception e) {
}
try {
list1.add(11, 11);
fail("AddAtIndex: Add at low index");
} catch(Exception e) {
}
try {
list1.add(1, null);
fail("AddAtIndex : Can't add null");
} catch(Exception e) {
}
shortList.add(0, "test");
assertEquals("addAtIndex: check value", shortList.get(0), "test");
assertEquals("addAtIndex: check value behind new item", shortList.get(1), "A");
assertEquals("addAtIndex: check size after addition", shortList.size(), 3);
}
@Test
public void testSet() {
try {
list1.set(-1, -111);
fail("AddAtIndex: Add at low index");
} catch(Exception e) {
}
try {
list1.set(11, 11);
fail("AddAtIndex: Add at low index");
} catch(Exception e) {
}
list1.set(0, 110);
assertEquals("set: check new value is set ", (Integer) 110, list1.get(0) );
assertEquals("set: check size afeter value is set", 3, list1.size());
}
@Test
public void testHeadTail() {
assertEquals("Head Tail: check head", list1.head, list1.head.next.prev);
assertEquals("Head Tail: check tail", list1.tail, list1.tail.prev.next);
}
}
These are Data Structures and Performance Week 4 Coursera Answers
Week 4 Reflective Programming Assignment Quiz
Q1. How much time did it take to complete the MyLinkedList project (both implementation and tester)?
- < 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 4 Coursera Answers
Q2. How difficult would you rate the MyLinkedList assignment relative to other programming projects you’ve done (in and outside this course)?
- Extremely easy
- Easy
- Somewhat Easy
- Somewhat Difficult
- Difficult
- Extremely Difficult
Answer: Somewhat Easy
These are Data Structures and Performance Week 4 Coursera Answers
Q3. Did you enjoy the MyLinkedList programming assignment?
- I really enjoyed the programming assignment
- I enjoyed the programming assignment
- I am 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 4 Coursera Answers
Q4. Please tell us, in 1-2 sentences, what was the trickiest part for you about the MyLinkedList assignment (including either implementation or testing).
Answer: In a linked list, reverse traversing is challenging.
These are Data Structures and Performance Week 4 Coursera Answers
Q5. Did you do the optional Markov Text Generation Project?
- Yes, and I got it working!
- Yes, but I didn’t quite finish it or didn’t quite get it working completely
- No
Answer: Yes, and I got it working!
These are Data Structures and Performance Week 4 Coursera Answers
Q6. How long did you work on the Markov Text Generator Extension?
- Not applicable (I didn’t work on the Markov Text Generator)
- < 1 hour
- 1-2 hours
- 2-3 hours
- 3-4 hours
- 4 hours
Answer: < 1 hour
These are Data Structures and Performance Week 4 Coursera Answers
Q7. How difficult would you rate the Markov Text Generator extension relative to other programming projects you’ve done (in and outside this course)?
- Extremely easy
- Easy
- Somewhat easy
- Somewhat hard
- Hard
- Extremely hard
Answer: Somewhat easy
These are Data Structures and Performance Week 4 Coursera Answers
Q8. Did you enjoy the programming assignment on Markov Text Generation
- Not applicable
- I really enjoyed the programming assignment.
- I enjoyed the programming assignment.
- I am 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 4 Coursera Answers
Q9. Please tell us, in 1-2 sentences, what was the trickiest part for you about the Markov Text Generator extension (including either implementation or testing).
Answer: The Evaluation Problem and the Forward Algorithm.
These are Data Structures and Performance Week 4 Coursera Answers
More Weeks of the course: Click Here
More Coursera courses: https://progiez.com/coursera
