Data Structures and Algorithms
0%
Course Title: Data Structures and Algorithms
Course No: CSC211
Nature of the Course: Theory + Lab
Semester: 3
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Credit Hours: 3
Course Description
Course Objectives
Course Contents
1.1. Foundations
- Data types
- Data structure
- Abstract data type
1.3. Algorithms
- Introduction to algorithms
- Asymptotic notations
- Common functions
2. Stack
4 hrs
2.1. Stack fundamentals
- Basic concept of stack
- Stack as an ADT
- Stack operations
- Stack applications
2.2. Expression processing
- Conversion from infix to postfix expression
- Conversion from infix to prefix expression
- Evaluation of postfix expression
- Evaluation of prefix expression
3. Queue
4 hrs
3.1. Queue fundamentals
- Basic concept of queue
- Queue as an ADT
- Primitive operations in queue
3.2. Types of queue
- Linear queue
- Circular queue
- Priority queue
4. Recursion
3 hrs
4.1. Recursion concepts
- Principle of recursion
- Comparison between recursion and iteration
- Tail recursion
4.2. Classic problems
- Factorial
- Fibonacci sequence
- GCD
- Tower of Hanoi (TOH)
5. Lists
8 hrs
5.1. List fundamentals
- Basic concept of list
- List as an ADT
- Array implementation of list
- Linked list
5.2. Types of linked list
- Singly linked list
- Doubly linked list
- Circular linked list
5.3. Linked list operations
- Node creation
- Insertion at beginning
- Insertion at end
- Insertion at specified position
- Deletion from beginning
- Deletion from end
- Deletion from specified position
6. Sorting
8 hrs
6.1. Sorting fundamentals
- Introduction to sorting
- Internal sort
- External sort
6.2. Comparison sorting algorithms
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
6.3. Divide and conquer sorting algorithms
- Merge sort
- Quick sort
- Heap sort
7.1. Searching fundamentals
- Introduction to searching
- Sequential search
- Binary search
7.3. Hashing
- Hash function
- Hash tables
- Collision resolution techniques
8. Trees and Graphs
8 hrs
8.1. Tree fundamentals
- Concept and definitions
- Basic operations in binary tree
- Tree height, level and depth
8.2. Binary search tree
- Insertion
- Deletion
- Traversals
- Search in BST
8.3. AVL tree
- Balancing algorithm
- Applications of trees
8.4. Graphs
- Definition of graphs
- Representation of graphs
- Graph traversal
8.5. Minimum spanning trees
- Kruskal algorithm
- Prims algorithm
8.6. Shortest path algorithms
- Dijkstra algorithm
Laboratory Works
- 1.Dynamic memory allocation and deallocation strategies
- 2.Stack operations and queue operations
- 3.Array and linked list implementation of list
- 4.Linked list implementation of stack and queues
- 5.Sorting, searching and hashing algorithms
- 6.Binary search trees and AVL trees
- 7.Graph representation, spanning tree and shortest path algorithms
Text Books
- 1.Y Langsam , MJ Augenstein and A.M , Tanenbaum Data Structures using C and C++ , Prentice Hall India, Second Edition 2015
Reference Books
- 1.Leen Ammeral, Programmes and Data Structures in C, Wiley Professional Computing
- 2.G.W Rowe, Introduction to Data Structure and Algorithms with C and C++ , Prentice Hall India
- 3.R.L Kruse, B.P. Leung, C.L. Tondo, Data Structure and Program Design in Prentice- Hall India