NotesNeo

Unit 1: Introduction to Data Structures and Algorithms

Syllabus:
Introduction: Basic Terminologies: Concept of Data Structure, Choice of right Data Structure,
Algorithms, how to design and develop algorithms, Complexity of algorithm.
Operations: insertion, deletion, traversal etc.; Analysis of an Algorithm.
Searching: Linear Search and Binary Search Techniques and their complexity analysis.

Topic 1: Basic Terminologies

1.1 Concept of Data Structure

●​ Definition: A data structure is a way of organizing and storing data to perform operations
efficiently. It defines the relationship between the data and the operations that can be
performed on the data. Data structures play a crucial role in computer science and are used
to manage and organise large amounts of data in various applications.

●​ Think of data structures as the digital containers that hold information in a structured
manner. They help us organise and manage data efficiently, allowing us to perform various
operations on it.

1.2 Types of Data Structure

Data structures can be classified into two broad categories:
●​ Linear Data Structures: In these structures, data elements are stored sequentially, forming
a linear order. Common linear data structures include:
1.​ Arrays: These are contiguous blocks of memory that can hold elements of the same
data type. Elements are accessed using their indices.
2.​ Linked Lists: These are dynamic data structures made up of nodes connected to
each other. Each node contains data and a reference to the next node.
3.​ Stacks: Stacks follow the Last-In-First-Out (LIFO) principle, meaning that the last
element added is the first to be removed.
4.​ Queues: Queues follow the First-In-First-Out (FIFO) principle, where the first
element added is the first to be removed.

●​ Non-linear Data Structures: In contrast, non-linear data structures don't store elements
sequentially. Instead, they establish more complex relationships among elements. Some
examples include:
1.​ Trees: Trees are hierarchical structures consisting of nodes with parent-child
relationships. They are widely used in applications like hierarchical data
representation, parsing, and decision-making.
2.​ Graphs: Graphs are networks comprising nodes (vertices) and edges (connections).
They model complex relationships and are used in applications such as social
networks, transportation systems, and network design.

2
 NotesNeo
1.3 Choice of Right Data Structure
The choice of the right data structure for a particular problem is important for the efficiency of the
program. Some factors to consider when choosing a data structure include:
1.​ Nature of Data: Understand the nature of the data you're working with. Is it simple or
complex? Does it have a hierarchical structure? Does it need to be sorted or searched
frequently?
2.​ Operations to be Performed: Consider the operations (insertion, deletion, search,
traversal, etc.) that need to be performed on the data. Some data structures are optimized
for specific operations.
3.​ Time and Space Complexity: Evaluate the time and space complexity of different data
structures for the operations you need to perform. Choose the one that provides the most
efficient performance for your specific use case.
4.​ Memory Constraints: Consider memory usage and constraints. Some data structures may
consume more memory than others.
5.​ Ease of Use and Implementation: Choose a data structure that aligns with your
programming language and the ease of implementation. Some data structures might be
more complex to implement or use in certain programming languages.
6.​ Available Libraries and Support: Consider using built-in data structures or libraries
provided by the programming language or framework you're working with. They might offer
efficient and optimized implementations.
7.​ Flexibility and Scalability: Ensure the data structure can accommodate future changes or
scaling requirements in your application.

For example, if you need to store a list of names and need to be able to insert and delete names
efficiently, a linked list would be a good choice. If you need to store a list of numbers and need to
be able to search for numbers efficiently, a sorted array would be a good choice.

Topic 2: Algorithms

2.1 Algorithm
●​ An algorithm is a well-defined, step-by-step set of instructions designed to solve a specific
problem or accomplish a particular task.
●​ Algorithms can be classified into two main types:
1.​ Recursive algorithms: Recursive algorithms solve a problem by breaking it down
into smaller subproblems of the same type.
2.​ Non-recursive algorithms: Non-recursive algorithms solve a problem by using a
sequence of steps that do not involve breaking the problem down into smaller
subproblems.
●​ Algorithms are at the core of all software applications. They determine how efficiently a task
can be accomplished. Efficient algorithms can significantly improve the performance of
software systems, making them faster and more responsive.

●​ When choosing an algorithm to solve a problem, it is important to consider the following

factors:
○​ The complexity of the problem: Some problems are more complex than others and
may require more sophisticated algorithms.
○​ The accuracy of the solution: Some algorithms are more accurate than others.
○​ The speed of the algorithm: Some algorithms are faster than others.

