# Angel Nikolov BSC IT Programming in Jav

PART 1 – To be completed by the student

Student Name

Angel Nikolov

Student ID Number

LON29101212

Module Name

(e.g.: Business Environment)

Data Structures and Algorithms

Course (e.g. HND Business )

BSC in IT

Assignment Title

Implementing Data Structures and Algorithms

Module Lecturer

Rafiqul Islam

Number of Words

2966

Assignment Due Date

06/05/2014

Submission Date

05/05/2014

First submission

Resubmission (as per lecturer’s instruction)

PART 2 – Student declaration

By submitting this work to LSBM, I confirm that I have read and understood the Dishonesty and Plagiarism Policy that is applicable to all assessments and assignments submitted by me.

I also confirm further that the work submitted here is my own work, save for where indicated by proper referencing. Should I not abide by the policy and be found guilty of plagiarism by my course lecturer or any other LSBM or appointed staff member I shall be bound by the decision of that lecturer and/or staff member as well as the terms of the Dishonesty and Plagiarism Policy.

Contents

Introduction1

Task 11

Task 2Heap sort8

Task 3 String operations10

Conclusion12

Bibliography12

Introduction

The good knowledge of data structures is absolute must for anyone involved in computer science. The data structures are part of any software system nowadays.

This report highlights three important aspects of the data structure algorithms. Sorting is the way of arranging the data elements in a way suitable for posterior handling. The searching is a process repeated thousands of times per hour and its optimizing by suitable algorithm can reduce the process times many times. And finally the metrics necessary for judging speed of other factors to compare algorithms. Different algorithms will be compared through their output in three cases, worst case, average case and best cases.

In task three will be given overview of Java features for manipulating Strings and will be shown in practice some of the characteristics.

Task 1

1.1 Stack and Queue.

A stack is a linear data structure which takes elements and can extract from only one end of it. The data handling is called LIFO – last in first out. A stack is very useful when data need to be stored and retrieved in reverse order. The different compilers keep the function executed in a stack structure, The back button of every browser and undo buttons are stack structures as well.

The valid operations on a stack structure are:

Push() put an element at the accessible end. Pseudo code:

The index “I” points to the first available position in the stack and Capacity is the maximum elements it can occupy. StackArray[i] dataElement

II+1

Pop() retrieves and element from the accessible end. Pseudo code: If I != 0

Ii-1

dataElement StackArray[i]

return dataElement

Top() extract the value of the top element of the stack without removing it. If I != 0 then

dataElement StackArray [i-1] // explain //

return dataElement

Size() returns the size of the stack:

Int sizei

Return size

IsEmpty() – checks if the stack is empty

If i==0 then return true

Else return false

A Queue is a data structure that accepts elements at one end and allows retrieval from the other end. The access has FIFO principle.

The Queue has a Front Index keeping the index of the last insertion, Rear index that keeps track of the position for inserting the next element and Capacity of the queue. The indexes grow in a circular motion. At the beginning, in an empty queue f=r

Possible operations:

isEmpty() – if the queue is empty:

if f=r then true

size() – check the number of occupied elements:

size (N-f+r) mod N

return size

Enqueue(dataElement). // add an element to the queue: // If size() = N-1 then break;

Else Q[r]dataElement

Dequeue() –...

Bibliography: Cay S. Horstmann, G. C., 2013. Core Java Volume I - Fundamentals. 9th ed. Boston: Prentice Hall Inc..

Drozdek, A., 2010. Data Structures and algorithms. 2nd ed. Boston: Course Technology.

Keil, D. M., 2014. Data Structures. [Online]

Available at: http://www.framingham.edu/~dkeil/ds-matls.htm

McQuain, 2006. Data structure and OO Development I. [Online]

Available at: http://courses.cs.vt.edu/cs2604/SummerI_2006/

Morin, P., 2011. Open data structures (in Java). 2nd ed. Chicago: Apress.

Reid-Miller, D. M., 2010. Introduction to data structures Fall 2010. [Online]

Available at: http://www.cs.cmu.edu/~mrmiller/15-121/

Please join StudyMode to read the full document