Kocaeli University Computer Engineering Department – Spring-2019:
Büyük Veri, Paralel İşleme ve Akademisyenlik [Link]
1. Algoritma Çözümleme (BLM 320)
Duyurular:
FİNAL sınavı’nda kullanılmak üzere hatırlatma kağıdı hazırlayıp getirebilirsiniz. Hatırlatma kağıdı A4 kağıdına HER İKİ yüzüne kendi el yazınızla hazırlanacaktır. Sınav bitiminde üzerinde isim ve no yazılmış şekilde, cevap kağıdıyla birlikte katlamadan teslim edilecektir. Hatırlatma kağıdı olmayanlar yoklama kağıdına belirtmelidir. (1) Hatırlatma kağıdını sınav sonunda teslim etmeyenler ve (2) hatırlatma kağıdını kendi el yazısıyla yazmayanlar kopye muamelesi görecektir. Bu konuda gerekli hassasiyeti göstermeniz dileğiyle sınavda başarılar.
VİZE sınavı’nda kullanılmak üzere hatırlatma kağıdı hazırlayıp getirebilirsiniz. Hatırlatma kağıdı A4 kağıdına TEK yüzüne kendi el yazınızla hazırlanacaktır. Sınav bitiminde üzerinde isim ve no yazılmış şekilde, cevap kağıdıyla birlikte katlamadan teslim edilecektir. Hatırlatma kağıdı olmayanlar yoklama kağıdına belirtmelidir. (1) Hatırlatma kağıdını sınav sonunda teslim etmeyenler ve (2) hatırlatma kağıdını kendi el yazısıyla yazmayanlar kopye muamelesi görecektir. Bu konuda gerekli hassasiyeti göstermeniz dileğiyle sınavda başarılar.
Lectures:
- Introduction to algorithms. What is more important than performance? What do you expect from a program? Why study algorithms? Decision Problems vs Optimization Problems. (Class notes)
- Introduction to algorithm analysis by simple sorting algorithms – Insertion Sort and Selection Sort. (Link-1)
- Merge Sort and its algorithmic analysis – running time in worst and best cases (As an application of Divide and Conquer Approach) (Link-1)
- Recursive function definitions for a given problem. For example for merge sort T(n)=2T(n/2)+n. Creating and solving recursive equations for divide and conquer problems. Solving asymptotic time complexity with recursion tree. (Class notes)
- Asymptotic Complexities (time analyses) and their meaning. Big-O, Big-omega, Little-o Little-omega, Theta. (Link-5)
- Time analysis on given pseudo code (Class notes)
– Exact time (sec, minutes etc.)
– Asymptotic time (time and space complexities in terms of number of inputs) - Asymptotic analysis of a pseudocode for an algorithm. Creating and solving summation formulas to calculate the number of steps in a given code. (Class notes)
- Studying some well-known divide and conquer problems (Link-1)
– Examples: Binary Search, Powering a number, Fibonacci Numbers, Matrix Multiplication, Strassen’s approach for matrix multiplication.
– Creating their recursive function definitions
– Solving them with recursive tree approach and master theorem formula - An application of divide and conquer approach on a sorting algorithm, Quick Sort. It’s best, worst and average case analyses. (Note: Randomized QuickSort is not covered) (Link-1)
- Decision Tree Modeling of comparison based sortings. Time analysis. Why can’t we sort an array with n elements less than O(n) time? (Link-1)
- Linear time sorting – O(n) sorting algorithms (Link-1)
– Counting Sort and Radix Sort
– Analysis of Counting sort O(n+k) – what is k here? what is its importance? Analysis of Radix Sort. – What is its limitation to be able to run in O(n) time? - Binary Trees and their properties. (Link-4)
– Insert, delete and search on BST
– Tree traversals – breadth first and depth first (preorder, postorder and inorder)
– Balanced Binary Search Trees
– AVL Trees - Heaps and Heap Sorts (Link-3) (Link-2 : Lectures 4)
-Heaps are implementation methods of priority queues
-Max heap and min heap properties
-Heap Operations: build_max_heap, max_heapify, insert, extract_max, heapsort - Getting prepared for the midterm exam
- Midterm Exam (18/04/2019 Thursday 15:00)
- Hashing (Link-1 : Lecture-7)
-Direct Access Table (DAT)
-Resolving collisions by chaining and by open addressing
-Load factor in hash tables
-Avg number of steps in hashing with chaining – successful and unsuccessful cases
-Probing strategies in open addressing: 1. linear probing 2. double hashing
-Asymptotic analyses - Graphs (Link-1 : Lectures 16) (Link-2 : Lectures 13-14-15-16-17)
-Graph types
-Graph representations: Adjacency matrix and adjacency list
-Minimum Spanning Tree – Prim’s Algorithm
-Shortest path definition: Single source shortest path and all-pairs shortest path
-Dijkstra’s shortest path algorithm (a sample of Greedy algorithm)
-DFS and BFS graph traversal and search algorithms
-How do you find single source shortest path by means of BFS? Think about weighted and unweighted cases - Design Paradigms in Algorithm and their comparisons
-Divide and Conquer (QuickSort, MergeSort)
-Greedy Algorithms
-Dynamic Programming (examples are given below)
-Bruteforce vs straightforward approaches
-Heuristic
-Straightforward
-Bottom-up and Top-down - Greedy examples: event scheduling, MST (Prim’s alg), Dijkstra’s single source shortest path (Link-1 : Lectures 15-16)
- Dynamic Programming examples
– Fibonacci bottom up approach
– LCS (Longest Common Subsequence): -Sub-sequence, sub-array and sub-string.
– 0/1 Knapsack problem
– Calculating a sub-array with the maximum sum in a given array. (Contiguous array with max sum)
– Maximum size square sub-matrix consisting of all 1s
– Maximum size rectangular sub-matrix consisting of all 1s - Getting prepared for the midterm exam
- Final Exam 13/06/2019 Thursday at 15:00
Useful References:
- Link-1: MIT – Introduction to Algorithms Lectures (2005)
- Link-2: MIT – Introduction to Algorithms Lectures (2011)
- Link-3: Heap, Heap Sort and Priority Queue (pdf)
- Link-4: İkili arama ağacı, ağaç gezinme, dengeli ikili arama ağacı oluşturma
- Link-5: Asymptotic Analysis and summation series
- Textbook: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009 -3rd edition is also available electronically.
- Kitabın türkçeye çevrilmiş hali de mevcuttur. “Algoritmalara Giriş” başlığı altında çeşitli yayınevlerinden temin edilebilir.
2. Otomata (BLM 436)
Duyurular:
- Dersin slidelarına buradan ulaşabilirsiniz.
- Sınavlar klasik olacaktır. Soru sayısı genellikle 2-4 aralığında olur.
Lectures:
- Course Overview – Finite Automata (FA) – Deterministic Finite Automata (DFA)
- Birinci Bölüm
- Non deterministic Automata – Lambda Geçişi (Lambda Transition) – Lambda
removal (Lambda geçişsiz eşdeğer çizeneğin bulunması) - Deterministik ve deterministik olmayan sonlu özdevinirlerin denkliği – Two-way
Deterministic Finite Automata (2DFA) - Çıkış üreten özdevinirler – Moore and Mealey Makinaları – Moore and Mealey
Makinalarının eşdeğerliği – Mealy makinasından Moore makinesine ve Moore
makinesinden Mealy makinasına çevirme teknikleri - Sonlu özdevinirlerin indirgenmesi (Reduction methods – Minimizing Finite
Automata): (1) Mealy makinalarının indirgenmesi, (2) Moore makinalarının
indirgenmesi, (3) DFA makinalarının indirgenmesi – Ardıl, Öncel, Denk ve
Ayırdedilebilir durum tanımları - Bölüm sonu sorularının çözülmesi
- İkinci Bölüm
- Düzgün Kümeler (Regular Sets)
- Düzgün Deyimler (Regular Languages)
- Düzgün deyimlere karşı gelen sonlu özdevinirlerin bulunması
- Sonlu Özdevinirlerin tanıdığı kümelerin düzgün deyim olarak bulunması
- Arasınav (Tarih Açıklanacak)
- 3.Bölüm (3.4 dahil değil)
- Dil bilgisi ve diller: tür-0, tür-1, tür-2 ve tür-3 dilbilgileri ve dilleri
- Düzgün dilbilgisinin türettiği dili tanıyan FA bulunması
- FA nın tanıdığı dili türeten düzgün dilbilgisinin bulunması
- 4. Bölüm (4.4 dahil değil)
- Bağlamdan bağımsız dilbilgisi, dilbilgisinin yalınlaştırılması, birim türetme kuralları, yarasız değişken, simge ve kurallar
- 5. Bölüm, Yığıtlı Ödevinirler (5.2 dahil değil)
- 6. Bölüm, Türing makinaları – dil tanıyıcı ve hesaplayıcı modeller (6.3 ve 6.4 dahil değil)
- Final Sınavı (Tarih Açıklanacak)
Useful References :
- Textbook: Prof. Dr. Ünal Yarımağan, Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller, 348 sayfa, 2nci basım, 2010.