3
 NotesNeo
○​ The memory requirements of the algorithm: Some algorithms require more memory
than others.

To solve logical and numerical problems in C, you can use a variety of algorithms. Some common
algorithms for solving logical problems include:
●​ Boolean search: This algorithm is used to find a value in a sorted array. It works by
comparing the value to the middle element of the array and then recursively searching the
left or right half of the array, depending on whether the value is greater or less than the
middle element.
●​ Dijkstra's algorithm: This algorithm is used to find the shortest path between two nodes in a
graph. It works by iteratively adding the shortest path to the current node to the set of
known paths.
●​ Greedy algorithm: This algorithm is used to find a solution to a problem by making the
locally optimal choice at each step. It is not guaranteed to find the global optimum, but it
can often find a good solution quickly.

Some common algorithms for solving numerical problems include:

●​ Bubble sort: This algorithm is used to sort an array by repeatedly comparing adjacent
elements and swapping them if they are in the wrong order.
●​ Merge sort: This algorithm is used to sort an array by dividing it into two halves and then
recursively sorting the halves and merging them back together.
●​ Quick sort: This algorithm is used to sort an array by repeatedly choosing a pivot element
and then partitioning the array around the pivot element.

2.2 Need for Algorithms in the Computer World

1.​ Efficiency: Algorithms provide efficient solutions to problems, allowing computers to perform
complex tasks quickly and with minimal resources.
2.​ Reusability: Well-designed algorithms can be reused in various applications, promoting
code efficiency and modularity.
3.​ Consistency: Algorithms provide a consistent and systematic approach to problem-solving,
ensuring reliability and predictability.
4.​ Optimization: Algorithms help in optimizing processes, making them more efficient and
reducing resource usage.
5.​ Automation: Algorithms play a crucial role in automating tasks, allowing computers to
perform repetitive actions without human intervention.

2.3 Development and Design of an Algorithm

Algorithm development is a systematic process that involves several key stages:
1.​ Problem Analysis: Begin by thoroughly understanding the problem you need to solve.
Identify the input, expected output, and any constraints or requirements.
2.​ Algorithm Design: Create a high-level plan or strategy for solving the problem. This plan
should be clear, logical, and efficient. During this stage, you decide on the steps and data
structures to use.
3.​ Pseudocode or Flowchart: Create a high-level description of the algorithm using
pseudocode or flowcharts to outline the steps.
4.​ Algorithm Implementation: Translate the algorithm into a programming language like C.
Write the actual code that follows the steps outlined in your design.
5.​ Algorithm Testing: Test the algorithm with various inputs and edge cases to ensure it works
correctly and handles all scenarios. Debug and refine the algorithm as needed.

4
 NotesNeo
6.​ Algorithm Optimization: If necessary, refine your algorithm to make it more efficient in terms
of time and space complexity. Optimization can involve finding better data structures or
improving the algorithm's logic.

2.4 Complexity Analysis of Algorithm

●​ The complexity of an algorithm is a measure of how much time and space it takes to
execute. Understanding the complexity of an algorithm is crucial for evaluating its efficiency
and scalability.
●​ Complexity analysis is an important tool for choosing the right algorithm for a particular
problem. By understanding the complexity of different algorithms, you can choose an
algorithm that is efficient and effective.

●​ The complexity of an algorithm can be analysed in terms of its time complexity and space
complexity.
1.​ Time complexity: The time complexity of an algorithm is the measure of the
amount of time it takes to execute. It is typically expressed in terms of the number of
operations performed by the algorithm.
2.​ Space complexity: The space complexity of an algorithm is the measure of the
amount of memory it uses to execute. It is typically expressed in terms of the
number of variables used by the algorithm.
​ ​
●​ There are three main types of complexity analysis :
1.​ Worst-case complexity: The worst-case complexity of an algorithm is the
maximum amount of time and space it takes to execute for any possible input.
2.​ Average-case complexity: The average-case complexity of an algorithm is the
average amount of time and space it takes to execute for all possible inputs.
3.​ Best-case complexity: The best-case complexity of an algorithm is the minimum
amount of time and space it takes to execute for any possible input.

●​ To analyse the complexity of an algorithm, you need to identify the following:

