Advanced Data Structures
Course Code: PGA123 Credits: 4:0:0
Prerequisites:Nil Contact Hours: 56
Course Coordinator/s: Dr. Mohana Kumar S
Contents
UNIT-I DICTIONARIES AND HASHING
Dictionaries: Definition, Dictionary Abstract Data Type, Implementation of Dictionaries.
Hashing: Review of Hashing, Hash Function, Collision Resolution Techniques in Hashing,
Separate Chaining, Open Addressing, Linear Probing, Quadratic Probing, Double Hashing,
Rehashing, Extendible Hashing.
UNIT-II SKIP LISTS
Skip Lists: Need for Randomizing Data Structures and Algorithms, Search and Update
Operations on Skip Lists, Probabilistic Analysis of Skip Lists, Deterministic Skip Lists.
UNIT-III TREES
Trees: Binary Search Trees, AVL Trees, Red Black Trees, 2-3 Trees, B-Trees, Splay Trees
UNIT-IV TEXT PROCESSING
Text Processing: Sting Operations, Brute-Force Pattern Matching, The BoyerMoore
Algorithm, The Knuth-Morris-Pratt Algorithm, Standard Tries, Compressed Tries, Suffix
Tries, The Huffman Coding Algorithm, The Longest Common Subsequence Problem (LCS),
Applying Dynamic Programming to the LCS Problem.
UNIT-V COMPUTATIONAL GEOMETRY
Computational Geometry: One Dimensional Range Searching, Two Dimensional Range
Searching, Constructing a Priority Search Tree, Searching a Priority Search Tree, Priority
Range Trees, Quad trees, k-D Trees. Recent Trends in Hashing, Trees, and various
computational geometry methods for efficiently solving the new evolving problem.
Text Books:
1. Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, 2nd Edition, Pearson,
2004.
2. M T Goodrich, Roberto Tamassia, Algorithm Design, John Wiley, 2002
References Text Book
1. Fundamentals of Computer Algorithms, Ellis Horowitz, SatrajSahani and Rajasekharam,
2nd Edition, 2009, University Press Pvt. Ltd.
2. Advanced Data Structures, Reema Thareja, S. Rama Sree, Oxford University Press, 2018
Random Process
Course Code: PGAE151 Credits: 3:0:0
Prerequisites:Nil Contact Hours: 42
Course Coordinator/s: Dr. Mohana Kumar S
Contents
Unit 1
INTRODUCTION TO PROBABILITY THEORY: Experiments, sample space, Events,
Axioms, Assigning probabilities, Joint and conditional probabilities, Baye’s Theorem,
Independence, Discrete Random Variables, Engg Example.
Unit 2
Random Variables, Distributions, Density Functions: CDF, PDF,Gaussian random variable,
Uniform Exponential, Laplace, Gamma, Erlang, Chi-Square, Raleigh, Rician and Cauchy
types of random variables.
Unit 3
OPERATIONS ON A SINGLE R V: Expected value, EV of Random variables, EV of
functions of Random variables, Central Moments, Conditional expected values.
Unit 4
Characteristic functions: Characteristic functions, Probability generating functions, Moment
generating functions, Engg applications, Scalar quantization, entropy and source coding.
Unit 5
Pairs of Random variables: Pairs of Random variables, Joint CDF, joint PDF, Joint
probability mass functions, Conditional Distribution, density and mass functions, EV
involving pairs of Random variables, Independent Random variables, Complex Random
variables, Engg Application. Definition and characterization, Mathematical tools for studying
Random Processes, Stationary and Ergodic Random processes,Properties of ACF.
Text Books
1. Shynk, John J. Probability, random variables, and random processes: theory and
signal processing applications. John Wiley & Sons, 2012.
2. Krylov, Nikolaĭ Vladimirovich. Introduction to the theory of random processes. Vol.
43. American Mathematical Soc., 2002.
