Dr. Sonali Agarwal

Assistant Professor, Indian Institute of Information Technology, Allahabad, India
 

  Contact Details

  Dr. Sonali Agarwal
  Assistant Professor
  Room No.: 2122, CC1 Building

  Indian Institute of Information   Technology Allahabad
  Devghat Jhalwa
  Allahabad (UP) INDIA

  Phone: 0532-2922111
  Web: www.sonaliagarwal.com

  E Mail: sonali@iiita.ac.in
  E Mail: raiagarwalsonali@gmail.com
  


      
  Subjects Taught

Data Structures(IDST232C)


Course Objective
  • Be familiar with basic techniques of algorithm analysis
  • Be familiar with writing recursive methods
  • Master the implementation of linked data structures such as linked lists and binary trees
  • Be familiar with advanced data structures such as balanced search trees, hash tables, priority queues and the disjoint set union/find data structure
  • Be familiar with several sub-quadratic sorting algorithms including quicksort, mergesort and heapsort
  • Be familiar with some graph algorithms such as shortest path and minimum spanning tree
Prerequisites
  • Concepts of Computer Programming, C Language
Syllabus
  • Algorithm

  • Data Structure def, classification, ADT
    Algorithm representation,Pointers, arrays (1-D and n-D), strings
  • Algorithm Cont.

  • Complexity, Elapsed time calculation
  • Stacks

  • Stacks (L2)
    Pre-, in-, post-fix conversions
    Evaluations of expressions
    An introduction to queues and circular queues
  • Recursion

  • Simple recursion
    Fibonacci numbers
    Backtracking: 8-queen problem
  • Searching and Sorting

  • Binary search
    Selection sort, Insertion sort
  • Lists and Queues

  • Linked lists
    Queues
    Circular queues
  • Graph Theory

  • Graphs, trees
    Binary trees, n-ary trees
    Heaps, heapsort
  • Searching and Sorting Cont.

  • Mergesort
    Quicksort
    Quickselect
  • Graph Theory Cont.

  • Priority queues
    Binary search trees
    Trie tree
  • Graph Theory Cont.

  • Disjoint sets
    Kruskal’s MST using disjoint sets
    Dijkstra's Algorithm
  • Hashing

  • Hashing by chaining
    Perfect hashing function
  • Graph Theory Cont

  • Floyd-Warshall's algorithm
    BFS and DFS searches
    AVL trees, B-trees
  • String algorithms

  • Simple string manipulations
    Rabin-Karp approach
  • Tools

  • Operating system: GNU/Linux
    Langauges: C++ (C++98)
    Graph visualization tool: graphviz
    Data and function plotter: gnuplot
  • Books

  • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (3Ed) (Text)
    Data Structures Using C and C++ by YedidyahLangsam, Moshe J. Augenstein and Aaron M. Tenenbaum(Text)
    Professional C++by MarcGregoire, Nicholas A. Solter, Scott J. Kleper (2Ed) (Ref)