1.​ The number of operations performed by the algorithm for each input.
2.​ The type of operations performed by the algorithm.
Once you have identified the number and type of operations performed by the algorithm,
you can use asymptotic notation to express the complexity of the algorithm.

●​ Asymptotic notation is a way of representing the growth rate of a function as its input size
grows. The most common asymptotic notations are big O notation, big Ω notation, and big
Θ notation.
1.​ Big O notation
●​ Big O notation is a mathematical notation that describes the upper bound of the
asymptotic complexity of a function as the argument tends towards a particular
value or infinity.
●​ Big O notation is used to represent the worst-case complexity of an algorithm. It is
expressed as O(f(n)), where f(n) is the number of operations performed by the
algorithm for the largest input size.

●​ Big O notation can be used to compare the efficiency of different algorithms for
solving the same problem. For example, the binary search algorithm is more
efficient than the linear search algorithm for searching for an element in a sorted
array. This is because the binary search algorithm has a lower Big O notation.
5
 NotesNeo
Linear search algorithm has a Big O notation of O(n) while binary search algorithm
has a Big O notation of O(log n).

●​ Examples of Big O notation:

1)​ O(1)-Constant time: The number of operations performed by the algorithm does not
depend on the size of the input.It's the most efficient scenario.
2)​ O(n)- Linear time: The number of operations performed by the algorithm is
proportional to the size of the input.
2
3)​ O(𝑛 )-Quadratic time: The number of operations performed by the algorithm is
proportional to the square of the size of the input.
4)​ O(log n)-Logarithmic time: The number of operations performed by the algorithm is
proportional to the logarithm of the size of the input.

●​ Big O notation is just an asymptotic approximation of the complexity of an algorithm.

It does not take into account other factors such as the constant overhead of the
algorithm or the specific hardware on which it is being executed.

2.​ Big Ω notation

●​ Big Omega notation (Ω) is a mathematical notation that describes the lower bound
of the asymptotic complexity of a function as the argument tends towards a
particular value or infinity.
●​ Big Ω notation is used to represent the best-case complexity of an algorithm. It is
expressed as Ω(f(n)), where f(n) is the number of operations performed by the
algorithm for the smallest input size.

3.​ Big Θ notation

●​ Big Theta notation (Θ) is a mathematical notation that describes the tightness of the
bound of the asymptotic complexity of a function as the argument tends towards a
particular value or infinity.
●​ Big Θ notation is used to represent the average-case / expected-case complexity of
an algorithm. It is expressed as Θ(f(n)), where f(n) is the number of operations
performed by the algorithm for the most likely input sizes.

Topic 3: Array
An array in C is a collection of elements of the same data type that are stored in contiguous
memory locations. Each element in the array is identified by its index or subscript. The first element
has an index of 0, the second has an index of 1, and so on.

●​ In C, an array is declared as follows:

data_type array_name[array_size];
For example, the following declares an array of 5 integers:
int my_array[5];

●​ To access an element of an array, you use its index as follows:

array_name[index]
For example, the following prints the second element of the array my_array:
printf("%d\n", my_array[1]);

6
 NotesNeo
Array as an abstract data type : ADT is a way to describe a data structure without specifying how it
is implemented. It is like a blueprint for a data structure, which defines the operations that can be
performed on it but not how those operations are implemented.

Multi-Dimensional Arrays
A multi-dimensional array is an array with more than one dimension. Unlike a one-dimensional
array, which is a simple list of elements, a multi-dimensional array can be thought of as a table or a
matrix with rows and columns. The most common types are 2D arrays (two-dimensional arrays),
but C also supports 3D arrays and arrays with more than three dimensions.

Example of a two-dimensional array :

#include <stdio.h>

int main() {
// Declare a 2D array with 3 rows and 4 columns
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};

// Access and print elements of the 2D array

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
printf("%d\t", matrix[i][j]);
}
printf("\n");
}

return 0;
}

Output:

1 2 3 4
5 6 7 8
9 10 11 12

We can extend this concept to create 3D arrays and higher-dimensional arrays by adding more
dimensions. For instance, a 3D array might represent a cube of data with length, width, and height.
int cube[2][3][4]; // 3D array with dimensions 2x3x4

Operations on Data Structure (Array)

Following operations are supported by an array:
●​ Traversal
●​ Insertion

7
 NotesNeo
●​ Deletion
●​ Searching
●​ Sorting
●​ Merging

