Bilgisayar Mühendisliği

CE 390 | Ders Tanıtım Bilgileri

Dersin Adı

Analysis of Algorithms

Kodu	Yarıyıl	Teori (saat/hafta)	Uygulama/Lab (saat/hafta)	Yerel Kredi	AKTS
CE 390	FALL	3	0	3	5

Ön-Koşul(lar)	Array
Dersin Dili	English
Dersin Türü	ELECTIVE_COURSE
Dersin Düzeyi	Lisans
Dersin Veriliş Şekli	Face-to-face, Online
Dersin Öğretim Yöntem ve Teknikleri	Problem solving Lecture / Presentation
Ulusal Meslek Sınıflandırma Kodu	-
Dersin Koordinatörü	Prof. Dr. Turhan Tunalı
Öğretim Eleman(lar)ı	Prof. Dr. Turhan Tunalı
Yardımcı(ları)	-

Dersin Amacı

The objective of this course is to introduce algorithms by looking at the realworld problems motivating them. Students will be taught a range of design and analysis techniques for problems that arise in computing applications. Greedy algorithms, divideandconquer type of algorithms, and dynamic programming will be discussed within the context of different example applications. Approximation algorithms with an emphasis on load balancing and set cover problems will also be covered.

Öğrenme Çıktıları

Bu dersi başarıyla tamamlayabilen öğrenciler;

Ad	Açıklama	PC Alt	* Katkı Düzeyi
Ad	Açıklama	PC Alt	1	2	3	4	5
LO1	will be able to analyze the time and space complexity of algorithms.	1.4				X
LO2	will be able to efficiently solve suitable problems with greedy algorithms.	4				X
LO3	will be able to discuss if a problem could be solved with divide and conquer algorithm and solve suitable problems with divide and conquer algorithm.	4				X
LO4	will be able to discuss if a problem could be solved with a dynamic programming algorithm and solve suitable problems with dynamic programming algorithms.	4				X
LO5	will be able to compare the trade-off between the time complexity and the optimality of the solution to find the most optimal solution and discuss approximation algorithms when the optimal is not feasible.	2				X

Ders Tanımı

Greedy algorithms, divide-and-conquer type of algorithms, dynamic programming and approximation algorithms.

Dersin İlişkili Olduğu Sürdürülebilir Kalkınma Amaçları

Dersin Kategorisi	Temel Ders
	Uzmanlık/Alan Dersleri	X
	Destek Dersleri
	İletişim ve Yönetim Becerileri Dersleri
	Aktarılabilir Beceri Dersleri

HAFTALIK KONULAR VE İLGİLİ ÖN HAZIRLIK ÇALIŞMALARI

Hafta	Konular	Ön Hazırlık	Öğrenme Çıktısı
1	Introduction and motivation. Mathematical foundations, summation, recurrences and growth of functions	Cormen Chapter 2, 3, and 4	LO1
2	Asymptotic notation and Master theorem	Cormen Chapter 4	LO1
3	Binary heaps and analysis of heapsort	Cormen Chapter 6	LO1
4	Sorting theory and more comparison sorting algorithms: Analysis of merge sort and Quicksort.	Cormen Chapter 7	LO3
5	Worst case analysis of Quicksort	Cormen Chapter 7	LO1
6	Sorting in linear time, lower bounds for sorting, counting sort, radix sort, bucket sort	Cormen Chapter 8	LO2
7	Medians and order statistics. Finding median and rank in linear time, selection algorithm.	Cormen Chapter 9	LO1
8	Midterm		-
9	Elementary data structures and runtime analysis of insertion, deletion and update	Cormen Chapter 10	LO1
10	Hash tables and runtime analysis.	Cormen Chapter 11	LO1
11	Binary search trees and Redblack trees	Cormen Chapter 12 and 13	LO3
12	Btrees and Augmenting data structures	Cormen Chapter 18	LO1
13	Amortized analysis	Cormen Chapter 17	LO5
14	Binomial heaps and fibonacci heaps	Cormen Chapter 19 and 20	LO4
15	Semester Review		-
16	Final Exam		-

Ders Kitabı	Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; and Clifford Stein. 2009. Introduction to Algorithms; Third Edition (3rd. ed.). The MIT Press.
Önerilen Okumalar/Materyaller	-

DEĞERLENDİRME ÖLÇÜTLERİ

