Course Plan

A. Course Handout (Version 1.0)

Institute/School Name Chitkara University Institute of Engineering and Technology

Department Name Department of Computer Science & Engineering
Programme Name Bachelor of Engineering (B.E.), Computer Science & Engineering
Course Name Java Programming Session 2024-2025
Semester/Batc
Course Code 22CS031 5th /2022
h
L-T-P (Per Week) 2-0-4 Course Credits 04
Course Coordinator Ms. Shivani Wadhwa

CLO01 Understand and apply the concept of algorithm complexity.

CLO02 Proficiency in implementing hash tables, heaps, priority queues.
Implement the advanced sorting algorithms and apply appropriate algorithm for a
CLO03
particular problem.
CLO04 Apply the concepts and theories of different algorithmic strategies.
CLO05 Design the problems by understanding and utilizing graph algorithms.

1. Objectives of the Course

The scope of the course is to provides the foundation for understanding the key aspects of java
programming and implementation obtaining a theoretical understanding of advance programming
concepts. The objectives of the course are:
• to build an understanding of analysing and evaluating algorithm efficiency.
• to inculcate the skill in students to implement and optimize data structures.
• to develop and apply advanced sorting and searching algorithms.
• to solve complex problems using greedy algorithms, backtracking, and dynamic programming.

2. Course Learning Outcomes

After completion of the course, student should be able to:

Course Learning Outcome *POs **CL ***KC Sessions

Understand and apply the concept of PO2, PO3, PO5, K1 Conceptual 15

CLO01 PO12
algorithm complexity.
Proficiency in implementing hash PO1, PO4, PO5, K3 Conceptual 15
CLO02 PO12 Procedural
tables, heaps, priority queues.
Implement the advanced sorting PO1, PO2, PO3, K4 Conceptual 28
CLO03 algorithms and apply appropriate PO4, PO5, PO7, Procedural
algorithm for a particular problem. PO11
Apply the concepts and theories of PO3, PO4, PO5, K4 Procedural 12
CLO04 PO6, PO8
different algorithmic strategies.

Page 1 of 10
Java Programming / 22CS031
 Course Plan

Design the problems by PO4, PO5 K5 Conceptual 20

CLO05 understanding and utilizing graph Procedural
algorithms.
Total Contact Hours 90
Revised Bloom’s Taxonomy Terminology
* PO’s available at ([Link]/cryzF)
**Cognitive Level =CL
***Knowledge Categories = KC

Course PO1 PO PO PO4 PO PO6 PO7 PO8 PO9 PO10 PO11 PO12
Learning 2 3 5
Outcomes
CLO01 H H H M H
CLO02 H H H M M H
CLO03 H H H H H H H
CLO04 H H H H H
CLO05 H H H H M H M M
H=High, M=Medium, L=Low

3. ERISE Grid Mapping

Feature Enablement Level (1-5, 5 being highest)

Entrepreneurship 1

Research 4

Innovation 2

Skills 5

Employability 5

4. Recommended Books:

Text Books:
B01: "Head First Java" by Kathy Sierra and Bert Bates, Shroff, 2nd Edition, 2009.
B02: "Java: A Beginner's Guide" by Herbert Schildt, McGraw-Hill Education, 9th Edition, 2022.
B03: “Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, and Clifford Stein, MIT press, 3rd Edition, 2009.
B04: "Design and Analysis of Algorithms" by S. Sridhar, Oxford University Press, 2014.
B05: "Algorithms Illuminated" by Tim Roughgarden, LLC, 2019

Page 2 of 10
Java Programming / 22CS031
 Course Plan

Reference Books:
B03: “Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
and Clifford Stein, MIT press, 3rd Edition, 2009.

E-Resources:
● [Link]

5. Other readings and relevant websites:

Serial No Link of Journals, Magazines, websites and Research Papers

1. [Link]
2. [Link]
position/
3. [Link]
hashing/
4. [Link]
5. [Link]
6. [Link]

6. Recommended Tools and Platforms

Code Quotient

7. Course Plan:

Lecture Topics Text Book