3.1 Traversal
●​ Traversal is a common operation in data structures that involves systematically visiting and
accessing each element within a data structure.Traversing an array typically involves using
a loop to visit and print each element.

●​ Algorithm for Traversal in an array:

1.​ Start from the first element (index 0) of the array.
2.​ Initialise a loop variable to zero i=0.
3.​ While the loop variable i is less than the size n of the array, print the element at the
current index and increment the loop variable.

●​ Code (C Language):
#include <stdio.h>

void traverse(int arr[], int n) {

for (int i = 0; i < n; i++) {
// Process or print each element in the array
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int myArray[] = {1, 2, 3, 4, 5};
int size = sizeof(myArray) / sizeof(myArray[0]);

// Call the traverse function to print the array elements

traverse(myArray, size);

return 0;
}

●​ Complexity Analysis:
Time Complexity:
○​ Traversal of an array requires visiting each element once using a loop, making it
O(n) (linear time), where n is the number of elements in the array. This is because
the time needed to access each element is constant (O(1)).

Space Complexity:
○​ The space complexity of array traversal is O(1) (constant space). This is because
you typically don't need additional memory that scales with the size of the array;
you're only using a constant amount of memory to keep track of the current element
or index.

8
 NotesNeo
●​ Practical Example: Consider a scenario where you're managing a music playlist. To listen to
each song or calculate the total duration, you need to traverse the playlist and access each
song in turn.

3.2 Insertion
●​ Insertion is the process of adding a new element at a specified position into a data
structure, such as an array.

●​ The algorithm for inserting an element at a specified position in an array is as follows:

1.​ Check if the array is full (i.e., if the number of elements equals the array's capacity).
If it is full, the insertion cannot be performed.
2.​ If the array is not full, shift the elements from the insertion position to the right to
make space for the new element.
3.​ Insert the new element at the desired position.
4.​ Update the count of elements in the array to reflect the new total.

●​ Code (C Language):
#include <stdio.h>

void insertElement(int arr[], int size, int element, int index) {

// Check if the index is within bounds
if (index < 0 || index > size) {
printf("Index out of bounds.\n");
} else {
// Shift elements to the right
for (int i = size - 1; i >= index; i--) {
arr[i + 1] = arr[i];
}
// Insert element at the given index
arr[index] = element;

// Increase the size by 1

size++;

// Print the updated array

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
}
}

int main() {
int arr[10] = {1, 3, 4, 2, 5};
int size = 5;
int element = 10;
int index = 5;

// Calling the insertElement function

9
 NotesNeo
insertElement(arr, size, element, index);

return 0;
}

●​ Output : 1 3 4 2 5 10
●​ For example, consider inserting an element 'X' at position '3' in an array:
Before Insertion: [A, B, C, D, E, F]
After Insertion: [A, B, X, C, D, E]

●​ Complexity Analysis:
Time Complexity:
○​ Insertion at the end of an array: O(1) (constant time), assuming there is available
space in the array as you can directly place the element at the end of the array.
○​ Insertion at the beginning or in the middle of an array: O(n) (linear time) in the worst
case because it may require shifting existing elements to make room for the new
element.

Space Complexity:
○​ The space complexity of the insertion operation is O(1), as it only changes the
content of existing memory locations without requiring additional memory allocation.

●​ Practical Example: Imagine you're managing a library, and a new book arrives that needs to
be inserted into the collection. You need to determine where to place the book so that it fits
seamlessly into the existing arrangement.

3.3 Deletion
●​ Deletion is another fundamental operation in data structures that involves removing
elements from a data structure.
●​ The algorithm for deleting an element at a specified position in an array is as follows:
1. Check if the specified position is valid (i.e., within the bounds of the array). If it is not
valid, the deletion cannot be performed.
2. If the position is valid, shift the elements from the position of the deleted element to the
left to fill the gap.
3. Update the count of elements in the array to reflect the new total.
●​ Code (C Language):
#include <stdio.h>

void deleteElement(int arr[], int size, int index) {

// Check if the index is within bounds
if (index < 0 || index >= size) {
printf("Index out of bounds.\n");
} else {
// Shift elements to the left
for (int i = index; i < size - 1; i++) {
arr[i] = arr[i + 1];
}

// Decrease the size by 1

10
 NotesNeo
size--;

// Print the updated array

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
}
}

int main() {
int arr[10] = {3, 6, 4, 5, 2};
int size = 5;
int index = 2; // Index of the element to delete

// Calling the deleteElement function

deleteElement(arr, size, index);

return 0;
}
●​ Output : 3 6 5 2
●​ For example, consider deleting the element at position '2' in an array:
Before Deletion: [A, B, C, D, E, F]
After Deletion: [A, C, D, E, F, _]

●​ Complexity Analysis:
Time Complexity:
○​ Deletion at the end of an array: O(1) (constant time) as it involves simply updating
the array size.
○​ Deletion from the beginning or middle of an array: O(n) (linear time) in the worst
case because it may require shifting elements to fill the gap left by the deleted
element.
○​ The average-case time complexity of the deletion operation is O(n/2), which means
that the algorithm will take an average of n/2 operations to delete an element from
an array.
Space Complexity:
○​ The space complexity of binary search is O(1), which means that the algorithm does
not require any additional memory to execute. Similar to insertion, deleting an
element in an array does not affect the space complexity, as it doesn't involve
allocating or deallocating memory.

●​ Practical Example: Picture yourself managing an online shopping cart. When a customer
decides to remove an item from their cart, you need to execute the deletion operation to
ensure that the cart reflects the updated list of items.

Topic 4: Searching
Searching is the process of finding a specific element (or determining its absence) in a collection of
items, such as an array, list, or database. In computer science, various searching algorithms are
used to efficiently locate a particular item within a dataset.

11
 NotesNeo
4.1 Linear Search
●​ Linear search is a simple searching technique that works well for unsorted arrays. It
involves examining each element in the array sequentially until a match (target element) is
found or the entire array has been traversed.

●​ Linear search is a simple search algorithm that works by sequentially traversing an array
and comparing each element to the target value. If the target value is found, the algorithm
returns the index of the element. Otherwise, the algorithm returns -1.

●​ Algorithm for linear search:

1.​ Start at the beginning of the array.
2.​ For each element in the array:
a.​ Compare the current element with the target element.
b.​ If they match, return the index of the current element.
3.​ If the loop completes without finding a match, return -1 to indicate that the element
is not in the array.

●​ Code (C Language):
#include <stdio.h>

int linearSearch(int arr[], int size, int target) {

for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Element found at index i
}
}
return -1; // Element not found
}

