Data Structures and Algorithms: Assignment 1

Question 1) Linked List and Snake Game (60%)

The purpose of this question is to create an application to check whether an input word or phrase is  a palindrome. A palindrome is a word, phrase, number, or sequence of words that reads the same     backward as forward. Additionally, the application also checks whether the given quadratic functions (y = (x + m)2 + n) are symmetrical in the given range.

Part 1 (36%)

Node Class (5%)

Create a Node Class which has data and linker parts to store any type of data and node can be linked to each other together by its linker named “next” .

Node class has a generic object. The generic object points to any types of data (the data type may be String, Integer, Float or Character).

Node Class has a node object named “ next” which points to another node.

Node Class has an “equals” method. “equals” method takes a Node object in and returns true if the argument (node)’s data equals to this node’s data. Otherwise, it returns false.

Node Class has an “compareTo” method. “compareTo” method takes a Node object in and returns   an int 0 if the argument node’s data equals to this node’s data; an int value less than 0 returns if this node’s data is numerically less than the argument node’s data or this node’s data is alphabetically    less than the argument node’s data. Otherwise, it returns an int value greater than 0.

LinkedList Class (15%)

Create a LinkedList Class which builds and manages a linked list. Extra 10 marks will be given if no loops are used.

LinkedList Class has a Node object named “ head” to point to the head of a linked list.

LinkedList Class has an int variable named “size” to store the size of a linked list (number of nodes).

LinkedList Class has an “add” method. It takes a generic object to create a node and add to the end of a linked list

LinkedList Class has an “addInOrder” method. It takes a generic object to create a node and add to a linked list following the ascending numerical order if the generic object is a number. It follows            alphabetical order if the generic object is a char or String.

LinkedList Class has a “contains” method. It takes a node and returns true if the linked list contains this node. Otherwise, it returns false.

LinkedList Class has a “remove” method. It takes a node as an argument and remove a node which has the same data as the argument node from the linked list.

LinkedList Class has a “removeFromHead” method. It removes the first node from the linked list. LinkdedList Class has a “removeFromTail” method. It removes the last node from the linked list.

LinkedList Class has a “printLinkedList”method. It prints all the contains of the linked list to the console.

Queue Class (5%)

Queue class manages a linked list as a queue.

Queue class has an “enqueue” method. It takes a generic object and enqueues the object to a

queue.

Queue class has a “dequeue” method. It dequeues and returns the node from a queue.       Queue class has a “printQueue” method. It prints the contains of the queue to the console.

Stack Class (5%)

Stack class manager a linked list as a stack.

Stack class has an “ push” method. It takes a generic object and push the object to a stack. Stack class has a “pop” method. It pops and returns the node from a stack.

Stack class has a “printStack” method. It prints the contains of the stack to the console.

DataAnalysis Class (6%)

DataAnalysis class checks whether a list of data is symmetrical (you can use Queue and Stack Classes).

DataAnalysis class has an “isSymmetrical” method. It returns true if a list of data is symmetrical (data0 == datan  data1 == datan- 1  data2 == datan-2 etc.)

You can add more fields or methods if you need for part 1.

Part 2 (24%)

Snake

Using the LinkedList you had before to build a snake game.

•    Randomly generate 10 numbers and 1 letter. The range of the number is from 0 to 9 inclusive.

•    Randomly set location of these 10 numbers and the letter.

•    Snake’s length is increased by 1 when it eats a letter.

•    A new letter generated and allocated randomly after eating a letter.

•    Snake’s body shows the letters it has eaten. These letters need to be stored in a linked list and in alphabet order.

Example:

Snake : @ABD

After eating C

Snake: @ABCD

•    Snake drops the length of its body by one when it hits a number. The number’s value        determines which node of the linked list needs to be dropped. If the value is greater than the snake’s length, the last node will be dropped.

Example:

Snake: @ABCDEFFG

After hitting 3

Snake: @ABDEFFG

After hitting 1

Snake: @BDEFFG

After hitting 9

Snake: @BDEFF

•    Game stops when the length of snake is 0.

•    Design YOUR OWN GUI

You may have a look the console-based prototype.