M180 Java Data Structures

Question 1

Write the Java code of the method IdentitiyMatrix that takes one 2-dimentional square array (matrix) A and returns true if the matrix is an identity matrix and false if it is not. For example, if A is as follows:

Return true:

Return false:

Hint: In linear algebra, the identity matrix of size n is the n x n square matrix with ones on the main diagonal and zeros elsewhere

Question 2

You are given a Node class and a List class:

public class Node
{
int data;
Node next;
}
public class List
{
Node first;
}

You are also given a Stack class. The following functions are available for use:

public class Stack {
public boolean isEmpty(){};
public void push(int n){};
public int pop(){};}

Write a Java method listToStck that pushes the positive data found in a linked list t in reverse order into the stack s, such that the last positive data in the list will be pushed into the stack s.

Example: if s and t are as follows: see image.

then s will be: see image.

Question 3

Write a java method isPal that takes string s to check if a string is palindrome string using recursion and returns true if it is palindrome and false otherwise.

A string is said to be palindrome if reverse of the string is same as string. For example, "abba" is palindrome, but abbc is not palindrome.

Example:

If s=”madam” then it returns true
If s=”sir” then it returns false

Question 4

For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation. Consider that we always have n>m.