int main() {
int arr[] = {11, 8, 13, 7, 15, 9, 10};
int size = sizeof(arr) / sizeof(arr[0]); // Length of array
int target = 7;

int index = linearSearch(arr, size, target);

if (index == -1) {
printf("Element %d not found in the array\n", target);
} else {
printf("Element %d found at index %d\n", target, index);
}

return 0;
}

●​ Complexity Analysis:
Time Complexity: The time complexity of linear search is O(n), where n is the size of the
array. This is because the algorithm may need to compare the target value to every element
in the array in the worst-case scenario.

12
 NotesNeo

Space Complexity: The space complexity of linear search is O(1), which means that the
algorithm does not require any additional memory to execute. It uses a constant amount of
extra space regardless of the size of the input.

●​ Practical Example: Imagine you're looking for a specific book in a library, and you decide to
scan each shelf, starting from the first, until you find the book you're looking for.

4.2 Binary Search

●​ Binary search is an efficient searching algorithm specifically designed for sorted arrays. The
key idea behind binary search is to repeatedly divide the search interval in half until the
target value is found or the interval becomes empty.

●​ Binary search is a more efficient search algorithm than linear search. It works by dividing
the array in half and comparing the target value to the middle element. If the target value is
equal to the middle element, the algorithm returns the index of the element. Otherwise, the
algorithm recursively searches the half of the array that contains the target value.

●​ Algorithm for Binary Search:

1. Initialize two pointers, `left` and `right`, to the first and last indices of the array,
respectively.
2. While `left` is less than or equal to `right`:
a.​ Calculate the middle index as `(left + right) / 2`.
b.​ Compare the element at the middle index with the target element.
c.​ If they match, return the middle index as the position of the target element.
d.​ If the middle element is less than the target element, set `left` to `middle + 1` to
search in the right half.
e.​ If the middle element is greater than the target element, set `right` to `middle - 1` to
search in the left half.
3. If the loop completes without finding a match, return -1 to indicate that the element is not
in the array.

