Birla Institute of Technology and Science, Pilani,

Hyderabad Campus
Department of Computer Sc. and Information Systems
First Semester 2022-2023
BITS F232 (Foundations of Data Structures and
Algorithms)

Date: 29th August 2022

Course Number : BITS F232 (L:3, P:1, U:4) M, W, F: 8th hour
Course Title : Foundations of Data Structures and Algorithms
Instructor-In-Charge : Prof. Chittaranjan Hota
(hota[AT]hyderabad.bits-pilani.ac.in)
Instructors : Dr. Lov Kumar, Dr. Aneesh Chivukula

Scope and Objectives of the Course:

A data structure is a collection of large amounts of data values, the
relationships among them, and the functions or operations that can be applied
on them. In order to be effective, data has to be organized in a manner that
adds to the effectiveness of an algorithm, and data structures such as stacks,
queues, linked lists, heaps, trees, and graphs provide different capabilities to
organize and manage large amounts of data. While developing a program or
an application, many developers find themselves more interested in the type
of algorithm used rather than the type of data structure implemented.
However, the choice of data structure used for a particular algorithm is
always of paramount importance. For example, B-trees have unique abilities to
organize indexes and hence are well suited for implementation of databases;
Linked lists are well suited for backtracking algorithms like, accessing
previous and next pages in a web browser; Tries are well suited for
implementing approximate matching algorithms like, spell checking software
or predicting text in dictionary lookups on Mobile phones; Graphs are well
suited for path optimization algorithms (like in Google maps) or searching in a
Social graph (like Facebook). As computers have become faster and faster, the
problems they must solve have become larger and more complex, requiring
development of more complex programs. This course will also teach students
good programming and algorithm analysis skills so that they can develop such
programs with a greater degree of efficiency.
The primary objectives of the course are as under:

 Apply various basic data structures such as stacks, queues, linked lists,
trees etc. to solve complex programming problems. Understand basic
techniques of algorithm analysis.
 Design and implement advanced data structures like graphs, balanced
search trees, hash tables, priority queues etc. Apply graph and string
algorithms to solve real world problems like finding shortest paths on huge
maps or detecting plagiarism percentage.
 Apply basic algorithmic techniques such as brute-force, greedy algorithms,
divide and conquer, dynamic programming etc. to solve complex
programming problems and examine their efficiency.

At the end of the course, you should understand common data structures and
algorithms, be able to develop new data abstractions (interfaces) and use
existing library components in C++.

Reference Books:
R1: Data Structures and Algorithms in C++, Michael T. Goodrich, Roberto
Tamassia, David M. Mount, 2nd Edition, 2011, Wiley (e-book in India).
R2: Introduction to Algorithms, TH Cormen, CE Leiserson, RL Rivest, C Stein,
3rd Ed., MIT Press, PHI, 2010.
R3: Data Structures & Algorithm Analysis in C++, Mark Allen Weiss, 4 th
Edition, Pearson, 2014.
R4: Data Structures and Algorithms, Alfred V. Aho, John E. Hopcroft, Jeffrey
D. Ullman, 4th Indian reprint, Pearson, 2001.

Lecture Plan:
Lect Learning
Chapter in the Text
ure Objectives Topics to be covered
Book
#
1 The role of DS What kinds of problems are solved by R2 (1), R4(1)
and algorithms? Journey from problems to
Algorithms in programs.
Computing.
2 Introduction Classes: Class Structure, Constructors, R1 (1.5, 1.6)
to C++. Class Friends and Class Members,
Standard Template Library (STL), An
example C++ program.
3-4 To understand Object Oriented Design: Goals, R1 (2.1, 2.2, 2.3)
the features of Principles and Design Patterns;
Object Inheritance and Polymorphism;
Oriented Interfaces and abstract classes;
Paradigm. Templates.
5-7 Implementing Using arrays, Insertion and removal R1 (3.1, 3.2, 3.3,
elementary from a Linked list, generic single linked 3.5)
data list, doubly linked lists, circular linked
structures and lists, linear and binary recursion.
8-9 algorithms. Functions: Linear, N-Log-N, Quadratic R1 (4.1, 4.2), R2
Understandin functions etc., Asymptotic notation and (2, 3)
g techniques asymptotic analysis, Using Big-Oh
for Algorithm notation, Examples of analysis.
analysis.
10- Stack ADT, Array-based stack R1 (5.1, 5.2)
12 Implementing implementation, stack implementation
more common using generic linked list, Applications of
data stacks: matching tags in an HTML
structures and document; Queue ADT, Array-based and
algorithms circular linked list based
like Stacks, implementation.
 13 Queues, Double-Ended queue: Deque ADT, R1 (5.3)
