CS192,REviewed Advanced Data Structures - Feb 2024 (3)
Uploaded by
monali samalCS192,REviewed Advanced Data Structures - Feb 2024 (3)
Uploaded by
monali samalCourse 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
RB5. Data Structures and Algorithms Made Easy (English, Paperback, Karumanchi Narasimha),
Karumanchi Narasimha, Careermonk Publications, ISBN: 9788193245279, 9788193245279.
Advanced Data Structures / CS192 Page 1 of 9
Course Plan
4. Other readings & relevant websites
S.N. Link of Journals, Magazines, Websites, and Research Papers
1. https://onlinecourses.nptel.ac.in/noc22_cs26/preview
2. https://www.youtube.com/watch?v=zWg7U0OEAoE
3. https://iq.opengenus.org/list-of-advanced-data-structures/
4. https://in.coursera.org/learn/advanced-data-structures
5. https://www.youtube.com/@JennyslecturesCSIT/videos
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-2 Arrays-1: Advance Problems on 1-D arrays RB3
3-4 Arrays-2: Advance Problems on 2-D arrays RB4
5-6 Pointers and arrays
7-8 Interview questions based on arrays
9 Searching algorithms and related problems RB1
10-11 Sorting algorithms and related problems
12-13 Interview questions based on searching and sorting RB2
14-15 Strings: Implementation Problems on Strings RB2
16-17 Linked list and related problems RB2
18 Memory efficient Doubly linked lists and related problems RB2
19-20 Interview questions based on linked lists
21-22 Stacks with arrays and linked lists. RB2
23-24 Interview questions based on stacks. RB2, RB5
25-26 Queues with arrays and linked lists.
27-28 Interview questions based on Queues.
29-30 Recursion: Basics of Recursion, Types of Recursion and basic problems on recursion. RB2, RB5
ST1 (Syllabus covered from Lecture 1 to 30)
31-33 Binary Trees – 1: Binary Trees (Definition, Traversals, Implementation, Algorithms on RB1, RB2, RB5
Trees, Interview Problems on Trees)
34-35 Binary Trees – 2: Interview Problems Based on Trees. RB4
36-37 Binary Search Trees – 1: Implementation of BST, Standard Problems on BST. RB4
38-39 Binary Search Trees – 2: Interview Problems Based on Trees. RB2
40-41 Hash maps – 2: Hashing Techniques, Interview Problems based on Hashing.
42-43 Priority Queue – 2: Advanced Problems on Heaps. RB3
44-46 Graphs-1: Undirected Graphs, Cycle Detection, shortest cycle in an undirected graphs RB3, RB4
etc. Directed Graphs, Topological sort, Cycle Detection in an directed graphs)
47-50 Graphs-2: Graph Traversals and Problems based on the above mentioned topics. RB2
51-54 Graphs-3: Minimum Spanning Trees, Kruskal's and Prism's Algorithm, Introduction to RB1
Weighted Graphs
55-58 Graphs-4: Single Source Shortest Path - Dijkstras's Algorithm, Bellman Ford Algorithm RB4, RB5
and related Problems.
ST2 (Syllabus covered from Lecture 31 to 58)
59-60 Revision and Doubt Clearing Sessions
END TERM – FULL SYLLABUS
7. Course Plan Lab
Practical Topics
1-2 Arrays-1: Advance Problems on 1-D arrays
3-4 Arrays-2: Advance Problems on 2-D arrays
5-6 Pointers and arrays
Advanced Data Structures / CS192 Page 2 of 9
Course Plan
7-8 Interview questions based on arrays
9 Searching algorithms and related problems
10-11 Sorting algorithms and related problems
12-13 Interview questions based on searching and sorting
14-15 Strings: Implementation Problems on Strings
16-17 Linked list and related problems
18 Memory efficient Doubly linked lists and related problems
19-20 Interview questions based on linked lists
21-22 Stacks with arrays and linked lists.
23-24 Interview questions based on stacks.
25-26 Queues with arrays and linked lists.
27-28 Interview questions based on Queues.
29-30 Recursion: Basics of Recursion, Types of Recursion and basic problems on recursion.
31-33 Binary Trees – 1: Binary Trees (Definition, Traversals, Implementation, Algorithms on Trees, Interview
Problems on Trees)
34-35 Binary Trees – 2: Interview Problems Based on Trees.
36-37 Binary Search Trees – 1: Implementation of BST, Standard Problems on BST.
38-39 Binary Search Trees – 2: Interview Problems Based on Trees.
40-41 Hash maps – 2: Hashing Techniques, Interview Problems based on Hashing.
42-43 Priority Queue – 2: Advanced Problems on Heaps.
44-46 Graphs-1: Undirected Graphs, Cycle Detection, shortest cycle in an undirected graphs etc. Directed Graphs,
Topological sort, Cycle Detection in an directed graphs)
47-50 Graphs-2: Graph Traversals and Problems based on the above mentioned topics.
51-54 Graphs-3: Minimum Spanning Trees, Kruskal's and Prism's Algorithm, Introduction to Weighted Graphs
55-58 Graphs-4: Single Source Shortest Path - Dijkstras's Algorithm, Bellman Ford Algorithm and related
Problems.
59-60 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 https://www.techiedelight.com/s
on Sliding Windows and Two liding-window-problems/
pointers will be discussed.
https://codeforces.com/blog/ent
ry/66274#:~:text=Prefix%20array
Arrays- 2: Discussion
Frequency Arrays and Prefix %20is%20a%20very,time%20com
Arrays and Its Problems. plexity%20of%20your%20progra
m.
3-5 Binary Search: Binary Search, https://www.thealgorists.com/Al
Its Implementation and go/BinarySearch/AdvancedBinary
Advance Binary Search Search
problems will be discussed.
Array Advanced Algorithms –
1: Kadane's Algorithm, Prime https://www.geeksforgeeks.org/l
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- https://medium.com/techie-
2: Problems on Sorting, delight/sorting-practice-
Pigeon Hole Principle and problems-and-interview-
questions-cff0b79f9cef
Advanced Data Structures / CS192 Page 3 of 9
Course Plan
Heavy Implementation will be
discussed. https://www.geeksforgeeks.org/t
wo-pointers-technique/
Strings: Implementation
Problems on Strings, Two
pointers in Strings and
Problem on Frequency Arrays
with respect to Strings.
10-12 Sliding Window - 1: Advance https://codeforces.com/blog/ent
Problems on Sliding Window ry/88880
and Discussion of Deque STL.
https://www.scaler.com/topics/d
Advanced String Algorithms:
String Matching Algorithms ata-structures/z-algorithm/
like KMP, Z Function, and
Rabin Karp will be discussed https://www.geeksforgeeks.org/r
and problems based on that. abin-karp-algorithm-for-pattern-
searching/
13-14 Array Interview Preparation https://www.geeksforgeeks.org/t
class: Recently asked op-50-array-coding-problems-for-
company problems based interviews/
upon arrays, string and the
above mentioned algorithms.
https://www.geeksforgeeks.org/t
op-50-string-coding-problems-
for-interviews/
15-16 Recursion – 1: Basics of https://www.geeksforgeeks.org/r
Recursion, basic problems on ecursive-functions/
recursion to have better
understanding of the call
stack, Types of Recursion.
17-19 Recursion Backtracking – 1: https://www.codingninjas.com/bl
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 https://www.geeksforgeeks.org/t
backtracking to get the flow op-20-backtracking-algorithm-
of it. interview-questions/
Recursion Backtracking – 2:
Advance problems on
backtracking.
20 Recursion on Matrix: https://www.geeksforgeeks.org/t
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 https://www.datatrained.com/po
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
ts%20attributes%20(data).
Constructors, Copy
Constructor, Copy Assignment
Operators, Destructors. https://en.cppreference.com/w/c
pp/language/rule_of_three
23-24 OOPS-2: Discussion on https://www.geeksforgeeks.org/
characterises of OOPs like object-oriented-programming-in-
Encapsulation, Abstraction, cpp/
Polymorphism, Inheritance,
Dynamic Binding, Message
Passing etc.
Advanced Data Structures / CS192 Page 4 of 9
Course Plan
25-27 Linked List – 2: Interview https://www.geeksforgeeks.org/t
Based Problems on LL. op-20-linked-list-interview-
question/
Stack Interview Questions:
Interview Problems Based on
https://medium.com/techie-
Stacks.
delight/stack-data-structure-
practice-problems-and-interview-
questions-9f08a35a7f19
28-30 Binary Trees – 1: Binary Trees https://www.geeksforgeeks.org/
(Definition, Implementation, binary-tree-data-structure/
Algorithms on Trees (DFS,
BFS, etc.), Standard Problems
on Trees)
31-36 Binary Trees – 2: Interview https://www.geeksforgeeks.org/t
Problems Based on Trees. op-50-tree-coding-problems-for-
interviews/
Binary Search Trees – 1:
Implementation of BST,
https://www.javatpoint.com/bin
Standard Problems on BST.
ary-search-tree
Binary Search Trees – 2:
Interview Problems Based on https://www.techiedelight.com/b
Trees. inary-search-tree-bst-interview-
questions/
37-40 Hashmaps-2: Advance https://www.geeksforgeeks.org/t
Hashing Techniques, op-20-hashing-technique-based-
Interview Problems based interview-questions/
Hashing etc.
Priority Queue-2: Advance https://www.hackerearth.com/pr
Problems on Heaps. actice/notes/heaps-and-priority-
queues/
41-46 DP-1: DP, Types of DP, https://www.hackerearth.com/pr
Importance of DP, 1-D DP actice/algorithms/dynamic-
company oriented questions. programming/introduction-to-
dynamic-programming-
DP-2: Discussion on 2D DP
1/tutorial/
and Grid DP and Advance
Problems based on that.
https://www.scaler.com/topics/d
DP-3: Knapsack and Selecting ata-structures/2d-dp-problems/
Distinct based DP.
https://www.geeksforgeeks.org/
DP-4: Problems based on DP
0-1-knapsack-problem-dp-10/
Patterns.
DP-5: Multi-dimensional DP https://leetcode.com/discuss/ge
neral-
DP-6: DP on Trees. discussion/458695/dynamic-
programming-patterns
https://www.upwork.com/resour
ces/what-is-dynamic-
programming
https://itnext.io/introduction-to-
multi-dimensional-dynamic-
programming-666b095b2e7b
Advanced Data Structures / CS192 Page 5 of 9
Course Plan
https://codeforces.com/blog/ent
ry/20935
47-48 Greedy Algorithms-2: https://www.interviewbit.com/c
Advance Problems on Greedy. ourses/programming/bit-
Bit-masking-2: Interview manipulation/
Based Problems on Bit
Manipulations.
49-51 Number Theory: Prime Sieve, https://www.geeksforgeeks.org/s
Segmented Sieve, Euclid egmented-sieve/
Algorithm, Extended Euclid
Algorithm and Its Application
https://www.geeksforgeeks.org/
in solving linear Diophantine
equations and multiplicative euclidean-algorithms-basic-and-
modulo inverse, Totient extended/
Equation, Fermat Little
Theoram etc. https://www.geeksforgeeks.org/
multiplicative-inverse-under-
modulo-m/
Maths: Big Integers,
Combinatory, Solving Linear https://www.geeksforgeeks.org/
Recurrences, Mathematical eulers-totient-function/
Expectation etc.
https://www.geeksforgeeks.org/f
ermats-little-theorem/
https://www.hackerearth.com/pr
actice/math/combinatorics/basic
s-of-combinatorics/tutorial/
https://www.tutorialspoint.com/
discrete_mathematics/discrete_
mathematics_recurrence_relatio
n.htm
https://www.statisticssolutions.c
om/free-resources/directory-of-
statistical-
analyses/mathematical-
expectation/
52-60 Graphs-1: Undirected Graphs, https://www.geeksforgeeks.org/
Cycle Detection, shortest detect-cycle-undirected-graph/
cycle in an undirected graphs
etc, Directed Graphs,
https://www.geeksforgeeks.org/t
Topological sort, Cycle
Detection in an directed opological-sorting/
graphs)
https://practice.geeksforgeeks.or
Graphs-2: Kosaraju algorithm, g/problems/strongly-connected-
DSU and Problems based on components-kosarajus-algo/1
the above mentioned topics.
https://www.geeksforgeeks.org/k
Graphs-3: Minimum Spanning
Trees, Kruskal's and Prism's ruskals-minimum-spanning-tree-
Algorithm, Introduction to algorithm-greedy-algo-2/
Weighted Graphs.
https://www.geeksforgeeks.org/
Graphs-4: Dijkstra's, Bellman dijkstras-shortest-path-algorithm-
ford algorithms and Problems greedy-algo-7/
based on the above
mentioned Topics.
Advanced Data Structures / CS192 Page 6 of 9
Course Plan
https://www.geeksforgeeks.org/
Graphs-5: Advance problems bellman-ford-algorithm-dp-23/
on Graphs.
https://www.codingninjas.com/c
odestudio/library/important-
graph-problems-for-interviews-
advanced-problems
61-64 Tries: Introduction, Range https://www.geeksforgeeks.org/i
Queries and Interview ntroduction-to-trie-data-
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 100% At the end of the semester 60%
Examination*
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 7 5%
Binary Search
Advanced Data Structures / CS192 Page 7 of 9
Course Plan
Array Advanced Algorithms – 1
Array Advanced Algorithms- 2
Strings
Sliding Window – 1
7 5%
Advanced String Algorithms
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:
http://www.beehyve.io/ - this is a community of CS students studying the same topics
http://www.geeksforgeeks.org/ - explains all the high level fundamentals
https://visualgo.net/en - has visualizations of a lot of helpful algorithms
International Courses:
CS 226 Algorithms and Data Structures: http://www.cs.princeton.edu/courses/archive/fall14/cos226/info.php
Brown CS 16 - Introduction to Algorithms and Data Structures: http://cs.brown.edu/courses/cs016/
Stanford CS 166 Data Structures: http://web.stanford.edu/class/cs166/
University of Washington, St. Louis (CSE241) Algorithms and Data Structures:
http://classes.engineering.wustl.edu/cse241/
Harvard CSE 22 Data Structures: http://sites.fas.harvard.edu/~cscie22/
Advanced Data Structures / CS192 Page 8 of 9
Course Plan
Michigan EECS 281 Data Structures and Algorithms:
http://web.eecs.umich.edu/~sugih/courses/eecs281/syllabus.html
Cornell CS 2110 OO Programming and Data Structures: http://www.cs.cornell.edu/courses/cs2110/2016fa/
MiT 6.006 Introduction to Algorithms: https://ocw.mit.edu/courses/electrical-engineering-and-computer-
science/6-006-introduction-to-algorithms-spring-2008/
Important links:
https://www.udemy.com/course/learning-data-structures-and-algorithms/
https://www.coursera.org/specializations/data-structures-algorithms
https://hackr.io/tutorials/learn-data-structures-algorithms
https://www.edx.org/course/algorithms-and-data-structures
https://www.codingninjas.com/courses/onlline-c-plus-plus-course
https://swayam.gov.in/nd1_noc20_cs85/preview
https://www.niit.com/india/short-term-courses/information-technology/data-structures-and-algorithms
https://practice.geeksforgeeks.org/courses/dsa-self-paced
https://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
https://www.youtube.com/channel/UCu4ztYtW-Bg1KIfcLAULtVQ
https://nptel.ac.in/courses/106/102/106102064/
https://www.swayamprabha.gov.in/index.php/program/archive/13
https://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
https://swayam.gov.in/nd2_cec19_cs04/preview
This document is approved by:
Designation Name Signature
