ASSIGNMENT
DESIGN AND ANALYSIS OF ALGORITHMS
By
Student Name:
Roll Number:
Semester: 3rd (A5)
Department of Computer Science and Engineering
Model Institute of Engineering & Technology (Autonomous)
(Permanently Affiliated to the University of Jammu, Accredited by NAAC with “A” Grade)
Jammu, India
2025
Assignment: COM-301
ASSIGNMENT
Subject Name / Course Code: Design and Analysis of Algorithms (COM-301)
Due Date: 29-11-2025
Question Course Maximum Marks
Bloom’s Level
Number Outcomes Marks Obtained
Q1 CO1 3 4
Q2 CO2 4 4
Q3 CO3 4 4
Q4 CO4 4 4
Q6 CO5 5 4
Total Marks 20
Faculty Signature
Email: [Link]@[Link]
Contact No : 8988096116
Assignment Objectives:
1. To apply syllabus-based algorithmic concepts through clear reasoning, structured analysis, and
Python implementations.
2. To validate algorithm correctness and performance using concise explanations, intermediate
steps, and well-organised outputs.
Assignment Instructions:
1. Group Size: 4-6 students
2. Assessment Rubrics: The evaluation will be done as per the rubrics.
3. Submission Method: All the students will submit their individual hard copy of assignment
and upload the same on Camu LMS on or before the Due date. No late submissions will be
considered for the evaluation.
Guidelines for Solving Assignment:
1. Each question may include explanation, analysis, design steps, and implementation.
Students must address every requirement in the question to receive full marks.
2. Code should be properly indented, commented, and readable. Screenshots or pasted output should
reflect the actual execution of your code.
3. When questions involve algorithm design, complexity analysis, or multi-step procedures, provide
intermediate steps (not just the final answer). Clarity of reasoning is essential for evaluation.
4. Do not copy diagrams, text, or code from external sources or friends. All explanations and
representations (charts, tables, sketches, code) must be your own. Plagiarism beyond permissible
limits will result in marks deduction.
Model Institute of Engineering and Technology (Autonomous), Jammu
Assignment: COM-301
Q. Questions BL CO Marks
No.
1 Design a Divide & Conquer algorithm to count the number of local 3 CO1 4
maxima in an array (a local maximum is an element greater than both its
neighbors).
Your submission must include:
a) Clear explanation of how the array will be divided and combined.
b) Well-structured pseudocode of the Divide & Conquer algorithm.
c) Manual trace of the algorithm on the array: [4, 7, 3, 9, 2, 11, 8, 5].
d) Python implementation of your algorithm.
e) Output showing the number of local maxima detected.
Expected Output: Explanation, pseudocode, trace, Python code + output.
2 Implement Binary Search Tree (BST) and Priority Queue (Min-Heap) 4 CO2 4
and compare their insertion performance.
Your submission must include:
a) Python implementation of BST insertion.
b) Python implementation of Min-Heap insertion.
c) Generate datasets of size 6000: Random and Sorted.
d) Measure total insertion time for both structures on both datasets.
e) Present results in a table: Input Type, BST Time, Min-Heap Time,
Observation.
f) Write a short explanation (4–5 lines) on how input ordering affects
BST performance.
Expected Output: Code, timing table, explanation.
3 Use Disjoint Set Union (Union–Find) to detect cycles in an undirected 4 CO3 4
graph.
Your submission must include:
a) Create a graph with 10 vertices and 12–14 edges.
b) Apply Union–Find with path compression and union by rank for each
edge.
c) Show manual union steps for the first 6 edges.
d) Write Python code for cycle detection using Union–Find.
e) Output showing whether a cycle exists and which edge introduces it.
Expected Output: Graph, manual steps, code + output.
4 Apply Dynamic Programming to compute the Longest Palindromic 4 CO4 4
Subsequence (LPS) for the string:
“ALGORITHMSANDDATASTRUCTURES”.
Your submission must include:
a) Fully filled DP table.
b) Explanation of key DP transitions.
c) Final LPS length + one valid subsequence.
d) Python code.
e) Output confirming DP result.
Expected Output: DP table, explanation, LPS, code + output.
Model Institute of Engineering and Technology (Autonomous), Jammu
Assignment: COM-301
5 Compare BFS, DFS, and Topological Sort performance on a DAG. 5 CO5 4
Your submission must include:
a) Construct a DAG with 8–10 vertices.
b) Manual BFS traversal (show queue state).
c) Manual DFS traversal (stack/recursion).
d) Python code for BFS, DFS, Topological Sort.
e) Execution time comparison table.
f) Detailed explanation of differences.
Expected Output: Graph, manual steps, code, timing table, explanation.
Rubrics for Assessment
Parameters Criteria Marks
Distribution
1 2 3 4 5
The content was The content was The content The content The content
Writing Skills not relevant to minimally was generally was relevant was very
the given task relevant to the relevant to the to the given relevant to the 2
a) Content given task given task task given task
The assignment The organization The The The assignment
is poorly of the assignment organization organization is very well
organized and is somewhat of the of the organized and
b) Organization lacked supporting organized with assignment is assignment is supported 2
evidence minimal generally well organized
supporting acceptable and supported
evidence with some
supporting
evidence
c) Grammar- Too many Numerous Several Few No
Mechanics-Usage- grammatical grammatical grammatical grammatical grammatical 1
Spelling errors errors errors errors errors
Student does not Student Student Student Student
Knowledge Skills demonstrate the demonstrates demonstrates demonstrates demonstrates
subject some grasp of the moderate level sufficient level sound subject 5
knowledge subject of the subject of the subject knowledge
knowledge knowledge knowledge
Overall Unable to answer Able to answer Presentation is Presentation is Presentation
Presentation/Viva questions, not questions but not acceptable but of good (including code
prepared and prepared and there are some quality, with a structure,
confidence at all confidence areas that clear effort to comments, user
could be present the interface, and
improved./ work documentation)
Able to professionally is of
answer and exceptionally 10
questions but effectively./ high quality./
with little Able to Able to answer
preparation answer questions very
and questions well well and
Model Institute of Engineering and Technology (Autonomous), Jammu
Assignment: COM-301
confidence and slightly confidently.
confidence Very well
and well prepared
prepared
Format Guidelines
Title Page: Use the Standardized Front Page shared by the Department.
Font and Spacing: Use a Times New Roman in 12-point size.
1.5 line spacing in the entire document, including the title page, headings, and references.
3. Margins: Set 1-inch (2.54 cm) margins on all sides of the paper.
4. Header: Include a header as Assignment and Course Code in the top right corner of each
page (except the title page).
5. Title: Center the title of your assignment at the top of the first page. It should be bold and
capitalized.
6. Headings: Use headings and subheadings to organize your content. Typically, use bold for
main headings (e.g., "Introduction") and italics for subheadings (e.g., "Methods").
7. Page Numbers: Page numbers should be placed in the center of footer of each page, starting
from the second page (the title page is page 1 & should not be numbered).
8. Citations and References: Use a consistent APA citation style to cite references.
9. Figures and Tables: If you include figures or tables, provide clear labels and captions. The
figure number should be placed below the Figure as “Figure 1: Figure name” and for the tables,
the table number must be mentioned above the table as “Table 1: Table name”.
10. Appendices (if needed): Include appendices for supplementary materials, such as charts,
graphs, or lengthy data tables.
11. Submission Format: Submit your assignment in the soft copy format as PDF and upload it
on CAMU as per the submission deadline. Please ensure that the assignment is renamed as Roll
Number.
12. Proofreading and Editing: Carefully proofread and edit your assignment for clarity,
grammar, and spelling errors before submission.
13. Plagiarism: Plagiarism must be below 15 percent for the assignment submitted.
Model Institute of Engineering and Technology (Autonomous), Jammu