CS 231 Data Structures and Algorithms – I (Notes)

S.Y.B.Sc. (Computer Science) Computer Science Paper - I Title: Data Structures and Algorithms – I
Course Contents
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, DataStructure 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.2 Array 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.3 Backtracking 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
Practice Assignments