Data Structures University Syllabus

Unit 1	Introduction to Algorithm and Data Structures
	Algorithms- Problem Solving, Introduction to Algorithms, Characteristics of algorithms, Algorithm design tools: flowchart,
	Algorithm design tools: Pseudo code , Writing pseudocode for sequential searching, max, min, factorial
	Iterative and Recursive algorithms
	Analysis of Algorithms, Complexity of algorithms- Space complexity
	Analysis of Algorithms, Time complexity,
	Asymptotic notation- Big-O, Theta and Omega, standard measures of efficiency.
	Data Structures- Data structure, Abstract Data Types (ADT), Concept of linear and Non-linear, static and dynamic, persistent and ephemeral data structures,
	Algorithmic Strategies- Introduction to algorithm design strategies- Divide and Conquer, and Greedy strategy. #Application
	Recurrence relation - Recurrence Relation, Linear Recurrence Relations, With constant Coefficients,
	Homogeneous Solutions. Solving recurrence relations
	Home assignment: Pseudo code writing  and Algorithm Analysis Class assignments: Objective questions
2	Linear Data Structures Using Sequential Organization
	Sequential Organization, Linear Data Structure Using Sequential Organization, Array as an Abstract Data Type,
	Memory Representation and Address Calculation
	Inserting an element into an array, Deleting an element, Multidimensional Arrays, Two-dimensional arrays, n- dimensional arrays,
	Concept of Ordered List, Single Variable Polynomial, Representation using arrays
	Polynomial as array of structure, Polynomial addition,
	Polynomial multiplication,
	Sparse Matrix, Sparse matrix representation, Sparse matrix addition,
	Transpose of sparse matrix
	String Manipulation Using Array.
	Case Study- Use of sparse matrix in Social Networks and Maps. Home assignment: Pseudo code writing for operations on arrays, strings Class assignments: Objective questions
3	Linked Lists
	Concept of Linked list, Comparison of sequential and linked organizations, ADT, Primitive operations,
	Realization of Linked Lists, Realization of linked list using arrays, Dynamic Memory Management,
	Linked list using dynamic memory management
	Linked list operations, Head pointer and header node,
	Types of linked list- Linear and circular linked lists, Singly circular linked list, operations
	Doubly Linked List and operations, Doubly circular linked list
	Polynomial Manipulations - Polynomial addition,
	Multiplication of two polynomials using linked list
	Generalized Linked List (GLL) concept, representation of polynomial and sets using GLL.
	Case Study- Garbage Collection Class Tutorial on objective questions, Home assignment: operations on linked lists
4	Stacks
	Stacks- concept, Primitive operations, Stack Abstract Data Type
	Representation of Stacks Using Sequential Organization, stack operations, Analysis
	Applications of Stack- Expression Evaluation and Conversion
	Polish notation and expression conversion
	Need for prefix and postfix expressions, Postfix expression evaluation,
	Linked Stack and Operations, Multiple Stacks
	Recursion- concept, variants of recursion- direct, indirect, tail and tree
	Backtracking algorithmic strategy, use of stack in backtracking,4 queens problem
	Case Study-, Android- multiple tasks/multiple activities and back stack Class assignment: Presentation on Linear data structure Applications
5	Queues
	Concept, Queue as Abstract Data Type, Realization of Queues Using Arrays,
	Queue operations, Analysis
	Circular Queue, Advantages of using circular queues, operations
	Dequeue operations
	Priority Queue, Array implementation of priority queue
	Linked Queue and operations
	Linked Dqueue, Multi-queues,
	Case study- Priority queue in bandwidth management
	Home assignment:  Operations on type of queues Class assignments:   Application of queue
6	Sorting and Searching
	Searching- Search Techniques, Sequential search, variant of sequential search- sentinel search
	Binary search, Analysis
	Fibonacci search, Analysis, Case Study
	Sorting- Types of sorting-Internal and external sorting, General sort concepts-sort order, stability, efficiency, number of passes
	Sorting methods- Bubble sort, Insertion sort, Selection sort
	Quick sort, analysis
	Heap sort, analysis ,Shell sort
	Bucket sort, Radix sort, analysis, Case Study
	Home assignment: Sorting techniques Class assignments:   Sorting techniques Comparison