HR22 HITAM HYDERABAD

B.Tech II Year–I Sem L T P C

Subject Code: 22PC3CD01 3 1 2 5

Data Structures and Algorithms

Prerequisite: Basic mathematical, analytical and logical capability, problem solving through C.
Course Objectives:
 Introduce Analysis of Algorithm in terms of space and time complexity.
 Exploring basic data structures such as stacks and queues.
 Introduces a variety of data structures such as hash tables, search trees, tries, heaps, graphs.
 Introduces sorting and pattern matching algorithms.

Course Outcomes:
 Understand concepts of ADT and to write an algorithm for a given problem statement, also
calculate time and space complexity.
 Ability to develop C programs for computing real-life applications using data struc-
tures like linked lists, stacks, queues.
 Understand different types of trees like Red-Black, AVL, Splay trees.
 Ability to implement searching and sorting algorithms, and pattern matching algorithms.

Module I
Introduction: Basics of Data Structures, Abstract data types, Dynamic aspects of operations on
data, Characteristics of data structures, Creation and manipulation of data structures, Operations
on data structures.

Introduction to Algorithms: asymptotic notations divide & conquer recursion, analyzing

recursive algorithms.

Programs:

1. Asymptotic notations to calculate the running time complexity of any algorithm. Ο Notation
(Big-O Notation), Ω Notation (Big-Omega Notation), θ Notation (Theta Notation)
2. Calculate complexity analysis of control structures

3. Calculate complexity analysis of any recursive algorithm

HR22 HITAM HYDERABAD

Module II
Linked lists: Types of linked lists – singly, doubly and circularly linked lists, operations on
linked lists.

Stacks: Implementation of stacks– array and linked list, operations on stacks, Applications of
Stacks, Notations – infix, prefix and postfix, Conversion and evaluation of arithmetic
expressions using Stacks.

Queues: Implementation of queues– array and linked list, operations on queues, Types of queues
– queue, double ended queue and priority queue.

Programs:
1. Write a Program to Implement Stack Operations using Dynamic Memory Allocation.
2. Write a program to convert expressions infix to postfix using stack.
3. Write a program to evaluate arithmetic expressions using stack
4. Write a program that uses functions to perform the following operations on Singly linked
list.
i) Creation ii) Insertion iii) Deletion iv) Traversal
5. Write a program that uses functions to perform the following operations on Circular
linked list.
i) Creation ii) Insertion iii) Deletion iv) Traversal
6. Write a program that implement Queue (its operations) using Arrays.
7. Write a program that implement stack (its operations) using Pointers

Module III
Dictionaries: Linear list representation, skip list representation, operations - insertion,
deletion and searching.

Hash Table Representation: hash functions, collision resolution-separate chaining, open

addressing- linear probing, quadratic probing, double hashing, rehashing, extendible
hashing.

Programs:
1. Write a program to implement dictionary linear list representation and its operations
2. Write a Program to Implement Hash Tables with Quadratic Probing
3. Write a Program to Implement Hash Tables with Linear Probing
4. Write a Program to Implement Hash Tables Chaining with Binary Trees
HR22 HITAM HYDERABAD

5. Write a Program to Implement Hash Tables Chaining with Doubly Linked Lists

Module- IV
Graph: Basic terminologies and Representation Traversal algorithms Breadth First Search,
Depth First Search, Shortest path: Depth first search in directed and undirected graphs. Union-
find data structure and applications. Directed acyclic graphs, topological sort.

Trees: Binary Search Trees, Definition, Implementation, Operations- Searching, Insertion and
Deletion, AVL Trees, Definition, Height of an AVL Tree, Operations – Insertion, Deletion and
Searching, Red –Black, Splay Trees.

Programs:
1. Write a program to implement the Binary Search tree.
a) Insertion b) Deletion c) Traversal d) Searching element in tree.

2. Write a program to implement the AVL tree.

a) Insertion b) Deletion c) Traversal d) Searching element in tree.

3. Write a program to implement the Red-Black tree.

a) Insertion b) Deletion

4. Write a program to implement the Splay tree.

a) Insertion b) Deletion
5. Write a program to implement graph traversal methods
a) Breadth First Search, b) Depth First Search

Module V
Sorting: objective and Properties of different sorting Algorithms Insertion Sort, Bubble sort,
Selection Sort, Merge sort, Quick Sort, Heap sort, Radix sort, Bucket sort. Performance and
comparison among all the methods

Pattern Matching and Tries: Pattern matching algorithms-Brute force, The Boyer –Moore
algorithm, Naive algorithm, The Knuth-Morris-Pratt algorithm; Tries- Standard Tries,
Compressed Tries, Suffix tries.
HR22 HITAM HYDERABAD

Programs:
1. Write a program to implement merge sort using divide and conquer technique
2. Write a program to implement bubble sort.
3. Write a program to implement brute-force method of string matching.
4. Write a Program to perform string matching using Naive String Matching
5. Write a program to implement Standard Trie
6. Write a program to implement Compressed Trie
7. Write a program to implement Suffix Trie

TEXT BOOKS:

1. Fundamentals of Data Structures in C, 2nd Edition, E. Horowitz, S. Sahni and Susan

Anderson Freed, Universities Press.
2. Data Structures using C – A. S. Tanenbaum, Y. Langsam, and M.J. Augenstein,
PHI/Pearson Education.
3. AV Aho. J. Hopcroft, JD Ullman, Data Structures and Algorithms, Addison-
Wesley,1983.

REFERENCE BOOKS:

