Software Technology 2 (7170)
Assignment 2 – Data Structures
Submission date: 23:55 Sunday 12/05/2019 (Week 13)
Type: Individual assignment
Submission: A compressed file that contains the following:
Snake Game project in Eclipse for Problem 1, and
MS Word file that contains Java sources and your comments for Problems 2, 3 and 4.
Submit this compressed file via Canvas site of this unit. Email submission is not accepted.
Total mark: 15
Proportion of unit assessment: 15%
Late submission: 5% of the total mark (i.e., 0.75 mark) per day.
Language: Java (use Google Java Style https://google.github.io/styleguide/javaguide.html)
[1 mark] For using Google Java Style
Problem 1.[8 marks] Snake Game
Snake (also called Nibbles) is a classic game which is played on a rectangular game board. When the game starts, an apple is randomly added to the game board and the snake moves forward. The player uses the 4 arrow keys on the keyboard to change the current direction of the snake. When the snake eats the apple, the body of the snake grows longer, and another apple is randomly added to the game board. The game is over if the snake either runs into one of the 4 edges of the game board, or it runs into its own body.
In this project, you will modify the existing Snake game implemented by Jan Bodnar and available at https://github.com/janbodnar/Java-Snake-Game to gain experience with linked list data structures. This game program uses two arrays below to store the x and y coordinates of all joints of the snake:
private final int x[] = new int[ALL_DOTS];
private final int y[] = new int[ALL_DOTS];
You are required to remove these two arrays from the game program and implement SnakeLinkedList and SnakeNode classes to perform the tasks of these two arrays. Other existing variables and method names in the game program are unchanged (however some method bodies that contain the x and y coordinates can be modified).
The SnakeLinkedList class is either singly-linked list or doubly-linked list class. This class contains the basic variables and methods for a linked list and the snakeMove method to move the snake. You cannot use the existing LinkedList class in Java to implement this class.
The SnakeNode class contains the basic variables and methods for a linked list node, the x and y coordinates and colour (red, green, yellow or blue). The red head and joints on the body of the snake are instances of this SnakeNode class. Below are screenshots that show the required snake with a red head and joints on its body when it starts and after it eats apples.
代做Data Structures作业、Software Technology作业代写、Java语言作业代写、Java编程作业调试
Problem 2.[2 marks] Problem 9.1, page 54 in Elements of Programming Interviews
a.[1.5 mark] Add your code to the MaxStack class given below to implement a stack that supports a max method, which returns the maximum value stored in the stack, and throws an exception if the stack is empty. Assume elements are comparable. All methods (push, pop, peek and max) must be O(1) time. If the stack contains n elements, you can use O(n) space, in addition to what is required for the elements themselves.
b.[0.5 mark] Add your code to the main method given below to test your implementation of this MaxStack class.
c.Submission: Copy your entire Java program to your Word file for submission.
import java.util.*;
public class MaxStackTest {
public static void main(String[] args) {
MaxStack<Integer> maxStack = new MaxStack<Integer>();
// Add your code here to test all methods of MaxStack class
}
}
class MaxStack<T extends Comparable<T>> {
// this class could use O(n) space in addition to what is required for
// the elements themselves.
// Y could be either T or class name of an additional class you design
LinkedList<Y> itemList = new LinkedList<Y>();
// add your code here if needed
void push(T item) {
// add your code here to insert item to itemList
// this method must be O(1) time complexity
}
T pop() {
// add your code here to remove the top item from itemList
// this method must be O(1) time complexity
// and throws an exception if the stack is empty
}
T peek() {
// add your code here to get the top item from itemList
// this method must be O(1) time complexity
// and throws an exception if the stack is empty
}
T max() {
// add your code here to get the maximum item in itemList
// this method must be O(1) time complexity
// and throws an exception if the stack is empty
}
}
// Add additional class here if you need
Problem 3.[2 marks] Problem 2.4, page 50 in Cracking the Coding Interview
a.[1.5 mark] You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Add your code to the add2LinkedLists method given below that adds the two numbers and returns the sum as a linked list.
EXAMPLE:
Input linked list X: 3 -> 1 -> 5, and linked list Y: 5 -> 9 -> 2.
Output linked list Z: 8 -> 0 -> 8
b.[0.5 mark] Add your code to the main method given below to test your implementation of the add2LinkedLists method. Use the program below
c.Submission: Copy your entire Java program to your Word file for submission.
import java.util.*;
public class Adding2LinkedListsTest {
public static void main(String[] args) {
// Add your code here to test Add2LinkedLists method
}
public static LinkedList<Integer> add2LinkedLists (LinkedList<Integer> llist1, LinkedList<Integer>llist2) {
// Add your code here to return the sum of 2 linked list. For example,
// llist1: 3 -> 1 -> 5 and llist2: 5 -> 9 -> 2. Return: 8 -> 0 -> 8
}
}
Problem 4.[2 marks] Solve the following problem on the Hacker Rank website: Team Formation (https://www.hackerrank.com/challenges/team-formation)
You are required to use Hashtable to solve this problem. Note: there are 20 test cases for this problem on the website.
Submission: Copy your entire Java program to your Word file for submission. Also add a note to show how many test cases your program could pass.
Problem (copied from the Hacker Rank website)
------------------------------
Hints will be given in lectures and tutorials.
Plagiarism and Extension: Please review the Unit Outlines that is available on Canvas site of this unit.
因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
微信：codinghelp