DSA (Data Structure and Algorithms)

DCRUST SYLLABUS

CSE 201 C Data Structure and Algorithms

CATEGORY : ENGINEERING SCIENCE COURSE

Course Objectives:

1. To analyse algorithms in terms of time, space  and computational complexities.
2. To learn searching algorithms (Linear Search and Binary search) and  implement them.
3. To study Stacks, Queues, Linked lists, Graph search and  traversal techniques. 
4. To study sorting algorithms i.e.  Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort and  Heap sort and compare their performance.

Unit I

Introduction:  Basic   Terminologies: Elementary Data Organizations, Data Structure operations: insertion, deletion, traversal       etc. Analysis of an Algorithm, Asymptotic Notations, Time-Space trade off. Searching: Linear  Search  and  Binary  Search  Techniques and their complexity analysis.

Click on any topic to read about the topic.

Unit II

Stacks   and   Queues:   ADT   Stack   and   its   operations: Algorithms and their complexity analysis,  Applications of  Stacks:   Expression  Conversion  and   evaluation – corresponding algorithms and complexity analysis. ADT queue, Types of Queue: Simple Queue, Circular Queue, Priority Queue;  Operations on  each  types  of Queues: Algorithms and their analysis.

Click on any topic to read about the topic.

Unit III

Linked            Lists:   Singly linked  lists:   Representation    in memory,  Algorithms  of  several operations:   Traversing,  Searching, Insertion into, Deletion         from    linked            list;  Linked representation of Stack and Queue, Header nodes, Doubly  linked  list:  operations  on  it  and algorithmic  analysis; Circular           Linked             Lists: all operations their  algorithms  and  the complexity analysis.

Trees:  Basic Tree Terminologies, Different types of Trees: Binary  Tree,  Threaded  Binary Tree,  Binary  Search  Tree,  AVL  Tree;  Tree  operations  on  each  of  the  trees  and  their algorithms  with complexity analysis.      Applications   of Binary Trees.  B  Tree,  B+  Tree: definitions, algorithms and analysis.

Click on any topic to read about the topic.

Unit IV

Sorting            and      Hashing:         Objective        and      properties        of different   sorting   algorithms: Selection Sort, Bubble Sort,  Insertion Sort,    Quick  Sort,  Merge Sort, Heap       Sort; Performance and Comparison among all the  methods, Hashing.

Graph: Basic Terminologies and Representations, Graph search and traversal algorithms and complexity analysis.

Click on any topic to read about the topic.

TEXT BOOKS :

1. Fundamentals   of   Data   Structures, Illustrated  Edition  by  Ellis  Horowitz,  Sartaj Sahni, Computer Science Press.
2. Data Structures, Revised 1^st Edition by Seymour Lipschutz , Scaum’s Outline Series  McGraw Hill

REFERENCE BOOKS :

1. Algorithms,  Data   Structures,  and   Problem Solving  with C++” ,  Illustrated  Edition by Mark Allen            Weiss, Addison-Wesley Publishing Company
2. How to Solve it by Computer , 2nd Impression by R. G. Dromey, Pearson Education.

Course Outcomes:  Upon successful completion of the course, students will demonstrate the ability to:

1. Analyze the algorithm for a problem solution and determine the time and computation complexity and justify the correctness.
2. Write the algorithm for Search   problem (Linear Search and Binary Search) .
3. Write an algorithm for Stack, Queue, Linked list, Graph search and  traversal    techniques  and analyze the same to determine the time and computation complexity.
4. Write an algorithm for Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, Heap sort and compare their performance in term of Space and time complexity.