BCA301

Data Structure and Algorithm
Code: 
BCA301
Year / Semester: 
3rd Semester
Objective: 

Data structures are used in almost every program or software system. Specific data structures are essential ingredients of many efficient algorithms, and make possible the management of huge amounts of data. This course will cover the data structure and algorithm.

Credits: 
3

Introduction to Data Structures and Algorithms

Introduction to data representation, Review of Data Structures – Arrays, pointers, structure, lists, trees and graphs, What is Algorithm?, Designing Algorithms, Analyzing Algorithms, Mathematical notation and Functions, Performance measurements.

Data Structure

Abstract Data Type, Arrays, Functions, Structure and unions, Pointers, Memory.

Arrays

One dimensional array, two dimensional arrays, multidimensional arrays, ordered arrays.
Linear Data Structure - Linear/Circular, Doubly linked list and operations, Applications of linked list, polynomial manipulation, multiple precision arithmetic.

Algorithms on Stack

Representation using arrays and linked list, Push and Pop Operation, Representation of expressions, Infix, Postfix, prefix, Evaluation of the expression, Transforming affix expression and into postfix expression, recursion.

Algorithms on Queue

Representing using arrays and linked list, Insertion and deletion operations, circular queue, double ended queues, priority queues, and multiple queues.

Non Linear Data Structure: Graphs

General Concept, Sequential and linked representation of binary tree sequential representation, Binary tree, binary tree traversal algorithms, threaded binary tree traversal, General tree and its conversion, binary search tree, Applications of trees.

Sorting Algorithms and their Analysis

Internal and external sorting, Sorting problem, Bubble sort, selection sort, insertion sort, Shell sort, Address calculation sort, etc.

Searching

Sequential search, Binary Search, hashing, Hash functions, Collison resolution Techniques, Dynamic memory Allocation.

File Structure

Definition and Concept, File Organization, Files in C.

Suggested Readings: 
  1. A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer
  2. Data Structures and Algorithms. Addison Wesley
  3. Introduction to Algorithms. McGraw-Hill
  4. Dinesh Mehta and Sartaj Sahni Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2007.
  5. Niklaus Wirth, Algorithms and Data Structures