Course Plan

A. Course Handout (For Students & Faculty)

Institute/School/College Name Chitkara University Institute of Engineering & Technology
Department/Centre Name Department of Computer Science & Engineering
Programme Name Bachelor of Engineering- Computer Science & Engineering
Course Name Advanced Data Structures Session 2023-2024
Course Code CS192 Semester/Batch 6th / 2021
Lecture/Tutorial (Per Week) 2-0-4 Course Credits 4
Course Coordinator Name Dr. Suhasini

1. Scope & Objective of the Course

The course provides a wide scope of learning & understanding of the subject and the main objectives of the
course are
 To understand the detailed view of Arrays, Strings, Recursion, Backtracking.
 To learn object-oriented basics with strong up-skilling on various linear and non linear data structures.
 To explore and implement various algorithm design strategies using examples.
 To analyse and evaluate different data structures.
 To implement the concepts of data structures and algorithms by solving complex engineering problems
and preparing well for interviews, competitions and hackathons.

2. Course Outcomes
At the end of the course, students will be able to:
CO1. Understand the detailed view of data structures and algorithms with underlying mathematics behind it.
CO2. Revisit Object Oriented fundamentals along with the concepts of other linear data structures like Linked
lists and Stacks and non linear data structures like Graphs, Tries, Binary Trees and its variations; with
main emphasis on Interview based questions.
CO3. Explore various algorithm strategies such as DP, Greedy Method, Backtracking and Bit-masking.
CO4. Analyse and evaluate different data structures and will be able to prepare well for Interview panels
through numerical understanding of the concepts.
CO5. Implement the concepts of data structures and algorithms on several forums like code-chef, coding
ninjas, GFG and Hacker Rank.

CLO-PO Mapping grid |Program outcomes (POs) are available as a part of Academic Program Guide

Course PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
Outcomes
CO1 H H M H M M L
CO2 H M H
CO3 H H M H L
CO4 M
CO5 M M M L M L L

3. Recommended Books (Reference Books/Textbooks)

RB1. Computer Algorithms by E. Horowitz, S. Sahni and S. Rajsekran, Computer Science Press, New York, ISBN
– 0-7167-8316-9.
RB2. Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Clifford Stein, MIT Press, Cambridge, Massachusetts London, England McGraw-Hill Book Company, ISBN
0-262-03293-7.
RB3. Data Structures with C (Schaum's Outline Series) (English, Paperback, Lipschutz Seymour), McGraw Hill
Education India, ISBN: 9780070701984, 9780070701984
RB4. Design & Analysis of Computer Algorithms (English, Paperback, Aho Alfred V.), Pearson Education India,
ISBN: 9788131702055, 9788131702055

Advanced Data Structures / CS192 Page 1 of 10

 Course Plan
RB5. Data Structures and Algorithms Made Easy (English, Paperback, Karumanchi Narasimha),
Karumanchi Narasimha, Careermonk Publications, ISBN: 9788193245279, 9788193245279.

4. Other readings & relevant websites

S.N. Link of Journals, Magazines, Websites, and Research Papers
1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]

