Task – 01

a) Initialize the array such that is a free list only with all pointers correctly set. List A
and List B will be empty lists.(P1.1,D3.2)
b) Display all of the entries in List B in the intended sequence of the list.(P1.1,D3.2)
c) Add a new data item (held in a filed called NEWITEM) to List A. (reminder:
Ensure that you insert the data in alphabetic sequence of characters.)(P1.1, D2.4,
D3.2)
Data Structure

The data structure is a specific way of adding and organizing data in a system. Data structures
are used in mainly every program or software system.

Properties and methods

Data type

Primitive types

1. Boolean
2. Char
3. Float
4. Double
5. int
6. String
7. Enumerated type

Data Structures Algorithm | T.M.Shammika Dilshan 1

Composite types

1. Array
2. Record
3. Union
4. Tagged Union
5. Plain old data structure

Abstract data types

1. Container
2. Queue
3. Set
4. Stack
5. String
6. Graph
7. Hash
8. Vector
9. Linked List
10. List Itterator.

Data Structures Algorithm | T.M.Shammika Dilshan 2

Initializing the Array Display and add new data

import java.util.ArrayList;

import java.util.Collections;

public class SwapElementsOfArrayListExample {

public static void main(String[] args) {

//create an ArrayList object

ArrayList arrayList = new ArrayList();

//Add elements to Arraylist

arrayList.add("A");

arrayList.add("B");

arrayList.add("C");

System.out.println("Before swaping, ArrayList contains : " + arrayList);

/*

To swap elements of Java ArrayList use,

static void swap(List list, int firstElement, int secondElement)

method of Collections class. Where firstElement is the index of first

element to be swapped and secondElement is the index of the second element

to be swapped.

If the specified positions are equal, list remains unchanged.

Data Structures Algorithm | T.M.Shammika Dilshan 3

 Please note that, this method can throw IndexOutOfBoundsException if

any of the index values is not in range.

*/

Collections.swap(arrayList,0,4);

System.out.println("After swaping, ArrayList contains : " + arrayList);

/*

Output would be

Before swaping, ArrayList contains : [A, B, C]

*/

Data Structures Algorithm | T.M.Shammika Dilshan 4

Task – 02

a) Implement this scenario using linked list data structure. Display the candidate code,
IQ score & English test marks of the candidates who have been selected for the
interview. Display the no of candidates who have received reject letters. Assume
that the no of candidates are taken at runtime.(P2.1,D2.2)
b) Exceptions should be handled appropriately throughout the implementation.
(P2.2,D2.4)
c) Prepare a test plan report for the above scenario. (P2.3,D1.2)
d)

(a). Linked List data structure code

import java.util.*;

Class Candidates

public static void main(String args[])

LinkedList CandidateDetails = new LinkedList();

