Data Structures & Algorithms 1 : SYBCS Semester 1 : Syllabus

 Chapter 1 Introduction to Data Structures and Algorithm Analysis

1.1 Introduction

1.1.1 Need of Data Structure 

1.1.2 Definitions - Data and information, Data type, Data object, ADT, Data Structure 

1.1.3 Types of Data Structures

1.2 Algorithm analysis 

1.2.1 Space and time complexity, Graphical understanding of the relation between

different functions of n, examples of linear loop, logarithmic,quadratic loop etc.

1.2.2 Best, Worst, Average case analysis, Asymptotic notations (Big O, Omega Ω, 

Theta  ), Problems on time complexity calculation.

Chapter 2 Array as a Data Structure 

2.1 ADT of array, Operations

2.2Array applications - Searching

2.2.1 Sequential search, variations - Sentinel search, Probability search, ordered list 

 search

2.2.2 Binary Search

2.2.3 Comparison of searching methods

2.3 Sorting Terminology- Internal, External, Stable, In-place Sorting 

2.3.1 Comparison Based Sorting - Lower bound on comparison based sorting, 

Methods- Bubble Sort, Insertion Sort, Selection Sort, Algorithm design strategies -

Divide and Conquer strategy, Merge Sort, Quick Sort, complexity analysis of sorting 

methods.

 2.3.2 Non Comparison Based Sorting: Counting Sort, Radix Sort, complexity analysis.

 2.3.3 Comparison of sorting methods

Chapter 3 Linked List

3.1 List as a Data Structure, differences with array.

3.2 Dynamic implementation of Linked List, internal and external pointers

3.3 Types of Linked List – Singly, Doubly, Circular

3.4 Operations on Linked List - create, traverse, insert, delete, search, sort, reverse, 

concatenate, merge, time complexity of operations.

3.5 Applications of Linked List – polynomial representation, Addition of two polynomials

3.6 Generalized linked list – concept, representation, multiple-variable polynomial 

representation using generalized list.

Chapter 4 Stack 

4.1 Introduction 

4.2 Operations – init(), push(), pop(), isEmpty(), isFull(), peek(), time complexity of 

operations.

4.3 Implementation- Static and Dynamic with comparison

4.4 Applications of stack

4.4.1 Function call and recursion, String reversal, palindrome checking

4.4.2 Expression types - infix, prefix and postfix, expression conversion and 

evaluation (implementation of infix to postfix, evaluation of postfix)

4.4.3Backtracking strategy - 4 queens problem (implementation using stack)

Chapter 5 Queue 

5.1 Introduction

5.2 Operations - init(), enqueue(), dequeue(), isEmpty(), isFull(), peek(),time complexity of 

operations, differences with stack.

5.3 Implementation - Static and Dynamic with comparison

5.4 Types of Queue - Linear Queue, Circular Queue, Priority Queue, Double Ended Queue

(with implementation)

5.5 Applications – CPU Scheduling in multiprogramming environment, Round robin 

algorithm