5. Recommended Tools and Platforms: Windows 10 or higher / Ubuntu 21.04, GCC Compiler, IDE
6. Course Plan Lecture
Lecture Topics Recommended
No. Books / Resources
1 Arrays – 1: Advance Problems on Sliding Windows and Two pointers will be RB3
discussed.
2 Arrays – 2: Discussion Frequency Arrays and Prefix Arrays and Its Problems. RB4
3 Binary Search: Binary Search, Its Implementation and Advance Binary Search RB1
problems will be discussed.
4-5 Array Advanced Algorithms – 1: Kadane's Algorithm, Prime Seive, Vectors and RB2
Amalgamation of the above topics will be discussed.
6-7 Array Advanced Algorithms- 2: Problems on Sorting, Pigeon Hole Principle and Heavy RB2
Implementation will be discussed.
8-9 Strings: Implementation Problems on Strings, Two pointers in Strings and Problem on RB2
Frequency Arrays with respect to Strings.
10 Sliding Window – 1: Advance Problems on Sliding Window and Discussion of Deque RB2
STL.
11-12 Advanced String Algorithms: String Matching Algorithms like KMP, Z Function, and RB2
Rabin Karp will be discussed and problems based on that.
13-14 Array Interview Preparation class: Recently asked company problems based upon RB2, RB5
arrays, string and the above mentioned algorithms.
15-16 Recursion – 1: Basics of Recursion, basic problems on recursion to have better RB2, RB5
understanding of the call stack, Types of Recursion.
17-19 Recursion Backtracking – 1: Implementation based Problems on recursion will be RB1, RB2, RB5
discussed in a thorough manner with call stacks, Introduction to Backtracking and
basic problem on backtracking to get the flow of it.
Recursion Backtracking – 2: Advance problems on backtracking.
20 Recursion on Matrix: Discussion on how recursion and backtracking are used in RB1, RB2, RB5
general to solve problems on matrix/grid.
21-22 OOPS-1: Discussion on OOPs with real world example why it is important, Discussions RB4
on classes, objects and self invoked functions like Constructors, Copy Constructor,
Copy Assignment Operators, Destructors.
23-24 OOPS-2: Discussion on characterises of OOPs like Encapsulation, Abstraction, RB4
Polymorphism, Inheritance, Dynamic Binding, Message Passing etc.
25 Linked List – 2: Interview Based Problems on LL. RB2
ST1 (Syllabus covered from Lecture 1 to 25)
26-27 Stack Interview Questions: Interview Problems Based on Stacks. RB3
28-30 Binary Trees – 1: Binary Trees (Definition, Implementation, Algorithms on Trees (DFS, RB3, RB4
BFS, etc.),Standard Problems on Trees)
31-32 Binary Trees – 2: Interview Problems Based on Trees. RB2
33-34 Binary Search Trees – 1: Implementation of BST, Standard Problems on BST. RB1
35-36 Binary Search Trees – 2: Interview Problems Based on Trees. RB4, RB5

Advanced Data Structures / CS192 Page 2 of 10

 Course Plan
37-38 Hash maps – 2: Advance Hashing Techniques, Interview Problems based Hashing etc. RB2
39-40 Priority Queue – 2: Advance Problems on Heaps. RB3
41 DP – 1: DP, Types of DP, Importance of DP, 1-D DP company oriented questions RB2, RB4
42 DP – 2: Discussion on 2D DP and Grid DP and Advance Problems based on that. RB2, RB3
43 DP – 3: Knapsack and Selecting Distinct based DP. RB2, RB4, RB5
44 DP – 4: Problems based on DP Patterns. GFG
45 DP – 5: Multi-dimensional DP GFG
46 DP – 6: DP on Trees. RB5, GFG
47 Greedy Algorithms – 2: Advance Problems on Greedy. GFG
48 Bit-masking – 2: Interview Based Problems on Bit Manipulations. GFG
49-50 Number Theory: Prime Sieve, Segmented Sieve, Euclid Algorithm, Extended Euclid
Algorithm and Its Application in solving linear Diophantine equations and RB2, GFG
multiplicative modulo inverse, Totient Equation, Fermat Little Theoram etc.
51 Maths: Big Integers, Combinatorics, Solving Linear Recurrences, Mathematical
GFG
Expectation etc.
ST2 (Syllabus covered from Lecture 26 to 51)
52-53 Graphs-1: Undirected Graphs, Cycle Detection, shortest cycle in an undirected graphs
RB2, GFG
etc, Directed Graphs, Topological sort, Cycle Detection in an directed graphs)
54-55 Graphs-2: Kosaraju algorithm, DSU and Problems based on the above mentioned
RB2, RB5, GFG
topics.
56-57 Graphs-3: Minimum Spanning Trees, Kruskal's and Prism's Algorithm, Introduction to
RB2, RB5, GFG
Weighted Graphs
58-59 Graphs-4: Dijkstras's, Bellman ford algorithms and Problems based on the above
RB2, RB5, GFG
mentioned Topics.
60 Graphs-5: Advance problems on Graphs. RB2, RB5, GFG
61 Tries: Introduction, Range Queries and Interview Problems on Tries. RB2, RB5, GFG
62-64 Revision and Doubt Clearing Sessions
END TERM – FULL SYLLABUS

