Data Structures and Algorithms: Problem Solving and Analysis

This assignment solution addresses various concepts within Data Structures and Algorithms. It begins with an introduction to algorithms and data structures, followed by the analysis of greedy criteria and their limitations in activity selection. The solution then delves into the Ford-Fulkerson algorithm, illustrating its application through residual graphs and maximum flow computations. Further, it explores binary search trees, including their properties, best and worst-case scenarios, and motivations for their use. The assignment also examines binomial trees and deletion operations. Finally, it covers binary search in sorted arrays, dynamic programming, and the NP-completeness of the traveling salesman problem, offering detailed explanations and analysis of each concept.

DATA STRUCTURE AND ALGORITHMS
NAME :
REGISTRATION NUMBER :
UNIT CODE :
DATE OF SUBMISSION :

Introduction
Algorithms are set of rules that are used to solve different kind of problems. There are different
types of algorithms that can be applied on different problems and solve them e.g dynamic
programming and greedy algorithms. On the other hand data structure is a systematic way of
storing data for future use. The following shows and describe how some algorithms are used to
problems.

1.
a)
i. S = {f[1]}
k = 1
n = A.length
for i = 2 to n:
if s[i] ≥ f[i]:
S = S U {f[i]}
k = i
return t[i]
ii. S <{f[1]}
n > 1
n = A.length
for i = 2 to n:
if s[i] ≥ f[i]:
S = S U {f[i]}
k = i
return f[i]
iii.
main() {
int f[] = {n}

int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The interval with few conflicts will be as shown below :\n");
for(i = 0; i<n; i++) {
printf("f[%d] = %d \n", i, s[n]);
}
b).
i.
5/5
10
8/8
10 8
10
5
i. S-b-c-t
iii. S-b-c-t = 8+10+8=16
s
d
a
b c t

c). Maximum flow problem– is a flow that normal involves finding feasible
flows over solo sources (Berg,2008).
Given a graph G= (j∪s, E) where we are to find the largest set of jobs to be
scheduled
N = J∪S∪{J,S}, E' ), is constructed to find the values where by maximum value
of the two will be equal.

2.
a.
Binary search tree is collection of nodes that are arranged in way that satisfies the
tree properties in which values are added to it according to the following.
 The left sub nodes which are the child nodes have keys that are less
than the parent node.
 The right sub nodes (Child nodes) have keys that are greater than the
parent node.
b. Best case to search values e.g 9
2
5
6
7
9
1

5,2,6,1,7,9
Worst case
5
2 6
1 7
9
2
5
6
7
9
1

c.
d. The motivation for using the binary trees according to (Oostenveld,2011).
 Binary trees allow us to accomplish in algorithmic time rather than linear
time.
 They carry out large inserts and deletes in data structures without resorting
them.
 It is very easy to implement lock free data structure from binary tree than
any other type.
 They have high speed and are more efficient.
5
2 6
1 7
9

5
1
6
2 7
9

3.
a. F
b.
1
2 3
6

c. Binomial tree.
B1.
B2

B3
d. Dd
In deleting the minimum the following is used.
Function deleteMin(heap)
Min=heap.trees().firts()
For each current in heap.trees()
If current.rootV min.root then min=current
Temp.add(tree)
Merge(heap,temp)
The operations using o(log n)