CandidateDetails.addFirst("Number: EM00219 Name: Anojan candidate number: EM012369 IQ

Marks:45 English Marks:78");

CandidateDetails.add("Number: EM00911 Name: Terryl candidate number: EM012965 IQ

Marks:55 English Marks:88");

Data Structures Algorithm | T.M.Shammika Dilshan 5

CandidateDetails.add("Number: EM00912 Name: Sarangan candidate
number: EM012985 IQ Marks:48 English Marks:68");

CandidateDetails.add("Number: EM00913 Name: Castro candidate number: EM012645 IQ

Marks:45 English Marks:79");

CandidateDetails.add("Number: EM00914 Name: Billgates candidate number: EM012161 IQ

Marks:55 English Marks:58");

CandidateDetails.add("Number: EM00915 Name: Steve jobbs candidate number: EM010965 IQ

Marks:65 English Marks:88");

CandidateDetails.add("Number: EM00916 Name: A.R Rahman candidate number: EM012065

IQ Marks:55 English Marks:98");

CandidateDetails.add("Number: EM00917 Name: Mark candidate number: EM012210 IQ

Marks:55 English Marks:48");

CandidateDetails.add("Number: EM00918 Name: Donglee candidate number: EM012565 IQ

Marks:65 English Marks:58");

CandidateDetails.add("Number: EM00919 Name: Plato candidate number: EM012594 IQ

Marks:55 English Marks:68");

CandidateDetails.add("Number: EM00920 Name: Kevin candidate number: EM012690 IQ

Marks:65 English Marks:48");

ListIterator li = CandidateDetails. listIterator(0);

while(li.hasNext())

System.out.println(li.next());

Data Structures Algorithm | T.M.Shammika Dilshan 6

}

(b) Handled Java Exceptions

Checked exceptions: A checked exception is an exception, which is generally a user error or a

problem that cannot be foreseen by the programmer. For example, if a file is to be opened, but
the file cannot be found, an exception occurs. These exceptions cannot simply be ignored at the
time of compilation.

Runtime exceptions: A runtime exception is an exception that occurs that probably could have
been avoided by the programmer. As opposed to checked exceptions, runtime exceptions are
ignored at the time of compilation.

Errors: These are not exceptions at all, but problems that arise beyond the control of the user or
the programmer. Errors are typically ignored in your code because you can rarely do anything
about an error. For instance, if a stack overflow occurs, an error will arise. They are also ignored
at the time of compilation.

(c)Test Plan Report

Figure 2.1

Data Structures Algorithm | T.M.Shammika Dilshan 7

Task – 03
a) Write a suitable sorting algorithm that you can use in this scenario. (P1.2)
b) Compare the performance of compare & exchange type of some sorting algorithms
& divide & conquer type of sorting algorithms.(P1.2, M3.3)
c) Suggest & justify a more efficient searching algorithm that you can use in this
system. (P1.2, M1.1, D1.2)
d) Describe some situations when recursive algorithms can be used in data structures.
(P1.3)

(a) Bubble sort

I have chosen bubble sort to use according to its scenario, and additionally the inventory control
system for KidsLanka (pvt) Ltd to manage the operations

void bubbleSort(int ar[])

{
for (int i = (ar.length - 1); i >= 0; i--)
{
for (int j = 1; j ≤ i; j++)
{
if (ar[j-1] > ar[j])
{
int temp = ar[j-1];
ar[j-1] = ar[j];
ar[j] = temp;
}}}}

Data Structures Algorithm | T.M.Shammika Dilshan 8

(b) Comparison sort
A comparison sort is a type of sorting algorithm, which only reads the elements via a single
abstract comparison operation which decides which of two elements must occur first in the final
sorted list. The only requirement is that the operator obeys two of the options of a total order.

For Instance:

if a ≤ b and b ≤ c then a ≤ c (transitivity)

for all a and b, either a ≤ b or b ≤ a (totalness or trichotomy).

Divide and conquer algorithms

Divide and conquer (D&C) is an imperative algorithm design paradigm based on multi-branched
recursion. A divide and conquer algorithm works by recursively breaking down a issue into two
or more sub-problems of the same or similar type, until these become simple enough to be
covered directly. The solutions to the sub-problems are then combined to give a solution to the
real problem.

This tactic is the basis of efficient algorithms for all sort of issues, such as sorting (e.g.,
quicksort, merge sort), multiplying large numbers (e.g. Karatsuba), syntactic analysis (e.g., top-
down parsers), and computing the discrete Fourier transform (FFTs).

On the other hand, the ability to realize and design D&C algorithms is a skill that takes time to
master. As when proving a theorem by induction, it is often necessary to replace the original
problem by a more general or complicated issue in order to initialize the recursion, and there is
no systematic method for finding the proper generalization.

These D&C complications are seen when optimizing the calculation of a Fibonacci number with
efficient double recursion.

The correctness of a divide and conquer algorithm is usually proved by mathematical induction,
and its computational cost is often determined by solving recurrence relations.

Data Structures Algorithm | T.M.Shammika Dilshan 9

(c). Dynamic Programming Algorithms
I like to suggest to Dynamic Programming as an Algorithm that can be used in this system,
Dynamic programming algorithms are used for optimization. A dynamic programming algorithm
will examine all possible ways to solve the errors or problems and it will pick the best solution
for the problem easily.

Therefore, We can roughly think of dynamic programming as an intelligent, brute force method
which enables us to go via all possible solutions to pick the best one. A dynamic programming
algorithm will look into the whole traffic report, focusing into all possible combinations of roads
you might take, and will only then tell you what route is the rapidest. Certainly, you might have
to wait for a while till the algorithm finishes.

(d) Recursive functions

What is recursion? Sometimes a problem is too difficult or too complex to solve because it is too
big. If the problem can be broken down into smaller versions of itself, we may be able to find a
way to solve one of these smaller versions and then be able to build up to a solution to the entire
problem. This is the idea behind recursion; recursive algorithms break down a problem into
smaller pieces which you either already know the answer to, or can solve by applying the same
algorithm to each piece, and then combining the results.

Stated more concisely, a recursive definition is defined in terms of itself. Recursion is a computer
programming technique involving the use of a procedure, subroutine, function, or algorithm that
calls itself in a step having a termination condition so that successive repetitions are processed up
to the critical step where the condition is met at which time the rest of each repetition is
processed from the last one called to the first.

Recursion turns out to be a wonderful technique for dealing with many interesting problems.
Solutions written recursively are often simple. Recursive solutions are also often much easier to
conceive of and code than their iterative counterparts.

Many mathematical functions can be defined recursively:

Factorial
Fibonacci

Data Structures Algorithm | T.M.Shammika Dilshan 10

Euclid's GCD (greatest common denominator)
Fourier Transform.

Many problems can be solved recursively, for instance, games of all types from simple ones like
the Towers of Hanoi problem to complex ones like chess. In games, the recursive solutions are
particularly convenient because, having solved the problem by a series of recursive call,

You want to find out how you got to the solution. By keeping track of the move chosen at any
point, the program call stack does this housekeeping for you! This is explained in more detail
later.

Why use recursive functions

Given that recursion is in general less efficient, why would we use it? There are two situations
where recursion is the best solution:

The problem is much more clearly solved using recursion: there are many problems where the
recursive solution is clearer, cleaner, and much more understandable. As long as the efficiency is
not the primary concern, or if the efficiencies of the various solutions are comparable, then you
should use the recursive solution.
Some problems are much easier to solve through recursion: there are some problems which do
not have an easy iterative solution. Here you should use recursion.

Data Structures Algorithm | T.M.Shammika Dilshan 11

Task – 04
a) What types of string operations are used when searching information? (P3.1)
b) Elaborate how it can be implemented using a simple pattern matching Algorithm?
(P3.2, D1.2, D3.2)
c) Describe few application areas where these can be used? (P3.1, D3.6)

(a) Most of the time, query strings are used while you search any information through
Google, Unicode characters are mixed with query strings
The maximum length of a query string is 2000 characters. Entire query strings consist of at least
one field value. It is suggested to write field values in lower case. Due to searches on atom, text,
and HTML fields are case insensitive, and a query string can also consists the Boolean operators
AND, OR, and NOT, which are recognized by writing them in upper case.

A query string must take many forms. It has two main ways to construct a query: with and
without field names. A global search uses a query string that consists of only field values.

This document illustrates how to construct query strings for global and field searches, and how
the search logic works in each case.

1. Global Search
 One- value queries
 Multi- value queries
 Boolean Operators
 Stemming
 Tokenization

Data Structures Algorithm | T.M.Shammika Dilshan 12

 2. Field Search
 Queries on atom fields
 Queries on text and HTML fields
 Queries on number fields
 Queries on date fields
 Queries on geo point fields
 Queries on multiple fields

3. Mixing global and field searches.

Global Search
Global search provides the ability to surf for documents by specifying values that might appear
in any document field.

To perform a global search you will require writing a query string that consists of one or more
field values. The search algorithms recognize the type of each value and searches entire
document fields that could contain that value.

One – Value queries

Brevity is the soul of wit, and a global search with one value is the epitome of brevity. A search
with a query string that consists of a single value that is managed according to below rules:

If the query string is a word (“red”) or a quoted string (“\” red rose \””), search retrieves entire
documents in an index that have:

 A text or HTML field that consists of that word or quoted string.

 An atom field with a value that links the word or quoted string.

Data Structures Algorithm | T.M.Shammika Dilshan 13

If the query string is a number ("3.14159"), search retrieves all documents
that have:

 a number field with a value equivalent to the number in the query (a number field with
the value 5 will match the query "5" and "5.0")
 a text or HTML field that contains a token that matches the number as it appears in the
query (the text field "he took 5 minutes" will match the query "5" but not "5.0")
 an atom field that literally matches the number as it appears in the query

If the query string is a date in yyyy-mm-dd form, search retrieves all documents that have:

 a date field whose value equals that date (leading zeros in the query string are optional,
"2012-07-04" and "2012-7-4" are the same date)
 a text or HTML field that contains a token that literally matches the date as it appears in
the query
 an atom field that literally matches the date as it appears in the query

Data Structures Algorithm | T.M.Shammika Dilshan 14

(b) Queries on Multiple fields

Query String Comments

"product=piano manufacturer=steinway" These queries retrieve all Steinway pianos. The
"product=piano AND manufacturer=steinway" space between the terms implies a logical
AND; the second form makes this explicit.
"product=piano AND NOT Retrieves all non-Steinway pianos.
manufacturer=steinway"
"product=piano AND price<2000" This query retrieves inexpensive pianos.

Mixing global and field searches

Query String Comments

"keyboard great price<5000" Retrieves documents where the words "great"
"keyboard AND great AND price<5000" and "keyboard" appear in any text, HTML, or
atom fields, and there is a price field less than
500. The AND is implied, the second form is
equivalent.
"keyboard OR product=piano" Retrieves documents with a product field that
contains piano, or documents with any text,
HTML, or atom field that contains keyboard.

(c). SERP used in Applications

Data Structures Algorithm | T.M.Shammika Dilshan 15

Figure 4.1

The above pictures show about an android application, where almost java programming language
was used to code. The above application is based on search engine results page, where I can use
this application to describe for this task.

Data Structures Algorithm | T.M.Shammika Dilshan 16

SERP used in an Android application

Figure 4.2

The above screenshot describes about a similar application as shown in the previous description,
which is another example for SERP used application.

Data Structures Algorithm | T.M.Shammika Dilshan 17

 Conclusion

This assignment report provides the reader considerable knowledge on data structures and
algorithms in different organization. It will help understand how Data structures and algorithms
will help in organizations, the requirements to set up their own programs its advantages and
disadvantages and its effects on productivity. I believe that the documented information will be
most helpful to those people or organizations who are considering creating a program for their
organizations.

Data Structures Algorithm | T.M.Shammika Dilshan 18

 Critical Appraisal

My knowledge on the subject was extremely limited before I started working on this assignment
report that you have just read. However, as I progressed past each task, the knowledge I gained
was simply immeasurable. I am confident that my knowledge on the subjects in this assignment
is much greater than it was before I started.

The section where the report was the one section that I answered fairly easily and the task on
writing the pseudo code was the section that I spent the most time on when it came to compiling
an answer. The time I spent answering the questions on the program and the languages that are
used in the development of these sites significantly helped improve my knowledge about them.

I sincerely do hope that this assignment will provide its every reader with as much knowledge as
I received when I compiled this assignment.

Data Structures Algorithm | T.M.Shammika Dilshan 19

 Gantt Chart

Data Structures Algorithm | T.M.Shammika Dilshan 20

 References

https://www.youtube.com/watch?v=CfSFyizmxp4

http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

http://www.java2s.com/Tutorial/Java/0140__Collections/Copyingelementsoutofalistintoanarray.h
tm

https://play.google.com/store/apps/details?id=pl.droidsonroids.seoserp.paid

https://play.google.com/store/apps/details?id=com.SERPmojo

Data Structures Algorithm | T.M.Shammika Dilshan 21