# Data Structures and Algorithms

In computer science, a **data structure** is a particular way of organizing data in a computer so that it can be used efficiently. They essentially provide** a means to manage **large amounts of data efficiently for uses such as large databases and internet indexing services.An **algorithm** is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks.

Usually, efficient data structures are key to designing efficient algorithms.This **course will teach you** C and Algorithm, Searching, Stack, Queues, Trees and Graphs and related concepts.

## Overview

Data Structures and Algorithms

Abbreviation | DSA | ||||
---|---|---|---|---|---|

Course | Second Year, Semester I ENTC | ||||

Credits
| |||||

Examination Scheme
| |||||

Language | English |

## Table of Contents

## Prerequisites

Basic knowledge of C language is required.

## Course Objectives

- To assess how the choice of data structures and algorithm design methods impacts the performance of programs.
- To choose the appropriate data structure and algorithm design method for a specified application.
- To study the systematic way of solving problems, various methods of organizing large amounts of data.
- To solve problems using data structures such as linear lists, stacks, queues, binary trees, binary search trees, and graphs and writing programs for these solutions.
- To employ the different data structures to find the solutions for specific problems

## Course Outcomes

On completion of the course, student will be able to:

- Discuss the computational efficiency of the principal algorithms such as sorting &

searching. - Write and understand the programs that use arrays & pointers in C
- Describe how arrays, records, linked structures are represented in memory and use

them in algorithms. - Implement stacks & queues for various applications.
- Understand various terminologies and traversals of trees and use them for various

applications. - Understand various terminologies and traversals of graphs and use them for

various applications.

## Syllabus and Notes

### Unit 1: Introduction to C and Algorithm

[Main Page: Introduction to C and Algorithm]

Constants, variables and keywords in C, operators and control structure in c(decision, loop and case), functions, macros, arrays and string manipulation, structure, union, enumeration, bitwise operations Functions: Parameter passing call by value and call by reference, scope rules, functions and pointers, function returning pointer, pointer to function, String manipulations using Arrays, pointer to pointer, Dynamic memory management.**Analysis of algorithm**: frequency count and its importance in analysis of an algorithm, Time complexity & Space complexity of an algorithm, Big ‘O’ notation

### Unit 2: Searching and Sorting

[Main Page: Searching and Sorting]

Need of searching and sorting, why various methods of searching and sorting**Sorting methods**: Linear, binary search and Fibonacci Search.**Sorting methods**: Bubble, insertion, selection, merge, Time complexity of each searching and sorting algorithm, Hashing Techniques.

### Unit 3: Stack and Queues

**Stacks**: Concept, Basic Stack operations, Array representation of stacks, Stack as ADT**Stack Applications**: Reversing data, Arithmetic expressions conversion and evaluation.**Queues**: Concept, Queue operations, Array representation of queues, Queue as ADT, Circular queues**Application of queues**: Categorizing data, Simulation of queues.

### Unit 4: Linked List

Concept of linked organization, singly linked list, stack using linked list, queue using linked list, doubly linked list, circular linked list, Linked list as ADT.

Representation and manipulations of polynomials using linked lists, comparison of sequential linked organization with linked organization

### Unit 5: Trees

- Introduction to trees: Basic Tree Concepts
- Binary Trees: Concept & Terminologies, Representation of Binary Tree in memory, Traversing a binary tree
- Binary Search Trees (BST): Basic Concepts, BST operations.

### Unit 6: Graphs

Basic Concepts & terminology, Sequential representation of graphs; Adjacency matrix, Path matrix, Linked representation of a graph, Operations on graph, Traversing a graph, Spanning trees; Minimum Spanning tree, Kruskal’s Algorithm, Prim’s Algorithm. Dijkstra's Shortest

Path Algorithm

## List of Practicals

Note: Practical 1-8 are compulsory. Practical 9-15 are optional.

Write C program to implement

- Write C program to store student information (e.g. RollNo, Name, Percentage etc).

a. Display the data in descending order of Percentage (Bubble Sort).

b. Display data for Roll No specified by user (Linear Search).

c. Display the number of passes and comparisons for different test cases (Worst, Average, Best case). - Perform following String operations with and without pointers to arrays (without using the library functions):

a. substring, b. palindrome, c. compare, d. copy, e. reverse. - Data base Management using array of structure with operations Create, display, Modify, Append, Search and Sort.(For any database like Employee or Bank database with andwithout pointers to structures)
- Create a singly linked list with options:

a. Insert (at front, at end, in the middle), b. Delete (at front, at end, in the middle), c. Display, d. Display Reverse, e. Revert the SLL - Implement Stack using arrays & Linked Lists. Write a menu driven program to perform following operations on stack

a. Push, b. Pop, c. Display - Implement Queue using arrays & Linked Lists. Write a menu driven program to perform following operations on Queue

a. Insert, b. Delete, c. Display - Binary search tree: Create, search, recursive traversals.
- Graph using adjacency Matrix with BFS & DFS traversals.
- Implement set operations using arrays and perform union, intersection, difference, symmetric difference
- Accept input as a string and construct a Doubly Linked List for the input string with eachnode contains, as a data one character from the string and perform:

a. Insert, b. delete, c. Display forward, d. Display backward - Represent graph using adjacency list or matrix and generate minimum spanning tree using Prism’s algorithm
- Read & write operations in a text file.
- Polynomial addition using array of structure.
- Evaluation of postfix expression (input will be postfix expression)
- Implement following Matrix operations:

a. addition with pointers to arrays, b. multiplication without pointers to arrays, c. transpose with pointers to arrays

### Previous Year Questions

- Pattern 2012 Question Papers
- Model Answer Paper: May 2017 Exam

## References

- UniPune Website
- Icon by Creative Stall and VishalE