11:56 AM
Course Title: Data
Structures and Algorithms
Course No. : ICT. Ed. 435
Nature of course: Theoretical
+ Practical
Level: B. Ed
Credit Hour: 3 hours (2T+1P)
Semester: Third
Teaching Hour: 80 hours (32+48)
*******
Contents
Unit 1: Introduction to Data
Structures & Algorithms(6)
1.1 Data types, Data structure and Abstract date
type
1.2 Memory allocation in C
1.3 Introduction to Algorithms
1.4 Role of algorithms in Computing
1.5 Asymptotic notations and common functions
Lab:
Write a program to implement dynamic
memory management functions(malloc(),calloc(),realloc() and free())
Unit 2: Stacks
(5)
2.1 Definition
2.2 Stack as an ADT
2.3 Stack operation
2.4 Stack application: Evaluation of Infix,
Postfix and Prefix expressions
Lab:
Write a program to implement stack operations
Unit 3: Queues (6)
3.1 Definition
3.2 Queue as an ADT
3.3 Primitive operations in queue: Enqueue and
Dequeue
3.4 Linear and Circular Queue
3.5 Priority queue.
Lab:
Write a program to implement linear and circular queue operations
Unit 4: List (4)
4.1 Definition
4.2 Static and dynamic list structure
4.3 Array implementation of lists
4.4 Queues as list
Unit 5: Linked lists
(8)
5.1 Definition and Linked List as an ADT
5.2 Applications and Types of Linked List
5.3 Basic operations in Linked List: creation,
node insertion and deletion from beginning, end and specified position
5.4 Stack and Queue as a circular list
Lab-1:
Write a program to implement singly and doubly linked list operations
Lab-2:
Write a program to implement stack and queue as linked list
Unit 6: Recursion
(5)
6.1 Principle of recursion
6.2 Comparison between recursion and iteration
6.3 Tower of Hanoi(TOH) and Fibonacci sequence
6.4 Applications and Efficiency of recursion
Lab-1:
Write a program to solve the problem of TOH
Lab-2:
Write a program to print Fibonacci series
Lab-3:Write
a program to calculate factorial
Lab-4:
Write a program to calculate gcd of two numbers
Unit 7: Trees
(10)
7.1 Concept and definitions
7.2 Basic operation in binary tree
7.3 Tree search, insertion/deletion, traversals
(pre-order, post-order and in-order )
7.4 Binary Search Tree
7.5 Tree height, level and depth
7.6 AVL tree and Balancing algorithm
7.7 The Huffman algorithm
7.8 B- Tree
7.9 Applications of tree
Lab:
Write a program to insert, delete, search and display(pre-order, in-order,
post-order) items in BST
Unit 8: Sorting
(10)
8.1 Introduction and Types of sorting: Internal
and External sort
8.2 Exchange sorts: Bubble sort and Quick sort
8.3 Selection and Tree sorting: Selection sort,
Binary tree sort, Heap sort, and Heap as a priority queue
8.4 Insertion Sorts: Insertion sort and Shell
Sort
8.5 Merge sort and Radix sort
8.6 Big ‘O’ notation and Efficiency of sorting
Lab:
Write a program to implement:
a) Bubble sort b) Selection sort c)
Insertion sort
d)
Quick sort e) Merge sort f) Heap sort
Unit 9: Searching
(6)
9.1 Introduction to searching
9.2 Sequential search, Binary search, Tree
search, General search tree and Interpolation search
9.3 Hashing : Hash function and hash tables
9.4 Collision resolution technique
9.5 Efficiency comparisons of different search
technique
Lab:
Write a program to implement:
a) Sequential search
b) Binary search
Unit 10: Graphs
(12)
10.1 Representation and applications
10.2 Graphs as an ADT
10.3 Transitive closure
10.4 Warshall’s Algorithm
10.5 Shortest path algorithm
10.6 Linked representation of graph: Dijkstra's
Algorithm, Organizing the set of graph nodes, Application to scheduling
10.7 Graph Traversal Algorithms: Depth First
Traversal and Breadth First Traversal
10.8 Minimum spanning trees: Prim’s, Kruskal’s and
Round-Robin algorithms
Lab:
Write a program to implement graph traversal algorithms(BFS and DFS)
Unit 11: Algorithms
(8)
11.1 Analyzing and Designing algorithms
11.2 Greedy, Dynamic programming and Back tracking
Algorithms
11.3 Divide and conquer algorithm
11.4 Deterministic and non-deterministic algorithm
11.5 Serial and Parallel algorithm
11.6 Heuristic and Approximate algorithm