Data Structures and Algorithms (CACS201) is a 3-credit subject in BCA 3rd Semester at Tribhuvan University. Below you'll find notes, old question papers, and lab reports aligned with the TU BCA curriculum.
Course Code: CACS201 | Credits: 3 | Semester: 3 | Curriculum: BCA Curriculum 2018
Arrays, stacks, queues, linked lists, trees, graphs, sorting, searching, and algorithm analysis with Big-O notation.
The general objective of this course is to provide fundamental concepts of data structures, different algorithms and their implementation.
Definition, Abstract Data Type, Importance of Data structure
Introduction, Stack as an ADT, POP and PUSH Operation, Stack Application: Evaluation of Infix, Postfix, and Prefix Expressions, Conversion of Expression.
Introduction, Queue as an ADT , Primitive Operations in Queue, Linear and Circular Queue and Their Application, Enqueue and Dequeue, Priority Queue
Introduction, Static and Dynamic List Structure, Array Implementation of Lists, Queue as a list
Introduction, Linked List as an ADT, Dynamic Implementation, Insertion & Deletion of Nodes, Linked Stacks and Queues, Doubly Linked Lists and Its Advantages
Introduction, Principle of Recursion, Recursion vs. Iteration, Recursion Example: TOH and Fibonacci Series, Applications of Recursion, Search Tree
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
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.
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.
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
Deterministic and Non-deterministic Algorithm, Divide and Conquer Algorithm, Series and Parallel Algorithm, Heuristic and Approximate Algorithms