Data Structures & Algorithms Southwest University China

Assignment for Week 2 2016

Write your answers for this assignment on this sheet and submit your answers at the beginning of the Monday morning class. You may work with a partner. If so, you should write your partner’s name above. Your mark for this assignment will not count towards your final grade, but there will be a test later in the course comprising questions taken from the weekly assignments.

If you have any questions or need any help with the assignment, please ask Prof Rachel or the teaching assistants. Prof Rachel will be available in office 1303 Monday & Wednesday (10.30-11.30) Thursday & Friday (12.30-2.30).

Linked Lists

1)List three points of difference between an array and a linked list.

2)Let Link be an object with two member variables:

public class Link {

char value;

Link next;

}

Assume that first is a reference to a Link object containing 'a',

whose successor is a link object containing 'b', whose successor is null.

Which of the following code snippets successfully reverses this structure as follows?

Explain your answers by drawing a picture of the result of each code snippet or giving a brief summary in words.

(Hint: Take care, this question is not the same as the one done in class)

a)

first.next = null;

first.next.next = first;

first = first.next;

b)

first.next.next = first;

first = first.next;

first.next = null;

This one

c)

Link temp = first;

first = temp.next;

first.next = temp;

temp = null;

d)

Link temp = first.next;

temp.next = first;

first.next = null;

first = temp;

3)For the tree shown abovestate:

  1. Which node is the root?
  1. Which nodes are leaves?
  1. What is the tree’s height ?
  1. List the sequence of nodes visited by traversing the tree using

i)preorder

ii)postorder

iii)inorder

iv)level order

4)Show the result of inserting 3, 1, 4, 2, 8, 5, 9, 7 in an initially empty binary search tree.

5)Showthe result of deleting the root of the tree you constructed for Q4.

6)Show the result of deleting node 8 from the tree you constructed for Q5.

7)Explain the steps of the QuickSort alogorithm using the following list: {42,99,66,22,15,53}. State clearly any assumptions you make.

Challenge (optional extension question for keen students)

[Weiss 8.21] An array contains N numbers, and you want to determine whether two of the numbers sum to a given number K. For instance, if the input is 8, 4, 1, 6 and K is 10, the answer is yes (4 and 6). A number may be used twice. Do the following.

  1. Give an O(N2) algorithm to solve this problem.
  1. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the

items first. After doing so, you can solve the problem in linear time.)

  1. Write Java code for both solutions and compare the running times of your algorithms.