Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

CS206: Data Structures¶

Lab2: Data Structures¶

Professor Blank¶

Goals:

1. Review of Java language: functions, if-statements, return values
2. Review of Java Classes: methods
3. First Data Structures: LinkedList and Node

Rubric:

1. Not only must you have the correct answer, but it must also be formatted with proper indentation.
2. Points are assigned to each test

This lab is worth 100 points.

Due date: Wed, Feb 8, 2017, beginning of lab.

[Your name in next cell as a level-2 header. Delete this line when done.]

Problem 1¶

Write a Java function letterGrade that takes a double score and returns the letter grade based on the following scale:

• score > 97, returns "A+"
• score > 94, returns "A"
• score > 90, returns "A-"
• score > 87, returns "B+"
• score > 84, returns "B"
• score > 80, returns "B-"
• score > 77, returns "C+"
• score > 74, returns "C"
• score > 70, returns "C-"
• score > 67, returns "D+"
• score > 64, returns "D"
• score > 60, returns "D-"
• otherwise, returns "F"
String letterGrade(double score) {
// You code goes here
}


Put your function definition by itself in the following cell:

In [ ]:
// Please enter your Java code here

In [ ]:
letterGrade(70); // should give the result of D+


All of the following tests should return true:

In [ ]:
letterGrade(97) == "A";

In [ ]:
letterGrade(89.9) == "B+";

In [ ]:
letterGrade(60) == "F";

In [ ]:
letterGrade(65) == "D";


Problem 2¶

Write a Java class Robot that takes an double x and y in the constructor. The robot needs to keep track of where it is in the world.

Methods:

• moveUp(double distance)
• moveDown(double distance)
• moveLeft(double distance)
• moveRight(double distance)

Make it so that the robot can't move beyond (0,0) and (10,10). If it tries, it will be right at the boundary value. For example, if it were at (1, 5) and tried to move left 2, then it would be at (0, 5).

class Robot {
double x; // x: left and right (positive is to right)
double y; // y: up and down (positive is down)

// Enter constructor here

void moveDown(double distance) {
y += distance;
// make sure that y is in range
// Use: Math.max(a, b), Math.min(c, d)
// Enter code here
}
// Enter code here
}


Define your class by itself in the following cell:

In [ ]:
// Please enter your Java code here

In [ ]:
Robot robot = new Robot(0, 0);
robot.moveDown(1);
robot.moveDown(1);
robot.y == 2
robot.x == 0

In [ ]:
Robot robot = new Robot(1, 1);
robot.moveDown(5);
robot.moveRight(5);
robot.y == 6
robot.x == 6

In [ ]:
Robot robot = new Robot(0, 0);
robot.moveRight(5);
robot.moveRight(6);
robot.moveLeft(4);
robot.x == 6
robot.y == 0

In [ ]:
Robot robot = new Robot(0, 0);
robot.moveDown(2.5);
robot.moveUp(5.75);
robot.moveDown(1.2);
robot.moveRight(11);
robot.y == 1.2
robot.x == 10

In [ ]:
Robot robot = new Robot(0, 0);
robot.moveRight(11);
robot.moveLeft(9);
robot.moveUp(11);
robot.moveDown(1);
robot.y == 1
robot.x == 1


Problem 3¶

Write Java class LinkedList and Node.

Node:

• constructor takes an integer (called value)
• class has a property called next that is of type Node

• constructor takes no arguments
• has a property called list that is of type Node
• has a method called length() that returns how many nodes are in list
• has a method called append(Node node) that takes a node and adds it to the end of the list
• has a method called insert(Node node) that takes a node and adds it to the beginning of the list
• has a method called contains(int value) that takes a value, and returns true if it is in the list, and false otherwise.

Define your class Node by itself in the following cell:

In [ ]:
// Your code here

In [ ]:
Node node = new Node(42);
node.value == 42

In [ ]:
Node node = new Node(-1);
node.value == -1
node.next == null

In [ ]:
Node node = new Node(0);
node.next = new Node(1);
node.next.value == 1

In [ ]:
Node node = new Node(0);
node.next = new Node(1);
node.next.next = new Node(2);
node.next.next.value == 2


Define your class LinkedList in the following cell:

In [ ]:
// Please enter your Java code here

In [ ]:
LinkedList ll = new LinkedList();
ll.length() == 0

In [ ]:
LinkedList ll = new LinkedList();
ll.append(new Node(100))
ll.length() == 1

In [ ]:
LinkedList ll = new LinkedList();
ll.append(new Node(100))
ll.append(new Node(67))
ll.length() == 2
ll.list.value == 100
ll.list.next.value == 67

In [ ]:
LinkedList ll = new LinkedList();
ll.insert(new Node(100))
ll.insert(new Node(67))
ll.length() == 2
ll.list.value == 67
ll.list.next.value == 100

In [ ]:
LinkedList ll = new LinkedList();
ll.insert(new Node(100))
ll.append(new Node(67))
ll.length() == 2
ll.contains(67) == true
ll.contains(100) == true
ll.contains(85) == false


Reflections¶

The reflection cell is the most import cell in this lab... in all labs. In your reflection, you should:

• Reflect! Think and comment on what you have learned this lab, and this week.
• Connect the ideas onto your own life, and experiences.
• Comment on what you found challenging, and what you found intuitive.
• How did this lab match your expectations?

Put your reflections in the cell below. You should write more than a paragraph. Remember:

• don't indent paragraphs
• use Markdown highlighting
• use the spell checker

You should delete all of the cells except yours when you are done. Make sure to submit your lab.