مساله یکتاسازی بدین شکل تعریف می شود:

• ورودی: یک دنباله از اعداد
• خرووجی: افراز اعداد دنباله ورودی به تعدادی دسته، با این شرط که دو عدد با هم برابر هستند اگر و فقط اگر در یک دسته باشند. (اعداد هر دسته با اندیس‌شان مشخص می‌شوند)

1. اثبات کنید که هر الگوریتم یکتاسازی مبتنی بر مقایسه روی n عنصر از $\Omega(n\log n)$ است.
2. فرض کنید یک لیست مجاورت از یال های یک گراف در اختیار داریم. الگوریتمی خطی $O(n+m)$ برای حذف یال های تکراری در این لیست ارائه دهید. (نکته: درنظر گرفتن یک حافظه به طول $k$ زمان $O(k)$ لازم دارد)
3. آیا الگوریتم شما در قسمت ب، مثال نقضی برای اثبات قسمت الف نیست؟

• سوال بعد
• سوال قبل