SPPU SE IT syllabus

SPPU · Second Year Information Technology · 2024 Pattern (Revised)

Data Structures & Algorithms

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

All notes for this subject
  1. Unit 1: Introduction to Data Structures & Algorithms

    7 hours

    Data objects, types and abstract data types; primitive and non-primitive, static and dynamic, persistent and ephemeral structures; algorithms, their characteristics and design strategies; time and space complexity, asymptotic notation, best, average and worst cases, the step-count method; linear and binary search; bubble, selection and insertion sort.

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

    • Data structures and abstract data types
    • Classification of data structures
    • Algorithms and design strategies
    • Time and space complexity, asymptotic notation
    • Step-count method and analysing loops
    • Linear and binary search
    • Bubble, selection and insertion sort
  2. Unit 2: Linear Data Structures

    7 hours

    Singly, doubly and circular linked lists and the list ADT; stacks with arrays and linked lists, implicit and explicit stacks, recursion, infix to postfix and prefix and their evaluation; queues with arrays and linked lists, circular queue and deque.

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

    • Singly linked list
    • Doubly and circular linked lists
    • Stack implementation with arrays and linked lists
    • Stack applications: recursion and expression conversion
    • Evaluating postfix and prefix expressions
    • Queue, circular queue and deque
  3. Unit 3: Non-linear Data Structures

    9 hours

    Binary trees, their representation and inorder, preorder and postorder traversal; threaded binary trees; BSTs; converting general trees to binary trees; AVL and 2-3 trees; graph representation, BFS and DFS, spanning trees, shortest paths, Prim's and Kruskal's; min and max heaps, heap sort.

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

    • Binary trees and their representation
    • Binary tree traversals
    • Threaded binary trees
    • Binary search trees
    • AVL and 2-3 trees
    • Graph representation, BFS and DFS
    • Minimum spanning trees: Prim's and Kruskal's
    • Shortest path algorithms
    • Heaps and heap sort
  4. Unit 4: Hashing and String Processing

    8 hours

    Hash functions and collision handling by chaining and open addressing; naïve, Rabin–Karp and KMP string matching; applications in social-network graphs and AI search.

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

    • Hash functions
    • Collision handling: chaining and open addressing
    • Naïve string matching
    • Rabin–Karp algorithm
    • Knuth–Morris–Pratt algorithm
  5. Unit 5: Advanced Algorithms

    7 hours

    Divide and conquer: merge sort, quick sort, matrix multiplication; greedy: activity selection, fractional knapsack, Huffman coding; dynamic programming: 0/1 knapsack, LCS, Floyd–Warshall.

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

    • Divide and conquer: merge sort and quick sort
    • Divide and conquer matrix multiplication
    • Greedy: activity selection and fractional knapsack
    • Huffman coding
    • Dynamic programming: 0/1 knapsack
    • Longest common subsequence
    • Floyd–Warshall algorithm

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