D

Data Structure and Algorithm - Syllabus

10 Chapter 5 Notes 0 Questions
Share Facebook Twitter Linked In Copy Link

1. Course Description

This course offers a thorough examination of the core principles of data structures and algorithms, crucial for computer science students. It starts with an introduction to data structures and advances through abstract data types, algorithm analysis, and design techniques. Topics covered include recursion, stacks, queues, linked lists, trees, sorting, searching, hashing, and graph algorithms, with in-depth explanations and practical examples. Through hands-on exercises, students gain proficiency in designing, implementing, and analyzing these structures and algorithms, with a focus on understanding their efficiency and real-world applications. Upon completion, students are equipped with the essential knowledge and skills to address intricate problems and develop efficient software solutions.

2. General Objectives

  • Provide a comprehensive understanding of fundamental data structures and algorithms.
  • Equip students with proficiency in designing, implementing, and analyzing data structures and algorithms.
  • Foster a deep comprehension of the efficiency and practical implications of different algorithms.
  • Prepare students to tackle complex problems and develop effective software solutions.

3. Specific Objectives and Contents

Specific ObjectivesContent
  • Explain fundamental concepts and importance of data structures.
  • Define and classify different types of data structures.
  • Differentiate   between   data   structures    and abstract data types (ADTs).
  • Analyze and evaluate algorithms in terms of time and space complexity.

Unit I: Introduction to data Structure [3 Hrs.]

  1. Introduction
  2. Definition,
  3. Classification of data structure
  4. Abstract Data Type
  5. Comparison between Data structure and ADT,
  6. Algorithm
  7. Analysis algorithm
  8. Design algorithm
    • Incremental approach
    • Divide and conquer
  9. Performance analysis and measurement
  • Space complexity
  • Time complexity
Discuss the principles and characteristics of recursion. Apply recursion to solve problems and implement algorithms efficiently.

Unit II: Recursion [4 Hrs.]

2.1 Introduction to Recursion

2.2 Principle of Recursion

2.3 Types of Recursion    

  • Direct    
  • Indirect    
  • Linear    
  • Tail recursion

2.4 Recursion Examples    

  • TOH    
  • Fibonacci Series

2.5 Application of Recursion

Become proficient in using stacks and understanding their terms.Implement stack algorithms such as POP and PUSH.Apply stacks in solving problems.Unit III: Stacks [4 Hrs.]3.1 Introduction3.2 Operation stack3.3 Stack terminology3.4 Algorithm for POP and PUSH3.5 Stack Applications    ▪ Stack frame    ▪ Reverse string    ▪ Calculation of postfix expression    ▪ A notation conversion3.6 Algorithm for converting infix expression to postfix form
Understand queue terminology and operations.Implement insertion and deletion algorithms.Recognize queue variations and their applications.Unit IV: Queue [4 Hrs.]4.1 Introduction4.2 Queue terminology4.3 Algorithm for insertion in queue4.4 Algorithm for deletion in queue4.5 Limitation of simple queue4.6 Variation in queue    ▪ Circular queue    ▪ Priority queue4.7 Application of queue
Understand linked list concepts and operations.Define key terms such as data field and link field.Perform operations like insertion, deletion, traversal, searching, etc.Identify types of linked lists.Unit V: Linked List [5 Hrs.]5.1 Introduction5.2 Linked List5.3 Advantage and disadvantage5.4 Key terms    ▪ Data field    ▪ Link field5.5 Representation of linear linked list5.6 Operations of linked list    ▪ Creation    ▪ Insertion    ▪ Deletion    ▪ Traversing    ▪ Searching    ▪ Concatenation    ▪ Display5.7 Types of linked list    ▪ Singly linked list    ▪ Doubly linked list    ▪ Circular linked list    ▪ Circular doubly linked list5.8 Create single linked list5.9 Insertion at specific position5.10 Deletion at specific position5.11 Application: Addition of two polynomials
Understand tree terminology and binary tree concepts.Implement traversal methods.Perform BST operations and understand AVL trees.Unit VI: Trees [7 Hrs.]6.1 Introduction6.2 Tree terminology6.3 Binary tree    ▪ Strictly binary tree    ▪ Complete binary tree    ▪ Extended binary tree6.4 Binary tree representation    ▪ Array representation    ▪ Linked list representation6.5 Create binary tree6.6 Tree traversal    ▪ Preorder    ▪ Inorder    ▪ Postorder6.7 Binary Search Tree (BST)    ▪ Insertion    ▪ Search    ▪ Deletion6.8 Tree height, level, depth6.9 AVL Tree6.10 Huffman Algorithm6.11 B-Tree
Learn sorting algorithms and efficiency analysis.Implement sorting techniques.Analyze performance using Big O notation.Unit VII: Sorting [7 Hrs.]7.1 Introduction7.2 Internal and External sorting7.3 Sorting algorithms    ▪ Bubble sort    ▪ Insertion sort    ▪ Selection sort    ▪ Quick sort    ▪ Merge sort    ▪ Shell sort    ▪ Binary sort7.4 Efficiency of sorting and Big O notation
Learn searching techniques and hashing.Understand collision resolution methods.Compare efficiency of searching methods.Unit VIII: Searching [5 Hrs.]8.1 Introduction8.2 Searching techniques    ▪ Sequential search    ▪ Binary search    ▪ Tree search8.3 Hashing    ▪ Hash functions    ▪ Characteristics of good hash function    ▪ Types of hash function    ▪ Hash tables and applications8.4 Collision resolution techniques    ▪ Linear probing    ▪ Quadratic probing    ▪ Double hashing    ▪ Chaining8.5 Rehashing8.6 Efficiency comparison
Understand graph terminology and types.Learn graph traversal algorithms.Study spanning trees and shortest path algorithms.Unit IX: Graph [7 Hrs.]9.1 Introduction9.2 Graph terminology9.3 Types of graph    ▪ Undirected graph    ▪ Directed graph9.4 Graph representation9.5 Graph traversal    ▪ BFS    ▪ DFS9.6 Spanning tree and MST    ▪ Kruskal’s algorithm    ▪ Prim’s algorithm9.7 Shortest path (Dijkstra’s Algorithm)9.8 Applications
Understand asymptotic notations.Learn limitations of Big O notation.Unit X: Growth Functions [2 Hrs.]10.1 Introduction to asymptotic notation10.2 Big O notation10.3 Omega notation10.4 Theta notation10.5 Limitation of Big O notation
  1. Laboratory Work