7. Course Plan Lab

Practical Topics
1-2 Arrays-1: Advance Problems on Sliding Windows and Two pointers will be discussed. Arrays- 2: Discussion Frequency
Arrays and Prefix Arrays and Its Problems.
3-5 Binary Search: Binary Search, Its Implementation and Advance Binary Search problems will be [Link]
Advanced Algorithms – 1: Kadane's Algorithm, Prime Seive, Vectors and Amalgamation of the above topics will be
discussed.
6-9 Array Advanced Algorithms- 2: Problems on Sorting, Pigeon Hole Principle and Heavy Implementation will be
[Link]: Implementation Problems on Strings, Two pointers in Strings and Problem on Frequency Arrays
with respect to Strings.
10-12 Sliding Window - 1: Advance Problems on Sliding Window and Discussion of Deque STL.
Advanced String Algorithms: String Matching Algorithms like KMP, Z Function, and Rabin Karp will be discussed and
problems based on that.
13-14 Array Interview Preparation class: Recently asked company problems based upon arrays, string and the above
mentioned algorithms.
15-16 Recursion – 1: Basics of Recursion, basic problems on recursion to have better understanding of the call stack, Types
of Recursion.
17-19 Recursion Backtracking – 1: Implementation based Problems on recursion will be discussed in a thorough manner
with call stacks, Introduction to Backtracking and basic problem on backtracking to get the flow of it.
Recursion Backtracking – 2: Advance problems on backtracking.
20 Recursion on Matrix: Discussion on how recursion and backtracking are used in general to solve problems on
matrix/grid.
21-22 OOPS-1: Discussion on OOPs with real world example why it is important, Discussions on classes, objects and self-
invoked functions like Constructors, Copy Constructor, Copy Assignment Operators, Destructors.
23-24 OOPS-2: Discussion on characterises of OOPs like Encapsulation, Abstraction, Polymorphism, Inheritance, Dynamic
Binding, Message Passing etc.
25-27 Linked List – 2: Interview Based Problems on LL.

Advanced Data Structures / CS192 Page 3 of 10

 Course Plan
Stack Interview Questions: Interview Problems Based on Stacks.
28-30 Binary Trees – 1: Binary Trees (Definition, Implementation, Algorithms on Trees (DFS, BFS, etc.), Standard Problems
on Trees)
31-36 Binary Trees – 2: Interview Problems Based on Trees. Binary Search Trees – 1: Implementation of BST, Standard
Problems on BST. Binary Search Trees – 2: Interview Problems Based on Trees.
37-40 Hashmaps-2: Advance Hashing Techniques, Interview Problems based Hashing etc. Priority Queue-2: Advance
Problems on Heaps.
41-46 DP-1: DP, Types of DP, Importance of DP, 1-D DP company oriented questions.
DP-2: Discussion on 2D DP and Grid DP and Advance Problems based on that.
DP-3: Knapsack and Selecting Distinct based DP.
DP-4: Problems based on DP Patterns.
DP-5: Multi-dimensional DP
DP-6: DP on Trees.
47-48 Greedy Algorithms-2: Advance Problems on Greedy. Bit-masking-2: Interview Based Problems on Bit Manipulations.

49-51 Number Theory: Prime Sieve, Segmented Sieve, Euclid Algorithm, Extended Euclid Algorithm and Its Application in
solving linear Diophantine equations and multiplicative modulo inverse, Totient Equation, Fermat Little Theoram etc.
Maths: Big Integers, Combinatory, Solving Linear Recurrences, Mathematical Expectation etc.
52-60 Graphs-1: Undirected Graphs, Cycle Detection, shortest cycle in an undirected graphs etc, Directed Graphs,
Topological sort, Cycle Detection in an directed graphs)
Graphs-2: Kosaraju algorithm, DSU and Problems based on the above mentioned topics.
Graphs-3: Minimum Spanning Trees, Kruskal's and Prism's Algorithm, Introduction to Weighted Graphs.
Graphs-4: Dijkstra's, Bellman ford algorithms and Problems based on the above mentioned Topics.
Graphs-5: Advance problems on Graphs.
61-64 Tries: Introduction, Range Queries and Interview Problems on Tries.
Revision and Doubt Clearing Sessions

