+254 704 052992

FAHDA_IT245

Annual Report

FY [Year]

[Add a quote here from one of your company executives or use this space for a brief summary of the document content.]

Data Structure

IT245

Instructions:

You must submit two separate copies (one Word file and one PDF file) using the Assignment Template on Blackboard via the allocated folder. These files must not be in compressed format.

It is your responsibility to check and make sure that you have uploaded both the correct files.

Zero mark will be given if you try to bypass the SafeAssign (e.g. misspell words, remove spaces between words, hide characters, use different character sets, convert text into image or languages other than English or any kind of manipulation).

Email submission will not be accepted.

You are advised to make your work clear and well-presented. This includes filling your information on the cover page.

You must use this template, failing which will result in zero mark.

You MUST show all your work, and text must not be converted into an image, unless specified otherwise by the question.

Late submission will result in ZERO mark.

The work should be your own, copying from students or other resources will result in ZERO mark.

  • Use Times New Roman font for all your answers.

Name: ###

CRN: ###

ID: ###

Learning Outcome(s): LO1: Describe basic and advanced data structures such as linked lists, stacks, and queues.

2 Marks

Question One

Discuss the differences between the following:

  • ArrayList and LinkedList. (1 mark)
  • Stack and Queue. (1 mark)

Criterion

ArrayList

LinkedList

Definition

Time Complexity (Big-O)for Insertion, Deletion, Retrieving and Checking a specific element

Criterion

Stack

Queue

Definition

Time Complexity (Big-O)for Insertion, Deletion, Retrieving and Checking Emptiness

Learning Outcome(s): LO3: Calculate and analyze the complexity of small to medium programs built with basic data structures.

3 Marks

Question Two

Compute the running time (Big-O) and provide an analysis of the following:

Code Snippet

Answer

x = 7000 + (2 * 3000);

for(int i = 0; i < n; i++)

System.out.print(x);

x = 100 – 50;

for(int c = 0; c < n; c++)

System.out.print(x);

for(int d = 0; d < n; d++)

for(int e = 0; e < n; e++)

System.out.print(e + c);

for(int a = 0; a < y; a++)

System.out.print(i);

for(int b = 0; b < z; b++)

System.out.print(i);

for(int i = 0; i < n; i++)

for(int j = 0; j < n; i++)

for(int k = 0; k < n; j/3)

System.out.print(i – j);

3 Marks

Learning Outcome(s): LO1: Describe basic and advanced data structures such as linked lists, stacks, and queues.

Question Three

Convert the following arithmetic expression into Postfix form by Showing illustrations that depict both stack and output for each step.

a b / c + (d + e * f)

admin