●​ Code (C Language):

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {

int left = 0, right = size - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == arr[mid]) {
return mid; // Element found at index mid
}
else if (target > arr[mid]) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}

13
 NotesNeo
return -1; // Element not found
}

int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Sorted array
int size = sizeof(arr) / sizeof(arr[0]); // Length of array
int target = 7;

int index = binarySearch(arr, size, target);

if (index == -1) {
printf("Element %d not found in the array\n", target);
} else {
printf("Element %d found at index %d\n", target, index);
}

return 0;
}

●​ Complexity Analysis:
Time Complexity: The time complexity of binary search is O(log n), where n is the size of
the array. This is because the algorithm divides the array in half on each recursive call.

Space Complexity: The space complexity of binary search is O(1), which means that the
algorithm does not require any additional memory to execute.

●​ Practical Example: Think of binary search as searching for a word in a dictionary. You open
the dictionary to a random page (the middle) and determine whether the word you're
looking for comes before or after the word on that page. You repeat this process, halving
the remaining pages each time, until you find the word you seek.

4.3 Linear Search vs Binary Search

Feature Linear Search Binary Search

Sequentially checks each Divides the search interval in half and

Search Strategy element until a match is found or narrows down the search space.
the end is reached. Requires a sorted collection.

Order Works for both sorted and Requires the collection to be sorted for
Requirement unsorted collections. correct operation.

Highly efficient for searching in sorted

Efficiency Less efficient for large datasets.
datasets.

1. Set two pointers (low and high).

1. Start from the beginning.
2. Divide the search interval.
2. Check each element
3. Repeat until target is found or interval
Algorithm Steps sequentially.
is empty.
3. Return index if the target is
4. Return index if the target is found;
found; otherwise, return -1.
otherwise, return -1.

14
 NotesNeo

O(log n) in the worst case, where n is the

O(n) in the worst case, where n
Time Complexity size of the collection. Efficient for large
is the size of the collection.
datasets.

Space
O(1) - In-place algorithm. O(1) - In-place algorithm.
Complexity

Small datasets or unsorted Large datasets, especially when the data

Use Cases
collections. is sorted.

Requires careful handling of sorted data

Implementation Simple and easy to implement.
and more complex to implement.

Searching for an element in an

Examples Searching for a word in a dictionary.
unsorted list.

MDU Previous Year Questions

1.​ Define Big-O notation .
2.​ What do you mean by Data Structure ? Give examples of linear, non-linear, homogeneous,
non homogeneous data structures.
3.​ What is data structure ? How can we choose the right data structure ?
4.​ Describe the time and space complexity of an algorithm.
5.​ What is an algorithm? In what way analysis of an algorithm is done? What is the need for
algorithms in the computer world ?
6.​ How do we develop and design an algorithm ? Also explain time and space complexity of
an algorithm. Explain with example.
7.​ Explain the Sparse matrices.
8.​ Explain the Multi dimensional arrays.
9.​ Write an algorithm to insert and delete an element from a two dimensional array.
10.​Write an algorithm to find out the transpose of a matrix.
11.​What is an array? Explain various operations that can be performed on the array.
12.​What is Linear search ? How is Binary search different from Linear search ? Explain.
13.​What do you mean by searching ? Explain binary search algorithm with suitable examples
and discuss its complexity.

15
 NotesNeo

Assignment 1
1.​ Differentiate linear and non-linear data structure.
2.​ Write a short note on abstract data structure.
3.​ Define array. Explain its operations.
4.​ Define ADT (Abstract Data Type). Mention the features of ADT.
5.​ Discuss the best case, worst case and average case of an algorithm.
6.​ Convert the prefix expression -/ab*+bed into infix expression.
7.​ Define binary search with an example and write down its limitations
8.​ Implement the following programs in C: 1. Linear Search 2. Binary Search
9.​ Advantages and Disadvantages of Array over Linked List.
10.​Define STACK. Explain its operations
11.​What is QUEUE? Explain its various types of Queue.
12.​Explain the memory allocation deallocation concept.
13.​Write a program using functions for implementation of circular Queue.
14.​ (a) Create functions for push and pop operations of stack.
​ (b) Write a function to convert an infix expression to a postfix expression.
Pass a one dimensional character array P to the function as input (infix exp) and
return character array Q (postfix exp).
Test your program for following input P: (A-(B/C) D+E) *F%G

16