Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Bachelors Level/Second Year/Third Semester/Science bit/third semester/data structures and algorithms/syllabus

Bachelors In Information Technology

Institute of Science and Technology, TU

Nature of the course: (Theory+Lab)

F.M: 60+20+20 P.M: 24+8+8

Credit Hrs: 3Hrs

Data Structures and Algorithms [BIT201]
Course Objective
i.
This course aims to provide sufficient theoretical and practical knowledge of data structure and algorithms required to build efficient programs.
Course Description

This course contains the concepts of different types of data structures and concepts of algorithms and their analysis.

S1:Background and Concept of Data Structures[2]
1
Concepts of Data Types, Data Structure, Abstract Data Type and their uses
2
Background for Data Structure, Definition and use of ADT, Array as an ADT, Structure, Pointer
S2:Algorithms[2]
1
Introduction to Algorithm and their properties, Concepts of Analysis of algorithm with asymptotic notations (Big Oh) and their properties, time and space complexities
S3:Stack[4]
1
Definition and Primitive Operations, Stack as an ADT
2
Stack Applications: Evaluation of Infix, Postfix and Prefix expressions, converting from infix to prefix and postfix.
S4:Queue[3]
1
Definition, Queue as an ADT and Primitive Operations of Linear and Circular Queue.
2
Application and advantages of Linear, Circular Queue, and Priority Queue (Ascending and Descending Priority Queue)
S5:Recursion[2]
1
Definition and Principle of Recursion, Application of Recursion, Recursion removal using stack, example of recursion for TOH Factorial, Fibonacci Sequences, GCD, efficiency of above recursive algorithms
S6:List[9]
1
List concepts, Definition and List as ADT, Static and Dynamic List Structure and implementation,
2
Types of linked list, Operations on Linked List
3
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
4
Linked implementation of a stack and queue in singly linked list
S7:Tree[7]
1
Definition and basic terminologies of tree, Binary Tree: Introduction, Types of Binary Tree, Level and depth, height balance tree(AVL)
2
Operations in Binary Search Tree (BST): Insertion, Deletion, Searching
3
Tree Traversal: Pre-order traversal , In-order traversal (sorted list of Nodes), Post-order traversal, Applications of Binary Tree (Huff man tree, expression tree)
S8:Sorting[6]
1
Introduction and types of sorting
2
Algorithm and implementation of Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort
3
Comparison and Efficiency of sorting algorithms
S9:Searching[5]
1
Introduction
2
Sequential Search, Binary Search and Tree Search
3
Comparison and Efficiency of Searching
4
Hashing: hash function, hash table and collision resolution techniques
S10:Graph[5]
1
Definition, Representation of Graph, Types of Graph
2
Graph Traversal: Depth First Search, Breadth First Search
3
Spanning Tree, Prim’s Algorithm, Kruskal’s algorithm and Round Robin Algorithm
4
Shortest Path Algorithm, Greedy and Dijkstra’s Algorithm
References
1.
Data structure using C and C++, Langsam, Augenstein, Tenenbaum
2.
Horowitz and Sahni, Fundamentals of Data Structures
3.
Aho, Hopcroft and Ullman, Data Structure and Algorithms
Labrotary Work
Unit 1,3
1.
Write a program to implement array as an ADT.
2.
Writing programs to implement stack operations
3.
Writing programs using stack to convert infix expression to postfix/prefix expression
4.
Write a program to evaluate postfix expression using stack
Unit 4
1.
Writing programs to implement primitive operation in linear and circular queue.
Unit 5
1.
Writing recursive programs to implement factorial, Fibonacci sequence, GCD, and Tower of Hanoi algorithms
Unit 6
1.
Writing programs with dynamic memory allocation and de-allocation
2.
Writing programs for operation of linear linked list
3.
Linked list implementation of stack and queue
Unit 7
1.
Writing programs to implement Binary Search Trees basic operations
Unit 8
1.
Writing programs to implement sorting algorithms; bubble, insertion, selection, merge and quick sort
Unit 9
1.
Writing programs to implement: sequential, binary search and hashing
Unit 10
1.
Writing programs to implement searching, spanning tree and shortest path algorithms in graph