SPPU SE AI&DS syllabus

SPPU · Second Year Artificial Intelligence and Data Science · 2024 Pattern (Revised)

Data Structures

PCC-201-AID · Semester III · 3 credits · CCE 40 + end-semester 60

All notes for this subject
  1. Unit 1: Searching, Sorting and Hashing

    9 hours

    Types of data structures; space and time complexity, Big-O, Theta and Omega, the step-count method; sequential and binary search; insertion, bubble, selection, merge, quick and radix sort; hash tables and functions, chaining, linear and quadratic probing, double hashing and overflow.

    Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)

    • Data structures and their types
    • Time and space complexity
    • Asymptotic notations
    • Sequential and binary search
    • Insertion, bubble and selection sort
    • Merge sort and quick sort
    • Radix sort
    • Hashing and collision resolution
  2. Unit 2: Memory Allocation and Linked Lists

    9 hours

    Static and dynamic allocation; linked lists through dynamic memory; the list ADT; singly, circular, doubly and doubly circular lists; create, traverse, search, insert, delete, sort and concatenate; polynomial addition; generalised linked lists.

    Marks: 12 in the end-semester exam · CCE: Unit test (15 marks, Units 1 & 2)

    • Static and dynamic memory allocation
    • Singly linked lists
    • Circular linked lists
    • Doubly linked lists
    • Polynomial addition with linked lists
    • Generalised linked lists
  3. Unit 3: Stacks and Queues

    9 hours

    The stack ADT and its array representation; expression conversion and evaluation; recursion; the queue ADT and its array representation; circular queues, deques and priority queues.

    Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)

    • Stack ADT and operations
    • Expression conversion and evaluation
    • Recursion
    • Queue ADT and operations
    • Circular queues
    • Deques and priority queues
  4. Unit 4: Trees

    9 hours

    Tree terms, representations and traversals; binary trees and binary search trees; threaded BSTs; optimal BSTs; AVL trees; heaps.

    Marks: 12 in the end-semester exam · CCE: Assignments or case study (15 marks, Units 3 & 4)

    • Tree terminology and representation
    • Binary tree traversals
    • Binary search trees
    • Threaded binary trees
    • Optimal binary search trees
    • AVL trees
    • Heaps
  5. Unit 5: Graphs

    9 hours

    Adjacency matrix and list; DFS and BFS; Prim's and Kruskal's minimum spanning trees; Dijkstra's shortest paths; Floyd–Warshall; topological ordering.

    Marks: 12 in the end-semester exam · CCE: Seminar, open-book test or quiz (10 marks, Unit 5)

    • Graph representation
    • DFS and BFS
    • Prim's and Kruskal's algorithms
    • Dijkstra's algorithm
    • Floyd-Warshall algorithm
    • Topological sorting

Unit contents are summarised from the official SPPU syllabus . AiCanCode.org is not affiliated with Savitribai Phule Pune University.