Course Title: Data Structures and Algorithms (3 Cr.)
Course Code: CACS201
Year/Semester: Semester
Class Load: 6 Hrs. / Week (Theory: 3 Hrs., Practical: 3 Hrs.)
Course Description
This course includes fundamental concepts of data structures such as stack, queue, list, linked list, trees and graph; application of these data structures along with several algorithms.
Course Objectives
The general objective of this course is to provide fundamental concepts of data structures, different algorithms and their implementation.
Course Contents
Unit 1: Introduction to data structure [2 Hrs.]
Definition, Abstract Data Type, Importance of Data structure.
Unit 2: The Stack [3 Hrs.]
Introduction, Stack as an ADT, POP and PUSH Operation, Stack Application: Evaluation of infix, Postfix, and Prefix Expressions, Conversion of Expression.
Unit 3: Queue [3 Hrs.]
Introduction, Queue as an ADT, Primitive Operations in Queue, Linear and Circular Queue and Their Application, Enqueue and Dequeue, Priority Queue
Unit 4: List [2 Hrs.]
Introduction, Static and Dynamic List Structure, Array Implementation of Lists, Queues as a List
Unit 5: Linked Lists [5 Hrs.]
Introduction, Linked List as an ADT, Dynamic Implementation, Insertion & Deletion of Node To and From a List, Insertion and Deletion After and Before Nodes, Linked Stacks and Queues, Doubly Linked Lists and Its Advantages
Unit 6: Recursion [4 Hrs.]
Introduction, Principle of Recursion, Recursion vs. IteratiOn, Recursion Example: TOII and Fibonacci Series, Applications of Recursion, Search Tree
Unit 7: Trees [5 Hrs.]
Introduction, Basic Operation in Binary tree, Trec Search and Insertion; Deletion, Binary Tree Traversals (pre-order, post-order and in-order), Tree Height, Level, and Depth, Balanced Trees: AVL Balanced Trees, Balancing Algorithm, The Huffman Algorithm, Game tree, B-Tree.
Unit 8: Sorting 5 Hrs.
Introduction, Internal and External Sort. Insertion and Selection Sort, Exchange Sort, Bubble and Quick Sort, Merge and Radix Sort, Shell Sort, Binary Sort, Heap Sort as Priority Queue, Efficiency of Sorting, Big or Notation
Unit 9: Searching [5 Hrs.]
Introduction to Search Technique; essential of search, Sequential search, Binary search, Tree search, General search tree, Hashing: Hash function and hash tables, Collision resolution technique, Efficiency comparisons of different search technique
Unit 10: Graphs [5 Hrs.]
Introduction, Graphs as an ADT, Transitive Closure, Warshall’s Algorithm, Types of Graph, Graph Traversal and Spanning Forests, Kruskal’s and Round-Robin Algorithms, Shortest-path Algorithm, Greedy Algorithm. Dijkstra’s Algorithm
Unit 11: Algorithms [5 Hrs.]
Deterministic and Non-deterministic Algorithm, Divide and Conquer Algorithm, Series and Parallel Algorithm, Heuristic and Approximate Algorithms
Laboratory Works
There shall be 10 lab exercises based on C or Java
– Implementations of different operations related to Stack
– Implementations of different operations related to linear and circular queues
-Solutions of DOH and Fibonacci Series using Recursion
-Implementations of different operations related to linked list: singly and doubly linked
-Implementation of trees: AVL trees, Balancing of AVI-
-Implementation of Merge sort
-Implementation of different searching technique: sequential, Tree and Binary
-Implementation of Graphs: Graph traversals
-Implementation of Hashing
-Implementations of Heap
Teaching Methods
The general teaching pedagogy includes class lectures, group discussions, case studies, guest lectures, research work, project work, assignments (theoretical and practical), and examinations (mitten and verbal), depending upon the nature of the topics. The teaching faculty will determine the choice of teaching pedagogy as per the need of the topics.
Evaluation:
Text Book
– Y. Langsam, M.J. Augenstein and A. M. Tenenbaum, “Data Structures using C and C++”, PHI
Reference Books
– G. W. Rowe, “Introduction to Data Structure and Algorithms with C and C++”, PHI
– Robert Lafore, Data Structures and Algorithms in Java (2nd Edition), San–4,s Publishing
To download full Syllabus CLICK HERE