Data Structures and Algorithms

Updated on 2017/06/20 04:26

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

Data Structures and Algorithms

AbbreviationDSA
Course

Second Year, Semester I

ENTC

Credits
Theory4
Practical1

Examination Scheme

Online Phase I & II (Objective)50
Phase II: End Semester Examination50
LanguageEnglish

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:

  1. Discuss the computational efficiency of the principal algorithms such as sorting &
    searching.
  2. Write and understand the programs that use arrays & pointers in C
  3. Describe how arrays, records, linked structures are represented in memory and use
    them in algorithms.
  4. Implement stacks & queues for various applications.
  5. Understand various terminologies and traversals of trees and use them for various
    applications.
  6. 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

[Main Page: 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

[Main Page: 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

[Main Page: 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

[Main Page: 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

  1. 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).
  2. 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.
  3. 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)
  4. 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
  5. Implement Stack using arrays & Linked Lists. Write a menu driven program to perform following operations on stack
    a. Push, b. Pop, c. Display
  6. Implement Queue using arrays & Linked Lists. Write a menu driven program to perform following operations on Queue
    a. Insert, b. Delete, c. Display
  7. Binary search tree: Create, search, recursive traversals.
  8. Graph using adjacency Matrix with BFS & DFS traversals.
  9. Implement set operations using arrays and perform union, intersection, difference, symmetric difference
  10. 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
  11. Represent graph using adjacency list or matrix and generate minimum spanning tree using Prism’s algorithm
  12. Read & write operations in a text file.
  13. Polynomial addition using array of structure.
  14. Evaluation of postfix expression (input will be postfix expression)
  15. 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

References

  • UniPune Website
  • Icon by Creative Stall and VishalE
Tags:
Created by Vishal E on 2017/05/08 14:32