Year: II

Semester: III

1. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
2. Course : Design and Analysis of Algorithms L: 3
3. Program : B.Tech CCVT T: 0
4. Target : 45% P: 0
C: 3
COURSE PLAN
Target 50% (marks)
Level-1 40% (population)
Level-2 50% (population)
Level-3 60% (population)

1. Method of Evaluation

UG PG
Quizzes/Tests, Assignments (30%) Quizzes/Tests, Assignments, seminar (50%)
Mid Examination (20%) End semester (50%)
End examination (50%)

2. Passing Criteria

Scale PG UG
Out of 10 point scale SGPA – “6.00” in each semester SGPA – “5.0” in each semester
CGPA – “6.00” CGPA – “5.0”
Min. Individual Course Grade  –  “C” Min. Individual Course Grade  –  “C”
Course Grade  Point –  “4.0” Course Grade  Point –  “4.0”

*for PG, passing marks are 40/100 in a paper

*for UG, passing marks are 35/100 in a paper

3. Pre-requisites: Basic knowledge of Mathematics and data structure

4. Course Objectives:
1. To understand the necessity of the algorithm design.
2. To write the algorithm to solve a problem.
3. To analyze the performance of the algorithm.
4. To implement the algorithm in C/C++.

5. Pedagogy
 Presentations
 Flipped Classroom sessions
 Think-Pair-Share Activities
 Video Lectures

6. References:
Text Books 1. Thomas H. Cormen (2009) Introduction to Algorithm (Third Edition), The MIT
Press. ISBN: 978-0-262- 03384-8
 Year: II
Semester: III

1. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
2. Course : Design and Analysis of Algorithms L: 3
3. Program : B.Tech CCVT T: 0
4. Target : 45% P: 0
C: 3
2. John Kleinberg and Eva Tardos (2005), Algorithm Design, ISBN: 0-321-29535-8

Web resources
Journals
Reference books 1. Rajesh K. Shukla (2015) Analysis and Design of Algorithms: A Beginner's
Approach, Wiley, ISBN10: 8126554770
2. S.Sridhar (2014), Design and Analysis of Algorithms 1st Edition, Publisher: Oxford
University Press ISBN: 9780198093695, 0198093691

GUIDELINES TO STUDY THE SUBJECT

Instructions to Students:

1. Go through the 'Syllabus' in the Black Board section of the web-site(https://learn.upes.ac.in) in

order to find out the Reading List.
2. Get your schedule and try to pace your studies as close to the timeline as possible.
3. Get your on-line lecture notes (Content, videos) at Lecture Notes section.  These are our lecture
notes. Make sure you use them during this course.
4. Check your blackboard regularly
5. Go through study material
6. Check mails and announcements on blackboard
7. Keep updated with the posts, assignments and examinations which shall be conducted on the
blackboard
8. Be regular, so that you do not suffer in any way
9. Cell Phones and other Electronic Communication Devices: Cell phones and other electronic
communication devices (such as Blackberries/Laptops) are not permitted in classes during Tests or
the Mid/Final Examination. Such devices MUST be turned off in the class room.
10. E-Mail and online learning tool: Each student in the class should have an e-mail id and a pass
word to access the LMS system regularly. Regularly, important information – Date of conducting
class tests, guest lectures, via online learning tool. The best way to arrange meetings with us or ask
specific questions is by email and prior appointment. All the assignments preferably should be
uploaded on online learning tool. Various research papers/reference material will be
mailed/uploaded on online learning platform time to time.
11. Attendance: Students are required to have minimum attendance of 75% in each subject. Students
with less than said percentage shall NOT be allowed to appear in the end semester examination.

This much should be enough to get you organized and on your way to having a great semester! If you need
us for anything, send your feedback through e-mail to your concerned faculty. Please use an appropriate
subject line to indicate your message details.
 Year: II
Semester: III

1. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
2. Course : Design and Analysis of Algorithms L: 3
3. Program : B.Tech CCVT T: 0
4. Target : 45% P: 0
C: 3
There will no doubt be many more activities in the coming weeks. So, to keep up to date with all the latest
developments, please keep visiting this website regularly.
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3
RELATED OUTCOMES
1. The expected outcomes of the Program are:

PO1 Engineering knowledge: Apply the knowledge of mathematics, science,

engineering fundamentals, and an engineering specialization to the solution of
complex engineering problems.
PO2 Problem analysis: Identify, formulate, review research literature, and analyze
complex engineering problems reaching substantiated conclusions using first
principles of mathematics, natural sciences, and engineering sciences.
PO3 Design/development of solutions: Design solutions for complex engineering
problems and design system components or processes that meet the specified
needs with appropriate consideration for the public health and safety, and the
cultural, societal, and environmental considerations.
PO4 Conduct investigations of complex problems: Use research-based knowledge
and research methods including design of experiments, analysis and interpretation
of data, and synthesis of the information to provide valid conclusions.
PO5 Modern tool usage: Create, select, and apply appropriate techniques, resources,
and modern engineering and IT tools including prediction and modeling to
complex engineering activities with an understanding of the limitations.
PO6 The engineer and society: Apply reasoning informed by the contextual
knowledge to assess societal, health, safety, legal and cultural issues and the
consequent responsibilities relevant to the professional engineering practice.
PO7 Environment and sustainability: Understand the impact of the professional
engineering solutions in societal and environmental contexts and demonstrate the
knowledge of, and need for sustainable development.
PO8 Ethics: Apply ethical principles and commit to professional ethics,
responsibilities, and norms of the engineering practice.
PO9 Individual and Teamwork: Function effectively as an individual, and as a
member or leader in diverse teams, and in multidisciplinary settings.
PO10 Communication: Communicate effectively on complex engineering activities
with the engineering community and with society, such as, being able to
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3
comprehend and write effective reports and design documentation, make effective
presentations, and give and receive clear instructions.
PO11 Project management and finance: Demonstrate knowledge and understanding of
the engineering and management principles and apply these to one’s own work, as
a member and leader in a team, to manage projects and in multidisciplinary
environments.
PO12 Life-long learning: Recognize the need for, and have the preparation and ability
to engage in independent and life-long learning in the broadest context of
technological change.

2. The expected outcomes of the Specific Program are:

PSO1 Perform system and application programming using computer system concepts,
concepts of Data Structures, algorithm development, problem solving and
optimizing techniques
PSO2 Apply software development and project management methodologies using
concepts of front-end and back-end development and emerging technologies and
platforms.
PSO3 Ability to design, develop and manage scalable IT Infrastructure.

3. The expected outcomes of the Course are:

CO 1 Apply mathematical Techniques to find the complexity of algorithm

CO 2 Analyze algorithms and express asymptotically different case behavior

CO 3 Demonstrate good principles of algorithm designs

CO 4 Design appropriate data structures to reduce the complexity of an algorithm.

CO 5 Differentiate among about P, NP-Hard and NP-Complete problems.

4. Co-Relationship Matrix
Indicate the relationships by1- Slight (low) 2- Moderate (Medium) 3-Substantial (high)

Progra PO PO PO PO PO PO PO PO PO PO PO PS PS
PO
m 2 3 4 5 6 7 8 9 10 11 12 O1 O2
1
Outcom PS
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3
es O3

Course
Outcom
es
CO 1 3 3 1 2 3 1

CO 2 3 3 2 2 3 1

CO 3 2 2 2 1 3 1

CO 4 2 3 2 1 3 1

CO 5 3 2 1 3 3 1

Average 2.6 2.6 1.6 1.8 3 1

5. Course outcomes assessment plan:

components

Course Assignment Test/Quiz Mid Semester End Semester Any other

Outcomes


CO 1    

CO 2    

CO 3    
CO 4
CO 5

BROAD PLAN OF COURSE COVERAGE

Course Activities:
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3
Planned
Remar
Unit Description Fro
To No. of Sessions ks
m
Algorithm, Psuedo code, Performance CO1
Analysis- Space complexity, Time complexity,
Asymptotic Notation- Big oh notation, Omega
notation, Theta notation with numerical,
1 different algorithm design techniques,
recurrence relation, solving methods:
substitution ,recursion tree, master theorem
with numerical.
CO2
Binary search, Quick sort: best case & worst
2
case analysis, Merge sort
Activity selection problem, knapsack CO3
problem, Minimum cost spanning trees:
3 Prims and kruskal, Single source shortest
path problem: Bellman ford, dijkstra’s,
Huffman codes.

CO4
Matrix chain multiplication, 0/1 knapsack
4 problem, All pairs shortest path problem,
largest common subsequence.
CO4
Lower Bounds For Sorting, Counting Sort,
5 Radix Sort, bucket sort Backtrackingsum of
subsets problem, graph coloring,
CO5
NP-Hard and NP-Complete problem and
6
concepts

Sessions: Total No. of Instructional periods available for the course

SESSION PLAN
UNIT-I
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3

Lectur CO
e No. Topics to be Covered Mapped
CO1
 1, 2  Algorithm, Pseudo code

3,4 Performance Analysis- Space complexity, Time complexity, examples

 Asymptotic Notation- Big oh notation, Omega notation, Theta notation with CO1
 5,6 numerical,

7,8  different algorithm design techniques, recurrence relation

CO1
 9,10  solving methods: substitution
CO1
 11,12  solving methods: recursion tree

13,14 master theorem with numerical

CO1
 15
CO1
 16
CO1
17
CO1
18

SESSION PLAN
UNIT-II
Lecture No. Topics to be Covered CO Mapped
 Divide and conquer: Binary search and case analysis,
 19 examples  CO2
 Divide and conquer: Quick sort: best case & worst case CO2
 20,21 analysis
CO2
 22  Merge sort & Analysis
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3
SESSION PLAN
UNIT-III

Lecture No. Topics to be Covered CO Mapped

Greedy method: activity selection problem
 23  CO3
knapsack problem(fractional) CO3
 24
Minimum cost spanning trees: Prims, kruskal. CO3
 25
Single source shortest path problem: dijkstra’s CO3
 26
Single source shortest path problem: Bellman ford CO3
 27
Huffman codes. CO3
28

SESSION PLAN
UNIT-IV

Lecture No. Topics to be Covered CO Mapped

Dynamic Programming: Matrix chain multiplication CO4
 29
0/1 knapsack problem, All pairs shortest path problem CO4
 30
largest common subsequence CO4
31
SESSION PLAN
UNIT-V
Lecture
No. Topics to be Covered CO Mapped
Sorting in linear time: lower bounds for sorting, counting sort, radix
 32 sort  CO4
 Year: II
Semester: III

5. Name of the Faculty: Dr Rahul Nijhawan Course Code:

CSEG2021
6. Course : Design and Analysis of Algorithms L: 3
7. Program : B.Tech CCVT T: 0
8. Target : 45% P: 0
C: 3
sum of subsets problem CO4
 33
graph coloring, examples  CO4
 34

SESSION PLAN
UNIT-VI
Lecture
No. Topics to be Covered CO Mapped
Branch and Bound method knapsack problem, examples
 35  CO5
NP-Hard and NP-Complete problem and concepts, examples CO5
 36