Data structures and algorithms PDF

Preview

Summary

THIS INCLUDES THE ANSWERS TO TMA1 ASSIGNMENT...

Description

Q1. Algorithm Analysis 1.1

Algorithm is a finite set of unambiguous instructions, which specify a finite sequence of operations that provides the solution to a problem to accomplish a particular task. In addition an algorithm must satisfy the following criteria.  Should have zero or more Input  Should produce at least one Output  Each instruction is clear and unambiguous – Definiteness  For all cases, the algorithm should terminate after a finite number of steps Finiteness.  Should be Effective and feasible Hence, algorithm is independent from any programming languages. In addition, an algorithm can be represented through the use of flowcharts or pseudo code.

1.2

It is the main fact which will based on a solution about how fast or slow and how much of accuracy it may perform. It can be calculated by a mathematical function and as well as there are three features to be discussed when measuring the complexity in problem solving in computing such a Storage requirements, accuracy and time taken. When we consider about the time and space complexity, it depends on the resources which they are having such as Operating system, processor speed and hardware resources. The accuracy depends on the variables it uses such as in mathematical computations the “int” will give a rounded real number where as the “float” will give a decimal number.

1.3 1.3.1

Complexity classes P class P is the class which basically includes all deterministic algorithms that can be solvable in polynomial time, i.e. these problems can be solved in time O(nk) in worst-case, where k is constant. Ex: Adding numbers Multiplying a range of numbers

1.3.2

NP class NP is the class which identifies of those problems that are easy to verify but hard to solve. They are non deterministic and can be verifiable in polynomial time. NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. Every problem in this class can be solved in exponential time using exhaustive search. Ex: Jigsaw puzzle Prime factorization Sudoku Chess

1.3.3

NP Complete If a problem in NP which is taking exponential time can be reducible to a polynomial time, then it is known as NP Complete. Ex: Boolean satisfiability problem (SAT) Hamiltonian path problem

1.3.4

NP Hard There are situations where you can solve a problem by reducing it to a different problem such that if a problem B reduces to Problem A where, if given a solution to Problem A, then it can construct a solution to Problem B within polynomial time. Such problems are known as NP Hard. Ex: Subset sum problem Travelling salesman problem

1.4 a) Preparing a cup of tea BEGIN GET a cup GET teabag GET milk GET sugar GET the kettle #assumed it as an electric kettle Fill the kettle with water Boil the water Put the teabag into the cup Wait 3 minutes #assumed that the water will boil within three minutes Pour boiled water to the cup Wait 30 seconds Remove the tea bag IF likes milk THEN Put milk ENDIF IF likes sugar THEN Put the desired amount of sugar ENDIF Stir well END

b) Calling a busy friend BEGIN SET attempts to one

# attempts is a integer variable used to store the no of times dialed

SET answered to NO

# answered is a Boolean variable used to indicate whether the friend answered or no

Get the telephone WHILE attemptslink = head head = p

x goes to the middle or end. (This pseudo code assumes the list is ordered.). Use two pointers: current and previous Begin p->info = x current = head WHILE current is not null and current->info < x previous = current current = current->link IF current is head p->link = head head = p ELSE previous->link = p p->link = current ENDIF DO END

(b) Inserting a new node into a doubly linked list

Adding a Node to the beginning newNode->NEXT = HEAD->FIRST HEAD->FIRST->PREV = newNode HEAD->FIRST = newNode newNode->PREV = NULL increment(HEAD->LENGTH)

Adding a node in the middle newNode->PREV = curPtr newNode->NEXT = curPtr->NEXT newNode->NEXT->PREV = newNode curPtr->NEXT = newNode increment(HEAD->LENGTH)

(c) Removing a node from a singly linked list current = head WHILE current is not null and current->info is not x previous = current current = current->link IF current is not null IF current points to the first node head = current->link IF current does not point to the first node previous->link = current->link destroy the current node (d) Removing a node from a doubly linked list

Deleting first node HEAD->FIRST = HEAD->FIRST->NEXT NODE-2->PREV = NULL decrement(HEAD->LENGTH) Deleting a node in the middle curPtr->PREV->NEXT = curPtr->NEXT curPtr->NEXT->PREV = curPtr->PREV decrement(HEAD->LENGTH) Deleting the last node curPtr->PREV->NEXT = NULL decrement(HEAD->LENGTH)

(e) Searching for an item in a doubly linked list WHILE current node is not null: IF currentData = currentNode.data THEN DISPLAY “Data Found” STOP ELSE currentNode = currentNode.next ENDIF DO...