Get all semester notes for Computer Engineering here.

# Data Structures and Algorithms PDF Notes for Pokhara University

## Data Structure and Algorithms ( DSA )

A computer program is a set of instructions designed to carry out a certain activity. A computer program may need to store, retrieve, and compute data in order to accomplish this.

A specified location that can be used to store and arrange data is called a data structure. Additionally, an algorithm is a series of procedures used to solve a certain problem. We may create computer programs that are effective and optimized by learning data structures and algorithms.

Course Contents :
1. Introduction of Data Structure (2hrs)
Concept of data structure, Abstract data type, Implementation of data structure.

2. The Stack (3hrs)
Definition, Stack as an ADT, POP and PUSH operation, Stack application: Evaluation of Infix, Postix, and prefix expressions.

3. Queue (3hrs)
Definition, Queue as ADT, Primitive operations in the queue, Linear and circular queue and their application, Enqueue and Dequeue, Priority queue.

4. List (5hrs)
Definition, Static and dynamic list structure, Array implementation of lists, Queues as a list.

Definition and link list as an ADT, Dynamic implementation, Basic operations in a linked list: node insertion, deletion, insertion and deletion after and before nodes, Linked stacks and Queues, Doubly linked lists and its advantages.

6. Recursion (4hrs)
Principle of recursion, Comparison between recursion and iteration, Recursion example, TOH and Fibonacci sequence, Applications of recursion, Search tree.

7. Tree (5hrs)
Concept and definitions, Basic operation in Binary tree, Tree search and insertion/deletions, Binary tree traversal (Preorder, Post-order and in-order), Tree height, level and depth, Balanced trees, AVL balanced trees, Balancing algorithm, The Huffman algorithm, game tree, B-Tree.

8. Sorting (5hrs)
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 a priority queue, Efficiency of sorting, Big ‘O’ notion.

9. Searching (5hrs)
Searching 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 techniques.

10. Graph (7hrs)
Representation and applications, Graph as an ADT, Transitive closure, Warshall’s algorithm, Graphs types, Graphs traversal and Spanning forest, Kruskal’s and Round Robin algorithms, Shortest-path algorithm, Greedy algorithm, Dijkstra’s Algorithm.

11. Algorithms (5hrs)
Deterministic and no-deterministic algorithm, Divide and conquer algorithm, Series and parallel algorithm, and Heuristic and Approximate algorithms.