Yarıyıl Aktiviteleri	Sayı	Katkı Payı %	LO1	LO2	LO3	LO4	LO5
Ödev	1	30	X				X
Ara Sınav	1	30	X	X	X	X
Final Sınavı	1	40	X	X	X	X	X
Toplam	3	100

AKTS / İŞ YÜKÜ TABLOSU

Yarıyıl Aktiviteleri	Sayı	Süre (Saat)	İş Yükü
Katılım	-	-	-
Teorik Ders Saati	16	3	48
Laboratuvar / Uygulama Ders Saati	-	-	-
Sınıf Dışı Ders Çalışması	15	4	60
Arazi Çalışması	-	-	-
Küçük Sınav / Stüdyo Kritiği	-	-	-
Portfolyo	-	-	-
Ödev	4	3	12
Sunum / Jüri Önünde Sunum	-	-	-
Proje	-	-	-
Seminer/Çalıştay	-	-	-
Sözlü Sınav	-	-	-
Ara Sınavlar	1	10	10
Final Sınavı	1	20	20
		Toplam	150

DERSİN ÖĞRENME ÇIKTILARININ PROGRAM YETERLİLİKLERİ İLE İLİŞKİSİ

#	PC Alt	Program Yeterlilikleri / Çıktıları	* Katkı Düzeyi
#	PC Alt	Program Yeterlilikleri / Çıktıları	1	2	3	4	5
1	Engineering Knowledge: Knowledge of mathematics, science, basic engineering, computation, and related engineering discipline-specific topics; the ability to apply this knowledge to solve complex engineering problems.
	1	Mathematics
	2	Science
	3	Basic Engineering
	4	Computation				LO1
	5	Related engineering discipline-specific topics
	6	The ability to apply this knowledge to solve complex engineering problems
2	Problem Analysis: Ability to identify, formulate and analyze complex engineering problems using basic knowledge of science, mathematics and engineering, and considering the UN Sustainable Development Goals relevant to the problem being addressed.					LO5
3	Engineering Design: The ability to devise creative solutions to complex engineering problems; the ability to design complex systems, processes, devices or products to meet current and future needs, considering realistic constraints and conditions.
	1	Ability to design creative solutions to complex engineering problems
	2	Ability to design complex systems, processes, devices or products to meet current and future needs, considering realistic constraints and conditions
4	Use of Techniques and Tools: Ability to select and use appropriate techniques, resources, and modern engineering and computing tools, including estimation and modeling, for the analysis and solution of complex engineering problems, while recognizing their limitations.					LO2 LO3 LO4
5	Research and Investigation: Ability to use research methods to investigate complex engineering problems, including literature research, designing and conducting experiments, collecting data, and analyzing and interpreting results.
	1	Literature research for the study of complex engineering problems
	2	Designing experiments
	3	Ability to use research methods, including conducting experiments, collecting data. analyzing and interpreting results
6	Global Impact of Engineering Practices: Knowledge of the impacts of engineering practices on society, health and safety, economy, sustainability, and the environment, within the context of the UN Sustainable Development Goals; awareness of the legal implications of engineering solutions.
	1	Knowledge of the impacts of engineering practices on society, health and safety, economy, sustainability, and the environment, within the context of the UN Sustainable Development Goals
	2	Awareness of the legal implications of engineering solutions
7	Ethical Behavior: Acting in accordance with the principles of the engineering profession, knowledge about ethical responsibility; awareness of being impartial, without discrimination, and being inclusive of diversity.
	1	Acting in accordance with the principles of the engineering profession, knowledge about ethical responsibility ethical responsibility
	2	Awareness of being impartial and inclusive of diversity, without discriminating on any subject
8	Individual and Teamwork: Ability to work effectively, individually and as a team member or leader on interdisciplinary and multidisciplinary teams (face-to-face, remote or hybrid).
	1	Ability to work individually and within the discipline
	2	Ability to work effectively as a team member or leader in multidisciplinary teams (face-to-face, remote or hybrid)
9	Verbal and Written Communication: Taking into account the various differences of the target audience (such as education, language, profession) on technical issues.
	1	Ability to communicate verbally
	2	Ability to communicate effectively in writing
10	Project Management: Knowledge of business practices such as project management and economic feasibility analysis; awareness of entrepreneurship and innovation.
	1	Knowledge of business practices such as project management and economic feasibility analysis
	2	Awareness of entrepreneurship and innovation
11	Lifelong Learning: Lifelong learning skills that include being able to learn independently and continuously, adapting to new and developing technologies, and thinking questioningly about technological changes.