Course Code: CMPC-201

Credit Hours: 3+1

Prerequisites: Object Oriented Programming

Learning Outcome

At the end of the course the students will be able to:

• Acquire the basic knowledge of data structures & algorithms and understand the concepts of various data structures and use them in different applications.
• Solve, analyze and evaluate the problems using different data structures and algorithms.
• Demonstrate& apply independently the various forms of data structures and algorithms

Reference Materials

1. Data Structures and Algorithms in C++ by Michael T. Goodrich, Roberto Tamassia, and David Mount (2nd Edition) : ISBN-13: 978-0470383278
2. Data Structures and Algorithms in C++ 4th Edition by Adam Drozdek : ISBN-13: 978- 1133608424
3. Data Structures and Algorithm Analysis in Java (3rd Edition) 3rd Edition by Mark A. Weiss : ISBN-13: 978-0132576277
4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, “Introduction to Algorithms”, 2nd Ed, MIT Press, 2001, ISBN 0-07-013151-1  
5. Data Structures and Abstractions with Java (5th Edition) (What's New in Computer Science) 5th Edition by Frank M. Carrano (Author), Timothy M. Henry (Author) : ISBN13: 978-0134831695 
6. Data Structures & Algorithm Analysis in C++ 4th Edition by Mark A. Weiss : ISBN13: 978-0132847377

COURSE CONTENTS

• Introduction to Course, Basic Object Orientation concepts, Properties of Algorithm, Introduction to Algorithm's Performance Analysis and Measurement (Big Oh Notation)
• ADT, Basic Operations, Reading, Writing, Insertion, Deletion, Merging, Binary.  
• Introduction to Sorting types and Techniques, Logical and Algorithmic Implementation of Bubble, Selection Sort, Insertion, Quick Sort, Merge Sort.
• The Stack ADT, Expressions, Postfix Notation, Infix to postfix, postfix evaluation, Applications of stack
• Introduction to Recursion, Examples of Recursion, Writing Recursive Programs
• The Queue ADT and Its Applications, Variation of Queue ADT i.e. Circular and Double Ended Queue
• Priority Queues, Introduction to Pointers, Linear single Link
• Linked Stacks and Queues, Linear Doubly Linked list
• Circular Lists: Implementation of queues and stacks, Doubly Link List
• Introduction to Trees, Tree Terminology, Logical construction and Representation of Trees, Introduction to Binary Tree ADT, Mathematical properties, Linked Implementation of Binary Trees (Insertion, Traversing, Searching and deletion in Binary Trees)
• Binary Search Tree, Implementation and Applications of BSTs
• Heaps and Heaps as Priority Queues, Introduction to Balanced and AVL Trees, Heap Sort.
• Hashing, Overflow Handling, Open Addressing, Chaining
• Introduction to graph and related terminology, Adjacency Matrix representation of graph and Adjacency list
• Elementary Graph Operations, DFS, BFS, Spanning Trees
• Shortest path algorithms: Dijkstra Algorithm, Minimum Cost Spanning Trees.

Evaluation Criteria

Mid Term: 30%

Final exam: 50%

Sessional :20%

Sessional makrs Criteria

• Attendance:  02 Marks
• Quiz  : 04 Marks
• Assignment 1: 02 Marks
• Assignment 2: (Major Assignment Project Base) : 12 Marks