PROGRAM CORE
Credit hour : 3
Synopsis
Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently. Data structures have a wide and diverse scope of usage across the fields of Computer Science.
This course provides a solid foundation in the basic concepts of data structures and algorithms. This course makes it easy to select and design data structures and algorithms in a problem-solving manner and clear concepts on the correctness of algorithms and their computational complexities. This course covers data types, linear and nonlinear data structures as well as various searching and sorting algorithms.
Course Outcome
i. Ability to analyze the performance of computer programs in terms of space and time complexity.
ii. Ability to appropriately apply various abstract data types in computer programs.
iii. Ability to apply and evaluate algorithms to solve computational problems.
Course Content
Analysis of Algorithms
Time complexity
Asymptotic Notation
Master Theorem
Basic Automata Computability and Complexity
Finite-state machines
Regular expressions
The halting problem
Context Free Grammar
P vs NP
NP-Completeness
Arrays
Array representation
Array operations
Types of arrays
Complexity analysis of array
Stacks
LIFO principles of stack
Operations of stack
Complexity analysis of stack
Applications of stack data structure
Queues
Basic operations of queue
Types of queue
Complexity analysis of queue
Applications of queue data structure
Linked List
Basic operations of linked list
Types of linked list
Complexity analysis of linked list
Applications of linked list data structure
Tree and Binary Tree
Tree data structure.
Basics of Binary Tree
Binary Tree Traversals
Complexity analysis of Binary Tree
Applications of Binary Tree
Graphs
Definition of Graphs
Graph Terminologies
Graph Implementation
Depth First Search vs Breadth First Search
Minimum Spanning Tree
Dijkstra Algorithm
AVL Tree
Balance Factor
Basic Operation of AVL Tree
Complexity Analysis of AVL Tree
Applications of AVL Tree
Hash Tables
Basics of Hash Tables
Hash Collisions
Good Hash Functions
Applications of Hash Tables
Searching
Introduction to searching
Searching Techniques
Applications of Searching Techniques
Sorting
Introduction to sorting
Sorting techniques
Applications of Sorting Techniques
References
Pai, G.A.V. (2017), Data Structures and Algorithms (Concepts, Techniques and Applications), McGraw-Hill Education.
Thareja, R. (2018), Data Structures Using C, 2nd Edition, Oxford University Press
Lee, K.D., Hubbard S. (2015), Data Structures and Algorithms with Python, Springer.
Karumanchi, N. (2017), Data Structures and Algorithms Made Easy, 5th Edition, CareerMonk Publications
Wengrow J.(2020). A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Level Up Your Core Programming Skills 2nd Edition, Pragmatic Bookshelf.
Skena, S.S. (2020), Algorithm Design Manual, 3nd Edition, Springer
Prepared By:
Ts. Dr. Hasneeza Liza Zakaria