پروژه‌ی پژوهشی درس الگوریتم‌های تقریبی شامل موارد زیر است:

• انتخاب یک مسئله و مقاله‌ی مرتبط با آن
• خواندن و درک کامل مقاله
• ارائه در کلاس درس
• تهیه‌ی گزارش پژوهشی (حداکثر ۱۰ صفحه)

مقاله‌ی انتخابی باید حاوی یک الگوریتم تقریبی و اثبات ضریب تقریب آن بوده و حداکثر طی دو سال‌ اخیر در یکی از کنفرانس‌های SODA و APPROX (یا هم‌تراز آن‌ها) ارائه شده باشد. لیست مقالات کنفرانس‌ها در https://dblp.org/db/conf/soda/index.html قابل مشاهده است. نسخه‌ی الکترونیکی مقالات را می‌توانید معمولاً از طریق Google Scholar پیدا کنید.

اطلاعات مقاله‌ی انتخابی برای تایید و قرار گرفتن در فهرست ارائه‌های پژوهشی باید در این قالب مشخص به مدرس اعلام شود: «نام دانش‌جو: عنوان مقاله. نام نویسندگان، نام و سال کنفرانس». مثالی از قالب صحیح اطلاعات یک مقاله در زیر آمده است.

هر دانش‌جو مقاله‌ی انتخابی خود را در زمان برنامه‌ریزی‌شده (معمولا بین ۱۵ تا ۲۰ دقیقه) در کلاس درس ارائه می‌نماید. در ارائه‌ی مقاله هدف عمده این است که تعریف روشنی از مسئله ارائه شده و ایده‌های اصلی راه حل به سایر دانش‌جویان منتقل شود. مواردی که در ارزیابی ارائه‌های پژوهشی مدنظر هستند عبارت‌اند از:

• محتوای ارائه
  تعریف روشن و دقیق مسئله، توضیح کارهای قبلی انجام‌شده، توضیح ایده‌های اصلی در راه‌حل جدید، جمع‌بندی و نتیجه‌گیری
• کیفیت ارائه
  تسلط بر موضوع ارائه‌شده، ترتیب منطقی ارائه، استفاده‌ی صحیح از زمان (اتمام به موقع)
• کیفیت اسلایدها
  استفاده از مثال‌ها و شکل‌های مناسب، مشخص بودن نکات کلیدی در اسلایدها، شلوغ و پر از متن نبودن اسلایدها

پس از ارائه‌ی شفاهی، گزارش کتبی مقاله در قالب یک گزارش پژوهشی توسط دانش‌جو ارائه می‌شود. گزارش پژوهشی شامل سه بخش اصلی زیر است:

• مقدمه و معرفی کارهای پیشین
  بخش اول گزارش شامل تعریف دقیق مسئله و معرفی کارهای قبلی انجام‌شده در این زمینه است. در این بخش شما باید کارهای اخیر انجام‌شده درباره‌ی مسئله را جست‌وجو و به‌طور خلاصه عنوان کنید. مشخصات مقالات عنوان‌شده باید در بخش مراجع ذکر شده و در متن گزارش با شماره مورد ارجاع قرار گیرند.

• ارائه‌ی الگوریتم و تحلیل آن
  در بخش دوم شما باید الگوریتم ارائه‌شده در مقاله را به زبان خود توضیح داده، اثبات درستی و تحلیل ضریب تقریب آن را به زبان ساده و روان بیان کنید. هدف در این بخش باید قابل فهم‌تر کردن الگوریتم یا تحلیل آن باشد. برای این کار شما باید از خلاقیت خود استفاده کنید: نگاه جدید به مسئله، ساده‌سازی علائم به‌کار رفته، استفاده از اشکال، حذف جزئیات غیرضروری، ارائه‌ی مثال‌های جدید، و هر آن‌جه که در فهم بهتر مقاله به خواننده‌ کمک می‌کند. دقت کنید که این کارها بدون خارج شدن از محدوده‌ی ۱۰ صفحه انجام شود.

• نتیجه‌گیری
  در بخش پایانی گزارش، شما باید ایده‌ها و نتایج ارائه‌شده در مقاله را مورد نقد دهید. این نقد می‌تواند از طریق مقایسه با سایر کارهای انجام‌شده، مقایسه با کران پایین مسئله، ارزیابی عملی بودن الگوریتم‌، و غیره صورت پذیرد. همچنین مسائل حل‌نشده‌ و کارهای دیگری را که می‌توان در این زمینه انجام داد بیان کنید. اگر ایده‌ای برای بهتر کردن نتایج ارائه‌شده در مقاله دارید، حتماً در این قسمت ذکر کنید.

گزارش پژوهشی باید مطابق این قالب تک تهیه شده و در نگارش آن نکات نگارشی رعایت شده باشد.

فهرست پروژه‌های پژوهشی درس در این صفحه به‌روز می‌شوند.