# Angel Nikolov BSC IT Programming in Jav

Topics: Quicksort, Sorting algorithm, Algorithm Pages: 15 (2965 words) Published: November 17, 2014
﻿Assignment Front Cover Sheet

PART 1 – To be completed by the student
Student Name
Angel Nikolov

Student ID Number
LON29101212

Module Name

Data Structures and Algorithms

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
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.

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
II+1

Pop() retrieves and element from the accessible end. Pseudo code: If I != 0
Ii-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 sizei
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/