Cevaplı Algoritmalar ve karmaşıklık çalışma kâğıdı

Bir algoritmanın en kötü durum çalışma süresi neyi tanımlar?

1. An boyutundaki tüm girdiler üzerinden aldığı en uzun süreyi
2. Bn boyutundaki rastgele bir girdide beklenen süreyi
3. CEn küçük girdide aldığı süreyi
4. DYavaş bir bilgisayarda aldığı süreyi

Bir dizide indeksle bir elemana erişmenin karmaşıklığı nedir?

1. AO(n)
2. BO(log n)
3. CO(1)
4. DO(n²)

Bir problem genellikle ne zaman "çözülebilir" (tractable) olarak adlandırılır?

1. ASabit zamanda çözülebiliyorsa
2. BHiç çözümü yoksa
3. CPolinom zamanda çözülebiliyorsa
4. DYalnızca her olasılığı deneyerek çözülebiliyorsa

Dinamik programlama birleştirmeli sıralama için neden gerçek bir hızlanma sağlamaz?

1. AAlt problemleri çakışmaz, bu yüzden yeniden kullanılacak bir şey yoktur
2. BDinamik programlama yalnızca graf problemlerinde çalışır, dizilerde çalışmaz
3. CBirleştirmeli sıralamanın özyinelemeli bir yapısı yoktur
4. DBirleştirmeli sıralama zaten O(n)'dir

Etkinlik seçimi probleminde hangi açgözlü kural her zaman çakışmayan en fazla sayıda etkinliği verir?

1. AEn erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
2. BÖnce en az çakışması olan etkinliği seç, sonra uyumlu olanlarla tekrarla
3. CEn erken başlayan etkinliği seç
4. DÖnce en kısa etkinliği seç

Şunun zaman karmaşıklığı nedir: for i = 1 to n: for j = 1 to i: O(1) iş yap?

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(n³)

Hangi teknik, hızlı sıralama için her girdide beklenen O(n log n) çalışma süresini sağlar?

1. APivotu düzgün dağılımla rastgele seçmek
2. BHızlı sıralamayı çalıştırmadan önce girdiyi sıralamak
3. CÖzyinelemeyi yalnızca sol tarafta kullanmak
4. DHer zaman ilk elemanı seçmek

NP sınıfının hangi tanımı doğrudur?

1. AEvet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
2. BPolinom zamanda çözülemeyen problemler
3. CHiçbir algoritmanın çözemeyeceği problemler
4. DPolinom olmayan problemler