It builds the foundation on how to write a program using any high-level language. Hence, this course requires a lot of programming practice so that students will be able to develop good logic building and program developing capability which is essential throughout the course.

Some important contents that should be included in lab exercises are as follows:

  1. Implementations of different operations related to Stack.
  2. Implementation of different operations related to linearand circular queue.
  3. Solution of TOH and Fibonacci Series using Recursion.
  4. Implementations of different operations related to singly linked list.
  5. Implementation of Trees: AVL trees,Balancing AVL.
  6. Implementation of merge sort.
  7. Implementation of differentsearching technique: sequential, Tree and Binary.
  8. Implementation of Graphs: Graph traversal
  9. Implementation of Hashing

Note: Each of the above lab session should cover more than 4 hours of practical work.

  1. Methods of Instruction
  • Lecture
  • Group discussion
  • Question-answers
  • Demonstration and discussion
  • Presentations
  • Guest lectures
  • Group work/project work
  • Problem solving
  • Simulation
  • Tutorials
  1. Evaluation systemand Student’s Responsibilities Evaluation System

In addition to the formal exam(s), the internal evaluation of a student may consist of quizzes, assignments, lab reports, projects, class participation, etc. The tabular presentation of the internal evaluation is as follows.

External EvaluationMarksInternal EvaluationWeightMarks

 

Semester-End examination

 

50

Theory 

 

30

Attendance & Class Participation10%
Assignments20%
Presentations/Quizzes10%
  Internal Assessment60% 
Practical  
Attendance & Class Participation10%

 

 

20

Lab Report/Project Report20%
Practical Exam/Project Work40%
Viva30%
Total External50Total Internal 50
Full Marks: 50 + 50 = 100

 

Student’s Requirements

Each student must secure at least 45% marks separately in both internal assessment and practical evaluation with 80% attendance in the class in order to appear in the Semester End Examination. Failing to get such score will be given NOT QUALIFIED (NQ) to appear the Semester-End Examinations. Students are advised to attend all the classes, formal exam, test, etc. and complete all the assignments within the specified time period. 

Students are required to complete all the requirements defined for the completion of the courses.

  1. Prescribed Books and References Text Books

Langsam, Y., Augenstein, M. J., & Tanenbaum, A. M. (2019). Data Structures using C and C++. PHI

Reference Books

  1. Rowe, G. W. (1997).Introduction to Data Structures and Algorithms with C and C++. PHI
  2. Lafore, R. (2002). Data Structures and Algorithms in Java. Sams Publishing
  3. Baluja, G. S. (2016).Data Structures throughC. Dhanpat Rai & Co