Data Structure and Algorithm

https://surajawal.pythonanywhere.com/syllabus/4/data-structure-and-algorithm/

IOE Syllabus of Data Structure and Algorithm

Subject Code : CT552

Semester : 4

Data Structure And Algorithm (DSA) (Course Code: CT 552) has Lecture : 3, Tutorial : 0, Practical : 3 and is introduced in BE Computer course for II Year II Part with the objective of providing fundamental knowledge of various data structures and their implementation and to provide the fundamental knowledge of various algorithms and their analysis. The following syllabus of Data Structure And Algorithm is according to latest update of IOE Syllabus for new course i.e. after 066 batch.

---

1. concept of data structure

- Data Types, Data Structure and abstract Data Types

- Introduction to Algorithm

2. The Stack and Queue

- Stack Operation

- Stack Application: Evaluation of Infix, Postfix and Prefix Expressions

- Operation in Queue: Enqueue and Dequeue

- Linear and Circular queue

- Priority Queue

3. LIst

- Definition of List

- Static and Dynamic List

- Array Implementation of List

- Queues as a list

4. LInked List

- Dynamic Implementatin of Linked List

- Operation in Linked List

- Linked Stack and Queue

- Doubly Linked List and its Applications

5. Recursion

- Principle of Recursion

- TOH and Fibonacci Sequence

- Application of Recursion

6. Trees

- Concept of Tree

- Operation in Binary Tree

- Tree Search, Insertion and Deletion

- Tree Traversal - Pre order, Post order and In order

- Height, Level and Depth of a Tree

- AVL Balanced Tree and Balancing Algorithm

- Huffmann Algorithm

- B Tree

- Red Black Tree

7. Sorting

- Types of Sorting

- Insertion and Selection Sort

- Exchange Sort

- Merge and Redix Sort

- Shell Sort

- Heap Sort as a Priority Queue

- Big 'O' Notation and Efficiency of Sorting

8. Searching

- Searching Techniques

- Sequential, Binary and Tree Search

- General Search Tree

- Hashing: Hash function and table; Collision Resolution Technique

9. Growth Functions

- Introduction to Growth Function

10. Graphs

- Representation and Application of Graph

- Transitive Closure

- Warshall's Algorithm

- Types of Graph

- Graph Traversal and Spanning Forests

- Depth First and Breadth First Traversal

- Depth First and Breadth First Topological Sorting

- Minimum Spanning Tree: Prim's, Kruskal's and Round Robin Algorithms

- Shortest Path Algorithm: Greedy and Dijkstra's Algorithm

---

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”, PHI
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”, PHI
3. G.W. Rowe, “Introduction to Data Structure and Algorithms with C and C++”, PHI
4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”, PHI
5. G. Brassard and P. Bratley, “Fundamentals of Algorithms”, PHI

---

Practicals:

There shall be 10 to 12 lab exercises based on C or C++
1. Implementation of stack
2. Implementations of linear and circular queues
3. Solutions of TOH and Fibonacci sequence by Recursion
4. Implementations of linked list: singly and doubly linked list
5. Implementation of trees: AVL trees, and balancing
6. Implementation of Merge sort
7. Implementation of search: sequential, Binary and Tree search
8. Implementation of Graphs: Graph Traversals
9. Implementation of hashing
10. Implementation of Heap

---

Marking Scheme:

Chapter	Credit Hours	Marks Distribution
1	2	4
2	6	10
3	3	6
4	4	10
5	4	8
6	7	12
7	5	8
8	5	8
9	2	4
10	6	10

There may be minor deviation in mark distribution*