8. Delivery/Instructional Resources
Lecture Topics PPT Industry Expert Web References Audio-
No. (Link of ppts Session Video
on the central (If yes: link of ppts on
server) the central server)
1-2 Arrays-1: Advance Problems [Link]
on Sliding Windows and Two liding-window-problems/
pointers will be discussed.
[Link]
Arrays- 2: Discussion ry/66274#:~:text=Prefix%20array
Frequency Arrays and Prefix %20is%20a%20very,time%20com
Arrays and Its Problems. plexity%20of%20your%20progra
m.
3-5 Binary Search: Binary Search, [Link]
Its Implementation and go/BinarySearch/AdvancedBinary
Advance Binary Search Search
problems will be discussed.

Array Advanced Algorithms –

1: Kadane's Algorithm, Prime [Link]
Seive, Vectors and ongest-sub-array-of-prime-
Amalgamation of the above numbers-using-segmented-sieve/
topics will be discussed.
6-9 Array Advanced Algorithms- [Link]
2: Problems on Sorting, delight/sorting-practice-
Pigeon Hole Principle and problems-and-interview-
Heavy Implementation will be
questions-cff0b79f9cef
discussed.

Strings: Implementation [Link]

Problems on Strings, Two wo-pointers-technique/
pointers in Strings and
Problem on Frequency Arrays
with respect to Strings.

Advanced Data Structures / CS192 Page 4 of 10

 Course Plan
10-12 Sliding Window - 1: Advance [Link]
Problems on Sliding Window ry/88880
and Discussion of Deque STL.
[Link]
Advanced String Algorithms:
String Matching Algorithms ata-structures/z-algorithm/
like KMP, Z Function, and
Rabin Karp will be discussed [Link]
and problems based on that. abin-karp-algorithm-for-pattern-
searching/
13-14 Array Interview Preparation [Link]
class: Recently asked op-50-array-coding-problems-for-
company problems based interviews/
upon arrays, string and the
above mentioned algorithms.
[Link]
op-50-string-coding-problems-
for-interviews/
15-16 Recursion – 1: Basics of [Link]
Recursion, basic problems on ecursive-functions/
recursion to have better
understanding of the call
stack, Types of Recursion.
17-19 Recursion Backtracking – 1: [Link]
Implementation based og/2021/05/24/recursion-
Problems on recursion will be backtracking-algorithm-with-
discussed in a thorough
practice-problem/
manner with call stacks,
Introduction to Backtracking
and basic problem on [Link]
backtracking to get the flow op-20-backtracking-algorithm-
of it. interview-questions/
Recursion Backtracking – 2:
Advance problems on
backtracking.
20 Recursion on Matrix: [Link]
Discussion on how recursion raverse-a-given-matrix-using-
and backtracking are used in recursion/
general to solve problems on
matrix/grid.
21-22 OOPS-1: Discussion on OOPs [Link]
with real world example why st/oops-concepts-with-real-time-
it is important, Discussions on examples/#:~:text=Let's%20take
classes, objects and self
%20an%20example%20of,of%20i
invoked functions like
Constructors, Copy ts%20attributes%20(data).
Constructor, Copy
Assignment Operators, [Link]
Destructors. pp/language/rule_of_three
23-24 OOPS-2: Discussion on [Link]
characterises of OOPs like object-oriented-programming-in-
Encapsulation, Abstraction, cpp/
Polymorphism, Inheritance,
Dynamic Binding, Message
Passing etc.
25-27 Linked List – 2: Interview [Link]
Based Problems on LL. op-20-linked-list-interview-
question/
Stack Interview Questions:
Interview Problems Based on
Stacks. [Link]
delight/stack-data-structure-
practice-problems-and-interview-

Advanced Data Structures / CS192 Page 5 of 10

 Course Plan
