Data Structures and Algorithms - Syllabus
Embark on a profound academic exploration as you delve into the Data Structures and Algorithms course (DSA) within the distinguished Tribhuvan university's BCA department. Aligned with the BCA Curriculum, this course (CACS201) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 60 + 20 + 20 marks system, coupled with a challenging passing threshold of , propels students to strive for excellence, fostering a deeper grasp of the course content.
This 3 credit-hour journey unfolds as a holistic learning experience, bridging theory and application. Beyond theoretical comprehension, students actively engage in practical sessions, acquiring valuable skills for real-world scenarios. Immerse yourself in this well-structured course, where each element, from the course description to interactive sessions, is meticulously crafted to shape a well-rounded and insightful academic experience.
Course Description
This course includes fundamental concept 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.
Units
Definition, Abstract Data Type, Importance of Data structure
The Stack
Introduction, Stack as an ADT, POP and PUSH Operation, Stack Application: Evaluation of Infix, Postfix, and Prefix Expressions, Conversion of Expression.
Queue
Introduction, Queue as an ADT , Primitive Operations in Queue, Linear and Circular Queue and Their Application, Enqueue and Dequeue, Priority Queue
List
Introduction, Static and Dynamic List Structure, Array Implementation of Lists, Queue as a list
Linked Lists
Introduction, Linked List as an ADT, Dynamic Implementation, Insertion & Deletion of Nodes, Linked Stacks and Queues, Doubly Linked Lists and Its Advantages
Recursion
Introduction, Principle of Recursion, Recursion vs. Iteration, Recursion Example: TOH and Fibonacci Series, Applications of Recursion, Search Tree
Trees
Introduction, Basic Operation in Binary tree, Tree Search and Insertion/Deletion, Binary Tree Transversals(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
Sorting
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'O'Notation.
Searching
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.
Graphs
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
Algorithms
Deterministic and Non-deterministic Algorithm, Divide and Conquer Algorithm, Series and Parallel Algorithm, Heuristic and Approximate Algorithms
Lab works
Laboratory Works
There shall be 10 lab exercises based on C or Java
I. Implementations of different operations related to Stack
2. Implementations of different operations related to linear and circular queues
3. Solutions of TOH and Fibonacci Series using Recursion
4. Implementations of different operations related to linked list: singly and doubly linked
5. Implementation of trees: AVL trees, Balancing of AVL
6. Implementation of Merge sort
7. Implementation of different searching technique: sequential, Tree and Binary
8. Implementation of Graphs: Graph traversals
9. Implementation of Hashing
10. Implementations of Heap