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 BIT department. Aligned with the BIT Curriculum, this course (BIT201) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 80 + 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 Synopsis: This course contains the concepts of different types of data structures and concepts of algorithms and their analysis.
Course Objective: This course aims to provide sufficient theoretical and practical knowledge of data structure and algorithms required to build efficient programs.
Concepts of Data Types, Data Structure, Abstract Data Type and
Background for Data Structure, Definition and use of ADT, Array
as an ADT, Structure, Pointer
Introduction to Algorithm and their properties, Concepts of
Analysis of algorithm with asymptotic notations (Big Oh) and
their properties, time and space complexities
Definition and Primitive Operations, Stack as an ADT, Stack Applications: Evaluation of Infix, Postfix and Prefix
expressions, converting from infix to prefix and postfix.
Definition, Queue as an ADT and Primitive Operations of Linear
and Circular Queue, Application and advantages of Linear, Circular Queue, and
Priority Queue (Ascending and Descending Priority Queue)
Definition and Principle of Recursion, Application of Recursion,
Recursion removal using stack, example of recursion for TOH
Factorial, Fibonacci Sequences, GCD, efficiency of above
List concepts, Definition and List as ADT, Static and Dynamic
List Structure and implementation,
Types of linked list, Operations on Linked List, Singly linked list, Circular Linked List, Doubly Linked List,
Doubly Circular Linked List, Inserting, traversing and deleting
nodes at beginning, end and specified positions in these linked lists, Linked implementation of a stack and queue in singly linked list
Definition and basic terminologies of tree, Binary Tree:
Introduction, Types of Binary Tree, Level and depth, height
balance tree(AVL), Operations in Binary Search Tree (BST): Insertion, Deletion,
Searching, Tree Traversal: Pre-order traversal , In-order traversal (sorted list
of Nodes), Post-order traversal, Applications of Binary Tree (Huff
man tree, expression tree)
Introduction and types of sorting
Algorithm and implementation of Bubble Sort, Insertion Sort,
Selection Sort, Quick Sort, Merge Sort
Comparison and Efficiency of sorting algorithms
Introduction Sequential Search, Binary Search and Tree Search Comparison and Efficiency of Searching, Hashing: hash function, hash table and collision resolution techniques
Definition, Representation of Graph, Types of Graph, Graph Traversal: Depth First Search, Breadth First Search
Spanning Tree, Prim’s Algorithm, Kruskal’s algorithm and Round
Robin Algorithm, Shortest Path Algorithm, Greedy and Dijkstra’s Algorithm
Data Structure and Algorithm is highly practical oriented course. Each unit should include plenty of programming practices. Laboratory work should include implementation of Stack, Queue, Lists, Tree, Graphs, and Recursive functions as well as implementation of Sorting Algorithms and Searching Algorithms. Laboratory exercises can be implemented in high level programming languages like C or C++.
Some important contents that should be included in lab exercises are as follows:
• Write a program to implement array as an ADT.
• Writing programs to implement stack operations
• Writing programs using stack to convert infix expression to postfix/prefix expression
• Write a program to evaluate postfix expression using stack
• Writing programs to implement primitive operation in linear and circular queue.
• Writing recursive programs to implement factorial, Fibonacci sequence, GCD, and Tower of Hanoi algorithms
• Writing programs with dynamic memory allocation and de-allocation
• Writing programs for operation of linear linked list
• Linked list implementation of stack and queue
• Writing programs to implement Binary Search Trees basic operations
• Writing programs to implement sorting algorithms; bubble, insertion, selection, merge and quick sort
• Writing programs to implement: sequential, binary search and hashing
• Writing programs to implement searching, spanning tree and shortest
path algorithms in graph