1. Data Structures : A Pseudocode Approach with C, 2 nd Edition, R. F. Gilberg and B.A.

Forouzan, Cengage Learning.
2. Fundamentals of Computer Algorithms by Horwitz and Sahni,Galgotia.
3. Mark Allen Weiss, "Data Structures and Algorithm Analysis in C", 2nd Edition, Pearson
Education, 2011.

WEB RESOURCES:
https://www.javatpoint.com /c-programming-language-tutorial
https://www.tutorialspoint.com/cprogramming/index.htm
 HR22 HITAM HYDERABAD

Course Outcomes:

O-PO/PSO Mapping Chart

(3/2/1 indicates strength of correlation)
3 – High; 2 – Medium; 1 – Low
Program Specific
Program Outcomes (POs)
Course Outcomes*
Outcomes PS PSO
PO PO PO PO PO PO PO PO PO PO PO PO PSO
(COs) O 3
1 2 3 4 5 6 7 8 9 10 11 12 2
1
CO1 3 2 2
CO2 3 2 1 1
CO3 3 2 1 2 1
CO4 3 2 1 2 1
HR22 HITAM HYDERABAD

B.Tech II Year–II Sem L T P C

Subject Code: 22PC4CD02 2 0 0 2

Introduction to Data Science

Course Objectives:

1. Learn concepts, techniques and tools they need to deal with various facets of data science
practice, including data collection and integration
2. Understand the basic types of data and basic statistics
3. Identify the importance of data reduction and data visualization techniques

Course Outcomes:
After completion of the course, the student should be able to
1. Classify basic terms of Statistical Inference means.
2. Identify probability distributions commonly used as foundations for statistical modeling. Fit a
model to data
3. Describe the data using various statistical measures and perform data reduction and apply
visualization techniques.
4. Utilize R elements for data handling

Module - I
Introduction: Definition of Data Science- Big Data and Data Science hype – and getting past
the hype - Datafication - Current landscape of perspectives - Statistical Inference - Populations
and samples - Statistical modeling, probability distributions, fitting a model – Over fitting.
Basics of R: Introduction, R- Environment Setup, Programming with R, Basic Data Types.

Module - II
Data Types & Statistical Description
Types of Data: Attributes and Measurement, What is an Attribute? The Type of an Attribute,
The Different Types of Attributes, Describing Attributes by the Number of Values, Asymmetric
Attributes, Binary Attribute, Nominal Attributes, Ordinal Attributes, Numeric Attributes,
Discrete versus Continuous Attributes.
HR22 HITAM HYDERABAD

Basic Statistical Descriptions of Data: Measuring the Central Tendency: Mean, Median, and
Mode, Measuring the Dispersion of Data: Range, Quartiles, Variance, Standard Deviation, and
Inter- quartile Range, Graphic Displays of Basic Statistical Descriptions of Data.

Module - III
Vectors: Creating and Naming Vectors, Vector Arithmetic, Vector sub setting,
Matrices: Creating and Naming Matrices, Matrix Sub setting, Arrays, Class.
Factors and Data Frames: Introduction to Factors: Factor Levels, Summarizing a Factor,
Ordered Factors, Comparing Ordered Factors, Introduction to Data Frame, subsetting of Data
Frames, Extending Data Frames, Sorting Data Frames.
Lists: Introduction, creating a List: Creating a Named List, Accessing List Elements,
Manipulating List Elements, Merging Lists, Converting Lists to Vectors

Module - IV
Conditionals and Control Flow: Relational Operators, Relational Operators and Vectors,
Logical Operators, Logical Operators and Vectors, Conditional Statements.
Iterative Programming in R: Introduction, While Loop, For Loop, Looping Over List.
Functions in R: Introduction, writing a Function in R, Nested Functions, Function Scoping,
Recursion, Loading an R Package, Mathematical Functions in R.

Module - V
Data Reduction: Overview of Data Reduction Strategies, Wavelet Transforms, Principal
Components Analysis, Attribute Subset Selection,
Regression and Log-Linear Models: Parametric Data Reduction, Histograms, Clustering,
Sampling, Data Cube Aggregation.
Data Visualization: Pixel-Oriented Visualization Techniques, Geometric Projection
Visualization Techniques, Icon-Based Visualization Techniques, Hierarchical Visualization
Techniques, Visualizing Complex Data and Relations.

TEXT BOOKS:
1. Doing Data Science, Straight Talk from The Frontline. Cathy O’Neil and Rachel Schutt,
HR22 HITAM HYDERABAD

O’Reilly, 2014
2. Jiawei Han, Micheline Kamber and Jian Pei. Data Mining: Concepts and Techniques, 3rd ed.
The Morgan Kaufmann Series in Data Management Systems.
3. K G Srinivas, G M Siddesh, “Statistical programming in R”, Oxford Publications.

REFERENCE BOOKS:
1. Introduction to Data Mining, Pang-Ning Tan, Vipin Kumar, Michael Steinbanch, Pearson
Education.
2. Brain S. Everitt, “A Handbook of Statistical Analysis Using R”, Second Edition, 4 LLC, 2014.
3. Dalgaard, Peter, “Introductory statistics with R”, Springer Science & Business Media, 2008.
4. Paul Teetor, “R Cookbook”, O’Reilly, 2011.

CO-PO &PSO Mapping:

Course Name - Course

1 1 1 PSO PSO PSO
Outcomes / Program 1 2 3 4 5 6 7 8 9
0 1 2 1 2 3
Outcomes

CO1 M H

CO2 M H

CO3 H

CO4 H