DATA STRUCTURE ASSIGNMENT QUESTION SOLVED!

QUESTION 1

 a. Given N elements in an array A, sorted in non decreasing order. Write an algorithm to

Determine whether a given element X is present in the list. If X exists, determine a value

Such that A=X. If X is not in the list then J is to be set to zero.

b. Define the following terms in relation to directed graph.

i) Source

ii)Sink

ANSWERS

1. Algorithm to determine if X is present in the sorted array A:

1. Initialize two pointers, low and high, to the first and last indices of the array A, respectively.

2. Calculate the midpoint, mid, of the range [low, high].

3. Compare the element at A[mid] with X.

4. If A[mid] == X, set J to mid and return true.

5. If A[mid] < X, update low to mid + 1 and repeat steps 2-5.

6. If A[mid] > X, update high to mid – 1 and repeat steps 2-5.

7. If the search range is empty (low > high), set J to 0 and return false.

Definitions in relation to directed graphs:

1. Source: A node with no incoming edges, only outgoing edges. It is a starting point for graph traversal or flow.
2. Sink: A node with no outgoing edges, only incoming edges. It is an ending point for graph traversal or flow.

QUESTION 2

ANSWERS

2a.  Table for database for ACAD

2b. Table for database reg number = 10/6766 (SPORTS)

2c. Table for reg numb (ACAD) & Reg numb (SPORTS)

2d. Table for Full outer join for the ACAD and SPORTS relation

QUESTION 3

a) Name the fields contained in the relation

b) ldentify the primary key in the relation

c) ldentify a suitable data types for each of the fields contained in the relation (7mrks)

d) State the cardinality and the degree of the above relation

ANSWERS

3a. Based on the data provided in question (6a), The names of the fields in the relation are:

I. S/N (Serial Number)

II. Item

III. Stock code

IV. Size (cm)

V. Manufacturer

VI. Date purchased

VI. Plastic? (a boolean field indicating whether the item is made of plastic or not)

3b. The primary key element of the relation is:

– S/N (Serial Number): The Serial Number (S/N) is unique for each item.

3c. The suitable data types for each field are:

I. S/N (Serial Number): Integer (or Auto-Incrementing Integer)

II. Item: String (or Text)

III. Stock code: String (or Text)

IV. Size (cm): Decimal (or Float)

V. Manufacturer: String (or Text)

VI. Date purchased: Date (or DateTime)

VII. Plastic?: Boolean (or Bit)

3d. The cardinality of the relation is 3. (since there are 3 tuple or rows in the relation)

The degree of the relation is 7. (since there are 7 attributes or fields in the relation: S/N, Item, Stock code, Size (cm), Manufacturer, Date purchased, and Plastic?) 

QUESTION 4

4a. What is algorithm?

4b. List any four (4) characteristics of algorithm

4c. List and briefly explain the five areas involved in the study of algorithm

ANSWERS

4a. Definition: – An algorithm is a Step By Step process to solve a problem, where each step

indicates an intermediate task. Algorithm contains finite number of steps that leads to the

solution of the problem.

4b. Properties /Characteristics of an Algorithm:-

Algorithm has the following basic properties

I. Input-Output:- Algorithm takes ‘0’ or more input and produces the required output.

This is the basic characteristic of an algorithm.

II. Finiteness:- An algorithm must terminate in countable number of steps.

III. Definiteness: Each step of an algorithm must be stated clearly and unambiguously.

IV. Effectiveness: Each and every step in an algorithm can be converted in to

programming language statement.

V. Generality: Algorithm is generalized one. It works on all set of inputs and provides

the required output. In other words it is not restricted to a single input value.

4c. Five (5) areas involved in the study of Algorithm:

I. Design: This involves creating a plan or blueprint for solving a problem or achieving a specific goal. It includes identifying the problem, defining the inputs and outputs, and developing a step-by-step procedure for solving the problem.

II. Analysis: This area focuses on understanding the behavior and performance of algorithms, including their time and space complexity, scalability, and trade-offs. It involves mathematical proofs and empirical studies to evaluate algorithm efficiency.

III. Implementation: This area deals with translating an algorithm design into a working program or code, using a programming language and considering issues like data structures, programming paradigms, and software engineering principles.

IV. Verification: This area ensures that an algorithm produces correct results and meets the desired specifications. It involves testing, debugging, and validating the algorithm against different inputs and scenarios.

V. Optimization: This area aims to improve the performance, efficiency, or effectiveness of an algorithm, often by reducing time or space complexity, improving scalability, or enhancing accuracy. It may involve refining the algorithm design, using more efficient data structures, or applying parallel processing techniques.