Number
B03-Chpater-1
Concept of Algorithm complexity- Big O notation,
1-2
Algorithm complexity-Average, best and worst case
Practice Problem: Prime Factorization, GCD of two B03-Chapter-1
3-4
numbers , Distribute in circle
Introduction to Hash Table, Collision, Collision Avoidance B03-Chapter-12
5-6 Strategies- Linear Probing, quadratic probing, Separate
Chaining
Practice Problem: Noise In The Library, Try balancing the B03-Chapter-12
7-8
scale, Find out the winner
Heap and Priority Queues: Heap Sort, Implement Priority B03-Chapter-20
9-12
Queue using Linked List
Practice Problem: Find max/min in the continuous stream B03-Chapter-20
13-14 of data, Sort an array using heap sort, Check if a given tree
is max-heap or not
Introduction to Binary Tree, Creating Binary Tree, Tree B03-Chapter-13
15-16
Traversal
Binary Search Trees: Insertion and Deletion, Binary Search B03-Chapter-13
17-20
Trees Traversals

Page 3 of 10
Java Programming / 22CS031
 Course Plan

Practice Problem: Find a lowest common ancestor of a B03-Chapter-13

21-22 given two nodes in a binary search tree, Find the kth
smallest element in the binary search tree
Divide and Conquer Strategies: Binary search Algorithm, B03-Chapter-7
23-26
Merge Sort, Quick Sort and Analysis
Practice Problem: Count Inversions, Find frequency of each B03-Chapter-7
27-28
element in a limited range array in less than O(n) time
29-30 Greedy Algorithms : Fractional Knapsack problem B03-Chapter-17
Practice Problem: Interval scheduling, Job Scheduling with B03-Chapter-17
31-34
deadlines
35-36 Backtracking: Introduction, N-Queen Problem B04-Chapter-20
Practice Problem: Robot Movement, Solve Sudoku, Rat in B04-Chapter-20
37-40
a Maze, Print all strings of n-bit
ST-1 Syllabus (Lecture number 1-40)
Dynamic Programming: Introduction, Memorization, B03-Chapter-16
41-42
Tabulation
Practice Problem: Longest Common Subsequence (LCS), B03-Chapter-16
43-46 Count number of ways to cover a distance, Matrix Chain
Multiplication problem, 0-1 Knapsack problem
Introduction to Graphs: edge list, adjacency matrix and B03-Chapter-23
47-48
adjacency list
49-50 Graph traversal: BFS, DFS B03-Chapter-23
Practice Problem: B03-Chapter-23
Find the cycle in undirected graph, Find the minimum
51-54
number of edges in a path of a graph, Find path in a
directed graph
55-60 Shortest Path Algorithm- Dijkstra, Bellman Ford, Floyd B03-Chapter-25, 26
Warshal Algorithm, Shortest path in a binary maze
61-64 Minimum Spanning Trees- Prim’s Algorithm, Kruskal’s B03-Chapter-24
Algorithm
65-66 Graphs Algorithms: Topological Sorting Algorithm B03-Chapter-27

67-68 Practice Problem: Find the number of islands B03-Chapter-27

69-74 String Algorithms: Manacher, Z-value Algorithm, KMP B03-Chapter-34

ST-2 Syllabus (Lecture number 41-74)

75-80 AVL Trees: Introduction, Insertion, Deletion B03-Chapter-13

81-86 Red Black Trees: Introduction, Insertion, Deletion B03-Chapter-14

