Advanced Data Structures

Home

• Announcements Forum
• Course introduction is here.

  Overview

  Prerequisite

  • Data Structures and algorithms 
  • Basic Mathematics, Geometry, linear algebra, vectors and matrices

  Course Objectives

  • To develop a logic for graphical modelling of the real life problems.
  • To suggest appropriate data structure and algorithm for graphical solutions of the problems. 
  • To understand advanced data structures to solve complex problems in various domains. 
  • To operate on the various structured data.
  • To build the logic to use appropriate data structure in logical and computational solutions. 
  • To understand various algorithmic strategies to approach the problem solution.

  Course Outcomes

  On completion of the course, student will be able to:
  

  • To apply appropriate advanced data structure and efficient algorithms to approach the problems of various domain. 
  • To design the algorithms to solve the programming problems. 
  • To use effective and efficient data structures in solving various Computer Engineering domain problems. 
  • To analyze the algorithmic solutions for resource requirements and optimization 
  • To use appropriate modern tools to understand and analyze the functionalities confined to the data structure usage.

• Syllabus and Notes

• Unit 1

  Unit 2

  Unit 3

  Unit 4

  Unit 5

  Unit 6

  Unit 1

  ×

  Trees

  Tree

  • Basic terminology
  • General tree and its representation
  • representation using sequential and linked organization

  Binary tree

  • Properties
  • converting tree to binary tree
  • binary tree traversals inorder, preorder, post order, level wise - depth first and breadth first
  • Operations on binary tree. 

  Binary Search Tree (BST)

  • BST, BST operations

  Threaded binary tree

  • Concepts
  • threading
  • insertion and deletion of nodes in in-order threaded binary tree
  • in order traversal of in-order threaded binary tree

  Case Study

  • Use of binary tree in expression tree-evaluation and Huffman's coding

  Close

  Unit 2

  ×

  Graphs

  • Basic Concepts, Storage representation, Adjacency matrix, adjacency list, adjacency multi list, inverse adjacency list. 
  • Traversals - depth first and breadth first, Introduction to Greedy Strategy, Minimum spanning Tree, Greedy algorithms for computing minimum spanning tree- Prims and Kruskal Algorithms, Dikjtra's Single source shortest path, Topological ordering. 
  • Case study- Data structure used in Webgraph and Google map

  Close

  Unit 3

  ×

  Hashing

  Hash Table

  • Concepts: hash table, hash function, bucket, collision, probe, synonym, overflow, open hashing, closed hashing, perfect hash function, load density, full table, load factor, rehashing, issues in hashing, 
  • Hash functions: properties of good hash function, division, multiplication, extraction, mid-square, folding and universal
  • Collision resolution strategies: open addressing and chaining
  • Hash table overflow: open addressing and chaining, extendible hashing

  Dictionary

  • Dictionary as ADT, ordered dictionaries.

  Skip List

  • Representation, searching and operations - insertion, removal.

  Close

  Unit 4

  ×

  Search Trees

  • Symbol Table, Representation of Symbol Tables- Static tree table and Dynamic tree table, 
  • Introduction to Dynamic Programming, Weight balanced tree, Optimal Binary Search Tree (OBST), OBST as an example of Dynamic Programming, 
  • Height Balanced Tree- AVL tree

  Close

  Unit 5

  ×

  Indexing and Multiway Trees

  Indexing and Multiway Trees

  • Indexing, indexing techniques

  Types of search tree

  • Multiway search tree
  • B-Tree, B+Tree, Trie Tree, Splay Tree, Red-Black Tree
  • K-dimensional tree, AA tree

  Set

  • Set ADT
  • realization of Set and operations

  Heap

  • Basic concepts
  • realization of heap and operations
  • Heap as a priority queue, heap sort

  Close

  Unit 6

  ×

  File Organization

  • Sequential file organization: concept and primitive operations
  • Direct Access File: Concepts and Primitive operations
  • Indexed sequential file organization: concept, types of indices, structure of index sequential file
  • Linked Organization: multi list files, coral rings, inverted files and cellular partitions
  • External Sort: Consequential processing and merging two lists, multiday merging- a k way merge algorithm

  Close
• Previous Years' Exams
  

  Question Papers

  April 2019October 2018April 2018October 2017April 2017

• Have Doubts?

• Forum

  Ask your doubts regarding the subject here. Discuss exam strategies, scores and latest trends in this forum.