SGBAU SY IT syllabus

SGBAU · Second Year B.E. Information Technology · NEP 2020

Data Structures

4IT209PC · Semester IV · 3 credits · IE 40 + ESE 60

Radix sort, header and two-way linked lists and record structures are in the syllabus but have no separate notes yet.

  1. Unit 1: Introduction to Data Structures

    7 hours

    Data structure operations, algorithmic notation and complexity of algorithms; string processing: storing strings, string operations, word processing and pattern-matching algorithms.

    Examined in the 60-mark end-semester paper

    • Data structures and abstract data types
    • Algorithms and design strategies
    • Time and space complexity, asymptotic notation
    • Naïve string matching
    • Knuth–Morris–Pratt algorithm
  2. Unit 2: Arrays & Record Structure

    7 hours

    Linear arrays, their memory representation, traversal, insertion and deletion; bubble sort; linear and binary search; multi-dimensional and pointer arrays; record structures.

    Examined in the 60-mark end-semester paper

    • Classification of data structures
    • Bubble, selection and insertion sort
    • Linear and binary search
  3. Unit 3: Linked Lists

    7 hours

    Memory representation, traversal and searching of linked lists; memory allocation and garbage collection; insertion and deletion; header and two-way linked lists.

    Examined in the 60-mark end-semester paper

    • Singly linked list
    • Doubly and circular linked lists
  4. Unit 4: Stacks & Queues

    7 hours

    Sequential representation of stacks; arithmetic expressions and Polish notation; quick sort, recursion and the Tower of Hanoi; queues, deques and priority queues.

    Examined in the 60-mark end-semester paper

    • Stack implementation with arrays and linked lists
    • Stack applications: recursion and expression conversion
    • Evaluating postfix and prefix expressions
    • Recursion and the Tower of Hanoi
    • Queue, circular queue and deque
    • Priority queues
  5. Unit 5: Trees

    7 hours

    Binary trees, their memory representation and traversal; header nodes; binary search trees; heaps and heap sort; path length and Huffman's algorithm.

    Examined in the 60-mark end-semester paper

    • Binary trees and their representation
    • Binary tree traversals
    • Binary search trees
    • Heaps and heap sort
    • Huffman coding
  6. Unit 6: Graphs & Sorting Algorithms

    7 hours

    Memory representation of graphs, Warshall's algorithm, graph operations, breadth-first and depth-first search; insertion, selection, radix and merge sort.

    Examined in the 60-mark end-semester paper

    • Graph representation, BFS and DFS
    • Closures and Warshall's algorithm
    • Bubble, selection and insertion sort
    • Divide and conquer: merge sort and quick sort

Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).