questions-9f08a35a7f19
28-30 Binary Trees – 1: Binary Trees [Link]
(Definition, Implementation, binary-tree-data-structure/
Algorithms on Trees (DFS,
BFS, etc.), Standard Problems
on Trees)
31-36 Binary Trees – 2: Interview [Link]
Problems Based on Trees. op-50-tree-coding-problems-for-
interviews/
Binary Search Trees – 1:
Implementation of BST,
Standard Problems on BST. [Link]
ary-search-tree
Binary Search Trees – 2:
Interview Problems Based on [Link]
Trees. inary-search-tree-bst-interview-
questions/
37-40 Hashmaps-2: Advance [Link]
Hashing Techniques, op-20-hashing-technique-based-
Interview Problems based interview-questions/
Hashing etc.

Priority Queue-2: Advance [Link]

Problems on Heaps. actice/notes/heaps-and-priority-
queues/
41-46 DP-1: DP, Types of DP, [Link]
Importance of DP, 1-D DP actice/algorithms/dynamic-
company oriented questions. programming/introduction-to-
dynamic-programming-
DP-2: Discussion on 2D DP
and Grid DP and Advance 1/tutorial/
Problems based on that.
[Link]
DP-3: Knapsack and Selecting ata-structures/2d-dp-problems/
Distinct based DP.
[Link]
DP-4: Problems based on DP
0-1-knapsack-problem-dp-10/
Patterns.

DP-5: Multi-dimensional DP [Link]

neral-
DP-6: DP on Trees. discussion/458695/dynamic-
programming-patterns

[Link]
ces/what-is-dynamic-
programming

[Link]
multi-dimensional-dynamic-
programming-666b095b2e7b

[Link]
ry/20935
47-48 Greedy Algorithms-2: [Link]
Advance Problems on Greedy. ourses/programming/bit-
Bit-masking-2: Interview manipulation/
Based Problems on Bit
Manipulations.
49-51 Number Theory: Prime Sieve, [Link]
Segmented Sieve, Euclid egmented-sieve/

Advanced Data Structures / CS192 Page 6 of 10

 Course Plan
Algorithm, Extended Euclid
Algorithm and Its Application [Link]
in solving linear Diophantine euclidean-algorithms-basic-and-
equations and multiplicative
extended/
modulo inverse, Totient
Equation, Fermat Little
Theoram etc. [Link]
multiplicative-inverse-under-
modulo-m/

Maths: Big Integers, [Link]

Combinatory, Solving Linear
eulers-totient-function/
Recurrences, Mathematical
Expectation etc.
[Link]
ermats-little-theorem/

[Link]
actice/math/combinatorics/basic
s-of-combinatorics/tutorial/

[Link]
discrete_mathematics/discrete_
mathematics_recurrence_relatio
[Link]

[Link]
om/free-resources/directory-of-
statistical-
analyses/mathematical-
expectation/
52-60 Graphs-1: Undirected Graphs, [Link]
Cycle Detection, shortest detect-cycle-undirected-graph/
cycle in an undirected graphs
etc, Directed Graphs,
[Link]
Topological sort, Cycle
Detection in an directed opological-sorting/
graphs)
[Link]
Graphs-2: Kosaraju algorithm, g/problems/strongly-connected-
DSU and Problems based on components-kosarajus-algo/1
the above mentioned topics.
[Link]
Graphs-3: Minimum Spanning
Trees, Kruskal's and Prism's ruskals-minimum-spanning-tree-
Algorithm, Introduction to algorithm-greedy-algo-2/
Weighted Graphs.
[Link]
Graphs-4: Dijkstra's, Bellman dijkstras-shortest-path-algorithm-
ford algorithms and Problems greedy-algo-7/
based on the above
mentioned Topics.
[Link]
Graphs-5: Advance problems bellman-ford-algorithm-dp-23/
on Graphs.
[Link]
odestudio/library/important-
graph-problems-for-interviews-
advanced-problems
61-64 Tries: Introduction, Range [Link]
Queries and Interview ntroduction-to-trie-data-

Advanced Data Structures / CS192 Page 7 of 10

 Course Plan
Problems on Tries. structure-and-algorithm-
Revision and Doubt Clearing tutorials/
Sessions

