Birla Institute of Technology and Science, Pilani, Hyderabad Campus

Department of Computer Sc. and Information Systems

Summer 2022-2023
BITS F232 (Foundations of Data Structures and Algorithms)

Date: 23rd May 2023

Course Number : BITS F232 (L:3, P:2, U:5) M, W, F: 2-3:50 pm (room: I113)
Course Title : Foundations of Data Structures and Algorithms
Instructor-In-Charge : Dr. Apurba Das (apurba[at]hyderabad.bits-pilani.ac.in)

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, Wiley, 2015.
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, 4th Edition, Pearson, 2014.
R4: Data Structures and Algorithms in C++, Adam Drozdek, 4th edition, Cengage Learning, 2012.

Lecture Plan:
Lectu Learning Chapter in the Text
Topics to be covered
re# Objectives Book
1 The role of DS What kinds of problems are solved by algorithms? R2 (1)
and Algorithms in Journey from problems to programs.
Computing.
Classes: Class Structure, Constructors, Class R1 (2.1,2.2,2.3)
Introduction to C+ Friends and Class Members, Standard Template
+. Library (STL), An example C++ program.

2 To understand the Object Oriented Design: Goals, Principles and R1 (2.1, 2.2, 2.3)
features of Object Design Patterns; Inheritance and Polymorphism;
Oriented Interfaces and abstract classes; Templates.
Paradigm.
3 Implementing Using arrays, Insertion and removal from a Linked R1 (3.1, 3.2, 3.3, 3.5)
elementary data list, generic single linked list, doubly linked lists,
structures and circular linked lists, linear and binary recursion.
4 algorithms. Functions: Linear, N-Log-N, Quadratic functions R1 (4.1, 4.2), R2 (2,
Understanding etc., Asymptotic notation and asymptotic analysis, 3)
techniques for Using Big-Oh notation, Examples of analysis.
Algorithm
analysis.
5 Stack ADT, Array-based stack implementation, R1 (5.1, 5.2)
Implementing stack implementation using generic linked list,
more common Applications of stacks: matching tags in an HTML
data structures and document; Queue ADT, Array-based and circular
algorithms like linked list based implementation.
6 Stacks, Queues, Double-Ended queue: Deque ADT, Implementing R1 (5.3)
Deques, Vectors, using doubly linked lists, Adapters: Implementing R1 (6.1)
List ADTs, stack using Deque.
Sequences, and Vector ADT, Simple Array-based implementation;
Trees. Using Extendable array based implementation
Amortization to (Amortization) and STL Vectors.
7 perform a set of List ADT: Node based operations and Iterators, R1 (6.2, 6.3, 6.4)
push operations on doubly linked list implementation, Sequence ADT,
a vector. Applications: Bubble sort on sequences, and its
analysis.
8 General Trees: Properties and functions, Traversal R1 (7.1, 7.2, 7.3)
algorithms: Pre order, post order traversals, Binary
tree: ADTs, Linked and Vector structures for
Binary trees, Binary tree traversal, Template
function pattern.
9-10 Priority Queue ADT, Implementing using Lists, R1 (8.1, 8.2, 8.3)
Algorithms suitable for Priority queues, Heap:
Complete binary trees and their representation,
Implementing Implementing Heaps using Priority queue, Heap
Advanced data sort as an example.
 10-11 structures like Map ADT, Implementation using Lists, Hash R1 (9.1, 9.2, 9.4)
Priority queues, tables: Bucket arrays, hash functions, compression
Heaps, Hash functions, collision-handling schemes, Rehashing
tables, Maps, Skip into a new table, Implementation of hash tables,
lists, Dictionaries, Skip lists: Search and update operation
Search Trees. implementations.
12-13 Dictionary ADT: Implementation with location- R1 (9.5)
aware entries. R1 (10.1, 10.2, 10.4,
Binary Search Trees: Operations and Analysis, 10.5)
AVL Trees: Insertion and deletion, Analysis, Multi-
way search trees, Red-Black Trees: Operations and
analysis.

14 Merge sort: Divide and conquer, merging arrays R1 (11.1, 11.2)

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

Evaluation Scheme:
Component Duration Weightage Date & Time Nature
Mid sem Test 90 mins. 20% 15/06 9.30 - Closed Book
11.00AM
Class Interaction In the 13% In the class Quiz (Open)
class
Lab Interaction In the lab 12% In the lab Quiz (Open)
Lab Test (One) 60 mins. 15% To be announced Open Book
Programming Assignments - 10% To be announced Take Home
(2)
Comprehensive examination 180 mins. 30% 13/07 FN Closed Book

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