Lecture Notes (Spring)

Kocaeli University Computer Engineering Department – Spring-2018:

 


1. Algoritma Çözümleme (BLM 320) 

Ders ile ilgili detaylı bilgileri Course Syllabus  linkinden bulabilirsiniz.

Duyurular:

*** FİNAL sınavı açıklama: 1.öğretim:(1) Geçme notu 45 e çekildi. (2) Yoklamalar final sınavına direkt eklendi. (3) BA+AA sayısı 13

*** FİNAL sınavı açıklama: 2.öğretim: (1) AA notu 85, geçme notu 45 yapıldı. (2) Yoklamalar final sınavına direkt eklendi. (3) BA+AA sayısı 10

FİNAL sınavı dönem boyunca işlediğimiz tüm konuları kapsayacaktır.

FİNAL sınavı’nda kullanılmak üzere hatırlatma kağıdı hazırlayıp getirebilirsiniz. Hatırlatma kağıdı A4 kağıdının HER İKİ yüzüne kendi el yazınızla hazırlanacaktır. Sınav bitiminde üzerinde isin 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 isin 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:

  1. 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)
  2. Introduction to algorithm analysis by simple sorting algorithms – Insertion Sort and Selection Sort. (Link-1)
  3. Merge Sort and its algorithmic analysis – running time in worst and best cases (As an application of Divide and Conquer Approach) (Link-1)
  4. 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)
  5. Asymptotic Complexities (time analyses) and their meaning. Big-O, Big-omega, Little-o Little-omega, Theta. (Link-5)
  6. 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)
  7. 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)
  8. 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
  9. 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)
  10. 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)
  11. 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?
  12. 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
  13. Getting prepared for the midterm exam
  14. Midterm Exam (27/03/2018 Tuesday 16:00)
  15. 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
  16. 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
  17. 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
  18. 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
  19. Greedy examples: event scheduling, MST (Prim’s alg), Dijkstra’s single source shortest path (Link-1 : Lectures 15-16)
  20. 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
  21. Final Exam (29/05/2018 Tuesday 16:00) (Amfi-3 1.öğr) (303 2.öğr)

 

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)  

Ders ile ilgili detaylı bilgileri Course Syllabus linkinden bulabilirsiniz.

 

Duyurular:

 

Lectures:

  1. Course Overview – Finite Automata (FA) – Deterministic Finite Automata (DFA)
  2. Birinci Bölüm
  3. Non deterministic Automata – Lambda Geçişi (Lambda Transition) – Lambda
    removal (Lambda geçişsiz eşdeğer çizeneğin bulunması)
  4. Deterministik ve deterministik olmayan sonlu özdevinirlerin denkliği –  Two-way
    Deterministic Finite Automata (2DFA)
  5. Çı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
  6. 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ı
  7. Bölüm sonu sorularının çözülmesi
  8. İkinci Bölüm
  9. Düzgün Kümeler (Regular Sets)
  10. Düzgün Deyimler (Regular Languages)
  11. Düzgün deyimlere karşı gelen sonlu özdevinirlerin bulunması
  12. Sonlu Özdevinirlerin tanıdığı kümelerin düzgün deyim olarak bulunması
  13. Arasınav (29/03/2018 Perşembe 10:30 (I) Amfi3 – 17:00 (II) 301-303)
  14. 3.Bölüm (3.4 dahil değil)
  15. Dil bilgisi ve diller: tür-0, tür-1, tür-2 ve tür-3 dilbilgileri ve dilleri
  16. Düzgün dilbilgisinin türettiği dili tanıyan FA bulunması
  17. FA nın tanıdığı dili türeten düzgün dilbilgisinin bulunması
  18. 4. Bölüm (4.4 dahil değil)
  19. Bağlamdan bağımsız dilbilgisi, dilbilgisinin yalınlaştırılması, birim türetme kuralları, yarasız değişken, simge ve kurallar
  20. 5. Bölüm, Yığıtlı Ödevinirler (5.2 dahil değil)
  21. 6. Bölüm, Türing makinaları – dil tanıyıcı ve hesaplayıcı modeller (6.3 ve 6.4 dahil değil)
  22. Final Sınavı

Useful References :

  • Textbook:  Prof. Dr. Ünal Yarımağan, Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller, 348 sayfa, 2nci basım, 2010.

 

 


3. Algorithms Design and Analysis BLM 512) (Graduate Level Course)

Ders ile ilgili detaylı bilgileri Course Syllabus linkinden bulabilirsiniz.

Assignments

  • Proje-1 : Graf Benzerlikleri ve Alt-graf Eşleştirme Algoritmaları Üzerine Bir Çalışma (A study on Algorithms for Graph Similarity and Sub-graph Matching) Due date: 17-04-2018
  • Proje-2 : Gezinge Verilerinin Benzerlikleri Üzerine Bir Çalışma (A Study on Algorithms for Trajectory Similarities)  Due date: 29-05-2018

 

Duyurular:

FİNAL sınavı dönem boyunca işlediğimiz tüm konuları kapsayacaktır.

FİNAL sınavı’nda kullanılmak üzere hatırlatma kağıdı hazırlayıp getirebilirsiniz. Hatırlatma kağıdı A4 kağıdının HER İKİ yüzüne kendi el yazınızla hazırlanacaktır. Sınav bitiminde üzerinde isin 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ı 3 Nisan Salı günü ders saatinde yapılacaktır. Lisans sınavları da olduğu için o hafta sınav olmayan boş bir sınıf bulmamız gerekecek.

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 isin 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:

  1. 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)
  2. Introduction to algorithm analysis by simple sorting algorithms – Insertion Sort and Selection Sort. (Link-1)
  3. Merge Sort and its algorithmic analysis – running time in worst and best cases (As an application of Divide and Conquer Approach) (Link-1)
  4. 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)
  5. Asymptotic Complexities (time analyses) and their meaning. Big-O, Big-omega, Little-o Little-omega, Theta. (Link-5)
  6. 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)
  7. 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)
  8. 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
  9. 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)
  10. 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)
  11. 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?
  12. 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
  13. 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
  14. Midterm Exam (03/04/2018 Salı,  saat: 14:00)
  15. 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
  16. 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
  17. 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
  18. Greedy examples: event scheduling, MST (Prim’s alg), Dijkstra’s single source shortest path (Link-1 : Lectures 15-16)
  19. 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
  20. Final Exam (05/06/2018 Tuesday 14: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.

 

 

LEAVE A COMMENT

This site uses Akismet to reduce spam. Learn how your comment data is processed.

theme by teslathemes