87-90 Introduction to tries, Suffix Arrays, Longest Repeated B03-Chapter-34
string - Overlapping and Non overlapping
ETE (Syllabus = (Lecture number 1-90)

8. Delivery/Instructional Resources

Page 4 of 10
Java Programming / 22CS031
 Course Plan

Lecture
Topics Web References Audio-Video
No.
Concept of Algorithm complexity- [Link]
Big O notation, Algorithm [Link]/news/big-o- [Link]
1-2
complexity-Average, best and cheat-sheet-time- m/watch?v=HfIH3czXc-8
worst case complexity-chart
[Link]
Practice Problem: Prime [Link]
[Link]/distributing-
3-4 Factorization, GCD of two numbers m/watch?v=5gFC-
m-items-circle-size-n-
, Distribute in circle ayyQMk
starting-k-th-position/
Introduction to Hash Table, [Link] [Link]
Collision, Collision Avoidance [Link]/open- m/watch?v=W5q0xgxmR
5-6 Strategies- Linear Probing, addressing-collision- d8&list=PLxM5rzx4f4fwO
quadratic probing, Separate handling-technique-in- PORqEZZhaaY5OG0WMZf
Chaining hashing/ F
[Link]
Practice Problem: Noise In The [Link]
[Link]/find-the-
7-8 Library,Try balancing the scale, Find m/watch?v=8uFWG6xfku
winner-of-the-game-
out the winner c
2/
[Link]
Heap and Priority Queues: Heap [Link]
[Link]/priority-
9-12 Sort, Implement Priority Queue m/watch?v=HqPJF2L5h9
queue-using-linked-
using Linked List U
list/
Practice Problem: Find max/min in [Link]
[Link]
the continuous stream of data, Sort [Link]/practice/note
13-14 m/watch?v=NKJnHewiGd
an array using heap sort, Check if a s/heaps-and-priority-
c
given tree is max-heap or not queues/
Introduction to Binary Tree, [Link]
[Link]
15-16 Creating Binary Tree, Tree m/topics/traversal-of-
m/watch?v=I_JuQ5ayPmc
Traversal binary-tree/
Binary Search Trees: Insertion and [Link]
[Link]
17-20 Deletion, Binary Search Trees maths/binary-search-
m/watch?v=cySVml6e_Fc
Traversals tree
Practice Problem: Find a lowest
[Link]
common ancestor of a given two
[Link]/lowest-
21-22 nodes in a binary search tree, Find [Link]
common-ancestor-in-
the kth smallest element in the
a-binary-search-tree/
binary search tree
[Link]
Divide and Conquer Strategies: [Link]/computing/
23-26 Binary search Algorithm, Merge computer- [Link]
Sort, Quick Sort and Analysis science/algorithms/m
erge-sort/
[Link]
Practice Problem: Count Inversions, [Link]/find-
Find frequency of each element in frequency-of-each-
27-28 [Link]
a limited range array in less than element-in-a-limited-
O(n) time range-array-in-less-
than-on-time/

Page 5 of 10
Java Programming / 22CS031
 Course Plan

[Link] [Link]
Greedy Algorithms : Fractional
29-30 [Link]/fractional- m/watch?v=oTTzNMHM0
Knapsack problem
knapsack-problem/ 5I
Practice Problem: Interval [Link]
[Link]
31-34 scheduling, Job Scheduling with [Link]/job-
m/watch?v=zPtI8q9gvX8
deadlines sequencing-problem/
[Link]
Backtracking: Introduction, N- [Link]
35-36 [Link]/blog/backtracki
Queen Problem m/watch?v=xFv_Hl4B83A
ng/

Practice Problem: Robot [Link]

37-40 Movement, Solve Sudoku, Rat in a [Link]/rat-in-a- [Link]
Maze, Print all strings of n-bit maze/

Dynamic Programming: [Link]

41-42 Introduction, Memorization, [Link]/tabulation- [Link]
Tabulation vs-memoization/
Practice Problem: Longest
Common Subsequence (LCS), Count [Link]
number of ways to cover a [Link]/0-1- [Link]
43-46
distance, Matrix Chain knapsack-problem-dp- m/watch?v=PfkBS9qIMRE
Multiplication problem, 0-1 10/
Knapsack problem
Introduction to Graphs: edge list,
47-48 [Link] [Link]
adjacency matrix and adjacency list
[Link] [Link]
49-50 Graph traversal: BFS, DFS [Link]/difference- m/watch?v=N2P7w22tN9
between-bfs-and-dfs/ c
Practice Problem:
[Link]
Find the cycle in undirected graph,
[Link]/detect- [Link]
51-54 Find the minimum number of
cycle-undirected- m/watch?v=porShXfpPqA
edges in a path of a graph, Find
graph/
path in a directed graph
55-60 Shortest Path Algorithm- Dijkstra, [Link]
Bellman Ford, Floyd Warshal [Link]/floyd- [Link]
Algorithm, Shortest path in a binary warshall-algorithm-dp- m/watch?v=Gd92jSu_cZk
maze 16/
61-64 Minimum Spanning Trees- Prim’s [Link]
[Link]
Algorithm, Kruskal’s Algorithm e/difference-between-
m/watch?v=_KX8GDvRzB
prims-and-kruskal-
c
algorithum/
65-66 Graphs Algorithms: Topological [Link]
Sorting Algorithm [Link]
[Link]/topological-
m/watch?v=3tkcfvCNtM8
sorting/

Page 6 of 10
Java Programming / 22CS031
 Course Plan

67-68 Practice Problem: Find the number

[Link]
of islands
[Link]/find-the- [Link]
number-of-islands- m/watch?v=muncqlKJrH0
using-dfs/
69-74 String Algorithms: Manacher, Z-
[Link]
value Algorithm, KMP [Link]
[Link]/z-algorithm-
m/watch?v=V5-
linear-time-pattern-
7GzOfADQ
searching-algorithm/
75-80 AVL Trees: Introduction, Insertion,
Deletion [Link] [Link]
[Link]/insertion-in- om/watch?v=YWqla0UX
an-avl-tree/ -38

81-86 Red Black Trees: Introduction, [Link] [Link]

Insertion, Deletion [Link]/introductio om/watch?v=3RQtq7PD
n-to-red-black-tree/ Hog
87-90 Introduction to tries, Suffix Arrays,
[Link]
Longest Repeated string - [Link]
[Link]/longest-
Overlapping and Non overlapping om/watch?v=ZyLXuDNIA
repeating-and-non-
vQ
overlapping-substring/

9. Action plan for different types of learners

Slow Learners Average Learners Fast Learners

• Remedial Classes on • Workshops • Engaging students to hold
Saturdays • Formative Exercises used hands of slow learners by
• Encouragement for to highlight concepts and creating a Peer Tutoring
improvement using Peer notions Group
Tutoring • E-notes and E-exercises • Design solutions for complex
• Use of Audio and Visual to problems
Materials read ahead of the • Design solutions for
• Use of Real-Life Examples pedagogic material. complex problems
• Presentation on topics beyond
those covered in CHO

10. Evaluation Scheme & Components:

Evaluation No. of Weightage of Mode of

Type of Component
Component Assessments Component Assessment
Subjective Test/Sessional Offline exam
Component 2 02* 40%
Tests (STs)

Component 3 End Term Examinations 01** 60% Offline exam

Total 100%

Page 7 of 10
Java Programming / 22CS031
 Course Plan

* As per Academic Guidelines, a minimum of 75% attendance is required to become eligible for
appearing in the End Semester Examination.

11. Syllabus of the Course:

Subject: Java Programming / 22CS031

No. of
S. No. Topic (s) Weightage %
Sessions
1 Concept of Algorithm complexity- Big O notation,
Algorithm complexity-Average, best and worst case,
Introduction to Hash Table, Collision, Collision
Avoidance Strategies- Linear Probing, quadratic
probing, Separate Chaining, Heap and Priority Queues:
Heap Sort, Implement Priority Queue using Linked List,
Divide and Conquer Strategies: Binary search
40 40%
Algorithm, Merge Sort, Quick Sort and Analysis, Greedy
Algorithms: Fractional Knapsack problem,
Backtracking: Introduction, N-Queen Problem

ST-1 (Covering 40% syllabus)

2 Dynamic Programming: Introduction, Memorization,
Tabulation, Introduction to Graphs: edge list,
adjacency matrix and adjacency list, Graph traversal:
BFS, DFS
Shortest Path Algorithm- Dijkstra, Bellman Ford, Floyd 34 40%
Warshal Algorithm, Minimum Spanning Trees- Prim’s
Algorithm, Kruskal’s Algorithm, Graphs Algorithms:
Topological Sorting Algorithm, String Algorithms:
Manacher, Z-value Algorithm, KMP
ST-2 (Covering 40% syllabus)
3 AVL Trees: Introduction, Insertion, Deletion, Red-Black
Trees: Introduction, Insertion, Deletion, Introduction
to tries 16 20%
Suffix Arrays, Longest Repeated string - Overlapping
and Non overlapping
End Term 100% syllabus

Page 8 of 10
Java Programming / 22CS031
 Course Plan

This Document is approved by:

Designation Name Signature

Course Coordinator Ms. Shivani Wadhwa
Head-Academic Delivery Dr. Susheela Hooda
Dean Dr. Rupali Gill
Dean Academics Dr. Monit Kapoor
Date 10.07.2024

Page 9 of 10
Java Programming / 22CS031