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 core algorithmic strategies including divide & conquer, heaps and priority queues,
greedy MST construction, dynamic programming, and string matching.
2. To ensure students validate algorithm behaviour and correctness through structured reasoning,
Python implementation, and clearly presented results.
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 Solve the following recurrence relations using the Master Theorem and 3 CO1 4
verify one experimentally: (a) T(n)=2T(n/3)+n, (b) T(n)=5T(n/4)+n², (c)
T(n)=9T(n/3)+n³.
Your submission must include:
a) Step-by-step solution of all recurrences using Master Theorem.
b) Final Big-O complexity for each.
c) Choose any one recurrence and write a Python script that
approximates its runtime using operation counts for n = 300, 600, 1200,
2400.
d) Present results in a table: Input Size vs Operation Count.
e) A short 3–4 line explanation comparing theoretical vs experimental
growth.
Expected Output: Solved recurrences, complexities, Python code, table,
explanation.
2 Implement Max-Heap, Min-Heap, and Heap Sort, and compare 4 CO2 4
performance across different dataset types.
Your submission must include:
a) Python implementation of Max-Heap, Min-Heap, and Heap Sort.
b) Generate three datasets of size 10,000: Random, Sorted, Reverse
Sorted.
c) Measure insertion time for Max-Heap & Min-Heap, and sorting time
for Heap Sort on each dataset.
d) Present results in a table: Dataset Type, Max-Heap Time, Min-Heap
Time, HeapSort Time, Observation.
e) Write a 5–6 line explanation on why heap operations behave
differently depending on input order.
Expected Output: Code, timing table, explanation.
3 Implement Kruskal’s Algorithm using Union–Find (Disjoint Set Union) 4 CO3 4
with path compression & union by rank.
Your submission must include:
a) A graph with at least 8 vertices & 12–15 weighted edges.
b) Sorted list of edges used by Kruskal’s algorithm.
c) Step-by-step MST construction (edges accepted/rejected).
d) Python implementation of Union–Find + Kruskal.
e) Output showing final MST edges and total cost.
Expected Output: Graph, sorted edges, manual steps, code, MST result.
4 Solve the Traveling Salesman Problem (TSP) using Dynamic 4 CO4 4
Programming for a small distance matrix of 5 cities, chosen by you.
Your submission must include:
a) A 5×5 symmetric distance matrix (choose realistic values).
b) DP table representation for the Held–Karp algorithm (subset DP).
c) Explanation of at least two important subproblem transitions.
d) Python implementation of DP-based TSP.
e) Program output showing the minimum TSP cost and optimal path.
Expected Output: Distance matrix, DP table, explanation, Python code
+ output.
5 Use KMP (Knuth–Morris–Pratt) algorithm to perform efficient string 5 CO5 4
matching and analyse its performance.
Your submission must include:
a) Python implementation of KMP (prefix array + search).
b) Create two strings of length 8,000 and 15,000 and embed a fixed

Model Institute of Engineering and Technology (Autonomous), Jammu

 Assignment: COM-301

pattern 5 times in each.

c) Compare Naïve vs KMP execution time on both strings.
d) Present results in a table: String Length, Naïve Time, KMP Time,
Observations.
e) Write 3–4 lines explaining how preprocessing improves performance.
Expected Output: Code (both methods), 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
confidence and slightly confidently.
confidence Very well
and well prepared
prepared

Model Institute of Engineering and Technology (Autonomous), Jammu

 Assignment: COM-301
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