9. Action plan for different types of learners

Slow Learners Average Learners Fast Learners
 Multiple Remedial Extra  Doubt-sessions  More Practice assignments on real life
Classes  Pre-coded algorithms to problems
 Encouragement for illustrate concepts and notions  Engaging students to hold hands of slow
improvement using  E-notes and E-exercises to learners by creating a Peer Tutoring Group
Peer Tutoring study in addition to available  Participation in Hackathons, coding
pedagogic material competitions etc.

10. Evaluation Scheme & Components

No. of Weightage of Mode of
Evaluation Component Type of Component
Assessments Component Assessment
Component 2 Sessional Tests (STs) 02 40% Offline
Component 3 End Term Examination 01 60% Offline
Total 100%
* Out of 02 STs, best 1 ST for final marks evaluation of STs will be considered.
Evaluation Components
Type of Assessment Timeline Total Question Paper Format
of Marks 1 Mark 2 Mark 5 Mark 10 Mark
Conduct MCQ MCQ Question Question
Sessional Test 1 Week 5 40 10 5 02 01

Sessional Test 2 Week 9 40 10 5 02 01

End Term Examination 60 10 10 04 01

11. Details of Evaluation Components

Evaluation Description Syllabus Covered (%) Timeline of Examination Weightage (%)
Component
ST 01 Up to 40% As defined in Academic Calendar
Component 02 40%
ST 02 40% - 80% As defined in Academic Calendar
End Term
Component 03 Examination 100% At the end of the semester 60%
*
Total 100%
*As per Academic Guidelines minimum 75% attendance is required to become eligible for appearing in the End
Semester Examination.
12. Syllabus of the Course
Subject: Advanced Data Structures Subject Code: CS192
Topic (s) No. of Lectures Weightage %
Arrays – 1
Arrays – 2
Binary Search 7 5%
Array Advanced Algorithms – 1
Array Advanced Algorithms- 2
Strings
Sliding Window – 1 7 5%
Advanced String Algorithms

Advanced Data Structures / CS192 Page 8 of 10

 Course Plan
Array Interview Preparation class
Recursion – 1
Recursion Backtracking – 1
6 5%
Recursion Backtracking – 2
Recursion on Matrix
OOPS-1
4 5%
OOPS-2
Linked List – 2 2 5%
Stack Interview Questions 1 5%
Binary Trees – 1
Binary Trees – 2
8 5%
Binary Search Trees – 1
Binary Search Trees – 2
Hashmaps – 2
5 5%
Priority Queue – 2
DP – 1
DP – 2
DP – 3
6 20%
DP – 4
DP – 5
DP – 6
Greedy Algorithms – 2 5%
2
Bitmasking – 2 4%
Number Theory
3 6%
Maths
Graphs-1
Graphs-2
Graphs-3 9 20%
Graphs-4
Graphs-5
Tries 4 5%
Useful Resources:
[Link] - this is a community of CS students studying the same topics
[Link] - explains all the high level fundamentals
[Link] - has visualizations of a lot of helpful algorithms

International Courses:
CS 226 Algorithms and Data Structures: [Link]
Brown CS 16 - Introduction to Algorithms and Data Structures: [Link]
Stanford CS 166 Data Structures: [Link]
University of Washington, St. Louis (CSE241) Algorithms and Data Structures:
[Link]
Harvard CSE 22 Data Structures: [Link]
Michigan EECS 281 Data Structures and Algorithms:
[Link]
Cornell CS 2110 OO Programming and Data Structures: [Link]
MiT 6.006 Introduction to Algorithms: [Link]
science/6-006-introduction-to-algorithms-spring-2008/

Important links:

Advanced Data Structures / CS192 Page 9 of 10

 Course Plan
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

This document is approved by:

Designation Name Signature

Course Coordinator Dr. Suhasini

Program Head Dr. Susheela Hooda

Cluster Dean Dr. Rupali Gill

Dean (Academics Affairs) Dr. Monit Kapoor

Date (DD/MM/YYYY) 01/02/2024

Advanced Data Structures / CS192 Page 10 of 10