Assignment 1

CS F364 — Design & Analysis of Algorithms | Summer 2026

Assignment 1

CS F364 — Design & Analysis of Algorithms Summer 2026

Due30 Jun 2026, 2:00 PM

Weight10%

SubmissionIndividual

Final markScore (out of 50) × Viva ÷ 10The viva score (0–10) acts as a weightage multiplier to verify the work is genuinely your own. High viva = you keep most of your marks. Low viva = proportional reduction.

How it works

1

Pick one of the four problems below.

2

Solve it in Python, C, or C++. Discussion allowed, but the code you submit must be entirely your own.

3

Upload your single source file as <rollno>_assignment1.<ext> to Google Classroom before the deadline.

4

Attend a 1-on-1 viva. Your assignment is scored out of 50. The viva (out of 10) decides what fraction of that score you keep: Final = Score × (Viva ÷ 10).

Make sure your code compiles and runs before you submit. It will be tested against hidden test cases. The deadline will not be extended for any reason. Plagiarism will result in a zero grade and disciplinary action.

Choose a Problem

A

Closest Pair of Points

Find the closest pair among n points in O(n log n) time using the δ-strip optimisation.

B

Longest Common Subsequence

Compute the LCS of two strings and produce an optimal alignment with O(mn) DP.

C

Huffman Coding

Build optimal prefix-free codes, encode a message, and decode it back using a min-heap.

D

Kruskal’s Minimum Spanning Tree

Find the MST using Kruskal’s algorithm with Union-Find and path compression.