Deques, Implementing using doubly linked lists,
Vectors, List Adapters: Implementing stack using
ADTs, Deque.
14 Sequences, Vector ADT, Simple Array-based R1 (6.1)
and Trees. implementation; Extendable array based
Using implementation (Amortization) and STL
Amortization Vectors.
15- to perform a List ADT: Node based operations and R1 (6.2, 6.3, 6.4)
16 set of push Iterators, doubly linked list
operations on implementation, Sequence ADT,
a vector. Applications: Bubble sort on sequences,
and its analysis.
17- General Trees: Properties and functions, R1 (7.1, 7.2, 7.3)
18 Traversal algorithms: Pre order, post
order traversals, Binary tree: ADTs,
Linked and Vector structures for Binary
trees, Binary tree traversal, Template
function pattern.
19- Priority Queue ADT, Implementing using R1 (8.1, 8.2, 8.3)
21 Lists, Algorithms suitable for Priority
queues, Heap: Complete binary trees
Implementing and their representation, Implementing
Advanced data Heaps using Priority queue, Heap sort
structures like as an example.
22- Priority Map ADT, Implementation using Lists, R1 (9.1, 9.2, 9.4)
24 queues, Hash tables: Bucket arrays, hash
Heaps, Hash functions, compression functions,
tables, Maps, collision-handling schemes, Rehashing
Skip lists, into a new table, Implementation of hash
Dictionaries, tables, Skip lists: Search and update
Search Trees. operation implementations.
25 Dictionary ADT: Implementation with R1 (9.5)
location-aware entries.
26- Binary Search Trees: Operations and R1 (10.1, 10.2,
28 Analysis, AVL Trees: Insertion and 10.4, 10.5)
deletion, Analysis, Multi-way search
trees, Red-Black Trees: Operations and
analysis.

29- Merge sort: Divide and conquer, R1 (11.1, 11.2)

30 Understandin merging arrays and lists, running time of
g various merge sort; Quick sort: Randomized
basic quick sort.
Algorithmic Sorting through algorithmic lens: Lower R1 (11.2, 11.3)
31- techniques bound, Linear time: Bucket and Radix
33 and usage of sort, Comparing sorting algorithms.
appropriate
34- data Strings and Dynamic programming: R1 (12.1, 12.2)
35 structures String operations, Matrix Chain-Product
along with as an example, Applying Dynamic
their programming to LCS problems.
36- applications Pattern matching algorithms: Brute R1 (12.3)
37 and analysis. force, Boyer-Moore algorithm, KMP
algorithm, Pattern matching using Tries.
 38- Graph Algorithms: Graph ADT, Data R1 (13.1, 13.2)
39 structures for graphs: Edge list,
Adjacency list, Adjacency matrix.
40 Graph Traversals: DFS, and BFS, R1 (13.4)
Traversing a Diagraph, Transitive
closure.
41- Shortest path and MST: Dijkstra, R1 (13.5, 13.6)
42 Kruskal, and Prim-Jarnik algorithms.

Evaluation Scheme:
Component Durati Weightag Date & Time Nature of
on e(%) the
componen
t
Mid sem Test 90 min 30% 05/11 1.30 - 3.00PM Closed
Book
Lab Test (One) 1 hr. 20% To be announced Open Book
Programming - 15% To be announced Take home
Assignments(5)
Comprehensive 180 35% 18/12 FN Part Open
examination min.

Note: minimum 40% of the evaluation to be completed by midsem grading.

Make-up-Policy:
Make-up exams will be strictly granted on prior permission and on genuine
grounds only. A request email should reach the I/C on or before the test.
Course Notices and Material:
Course material pertaining to this course will be made available on a regular
basis on the course webpage in googleclass page and will be used for notices,
announcements, grades, quizzes, and googlemeet recordings. Programming
assignments will have a demo/ viva monthly once.

Consultation Hour:
To be announced in the class.
Academic Honesty and Integrity Policy:
Academic honesty and integrity are to be maintained by all the students
throughout the semester and no type of academic dishonesty is acceptable.

Instructor-In-Charge, BITS F232