course pages

Yazilim Mühendisligi
http://eng.harran.edu.tr/~nbesli/

BIL 582
http://sadik.etu.edu.tr/

Dosyalar / Yazilim Mühendisligi
http://www.ce.yildiz.edu.tr/personal/yunus/file/295/Yaz%C4%B1l%C4%B1m+M%C3%BChendisli%C4%9Fi


BM 314 Yazilim Mühendisligi
http://ceng.gazi.edu.tr/~hkaracan/bm314.html


SE102 Foundations of Software Engineering II
https://www.cs.drexel.edu/~spiros/teaching/SE102/index.html


Software Project Management
http://ii.metu.edu.tr/~is529/index.html#dwn

GRE Computer Science Questions

GRE Computer Science Question 01


40. Consider the following pseudocode program.
int i
main ()
{
i = 3
S ()
R ()
}
void S ()
{
print i // prints the value of i on the current line of output
print " " // prints a blank space on the current line of output
}
void R ()
{
int i
i = 2
S ()
}
What is the output of the program if the pseudocode uses either static (lexical) scoping or dynamic scoping?
Static Scoping Dynamic Scoping
(A) 3 2 3 2
(B) 3 3 2 2
(C) 3 3 2 3
(D) 3 3 3 2
(E) 3 3 3 3

http://www.youtube.com/watch?v=SwyaLVsJCsI

Selection Sort

• Algorithms Lesson 8: Selection Sort

http://www.youtube.com/watch?v=6nDMgr0-Yyo&feature=relmfu

• Selection Sort

In computer science, a selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm works as follows:
Find the minimum value in the list
Swap it with the value in the first position
Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)


/* a[0] to a[n-1] is the array to sort */
int i,j;
int iMin;

/* advance the position through the entire array */
/*   (could do j < n-1 because single element is also min element) */
for (j = 0; j < n-1; j++) {
    /* find the min element in the unsorted a[j .. n-1] */

    /* assume the min is the first element */
    iMin = j;
    /* test against elements after j to find the smallest */
    for ( i = j+1; i < n; i++) {
        /* if this element is less, then it is the new minimum */
        if (a[i] < a[iMin]) {
            /* found new minimum; remember its index */
            iMin = i;
        }
    }

    /* iMin is the index of the minimum element. Swap it with the current position */
    if ( iMin != j ) {
        swap(a[j], a[iMin]);
    }
}


http://en.wikipedia.org/wiki/Selection_sort

• Selection Sort

https://www.youtube.com/watch?v=f8hXR_Hvybo

• Algorithms #3 - Selection Sort

https://www.youtube.com/watch?v=TW3_7cD9L1A

Insertion Sort

• Algorithms Lesson 2: Insertion Sort

worst case: n^2

http://www.youtube.com/watch?v=c4BRHC7kTaQ&feature=fvwrel

• Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort
More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort

for i ? 1 to i ? length(A)-1
   {
     // A[ i ] is added in the sorted sequence A[0, .. i-1]
     // save A[i] to make a hole at index iHole
     item ? A[i]
     iHole ? i
     // keep moving the hole to next smaller index until A[iHole - 1] is <= item
     while iHole > 0 and A[iHole - 1] > item
       {
         // move hole to next smaller index
         A[iHole] ? A[iHole - 1]
         iHole ? iHole - 1
       }
     // put item in the hole
     A[iHole] ? item
   }
 
http://en.wikipedia.org/wiki/Insertion_sort

• The ideas of insertion

The main operation of the algorithm is insertion. The task is to insert a value into the sorted part of the array.

Java implementation

void insertionSort(int[] arr) {
      int i, j, newValue;
      for (i = 1; i < arr.length; i++) {
            newValue = arr[i];
            j = i;
            while (j > 0 && arr[j - 1] > newValue) {
                  arr[j] = arr[j - 1];
                  j--;
            }
            arr[j] = newValue;
      }
}


http://www.algolist.net/Algorithms/Sorting/Insertion_sort

Bubblesort

• Algorithms Lesson 1: Bubblesort

http://www.youtube.com/watch?v=P00xJgWzz2c&feature=relmfu

• Bubble sort - algorithm and analysis

http://www.youtube.com/watch?v=PdmyYqO_59s&feature=related

• Bubble sort

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order

Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted

procedure bubbleSort( A : list of sortable items )
   repeat    
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure


http://en.wikipedia.org/wiki/Bubble_sort

• Bubble Sort

Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes.

Java

public void bubbleSort(int[] arr) {
      boolean swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < arr.length - j; i++) {                                      
                  if (arr[i] > arr[i + 1]) {                        
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }              
      }
}

http://www.algolist.net/Algorithms/Sorting/Bubble_sort

Heapsort

• Algorithms Lesson 9: Heaps

http://www.youtube.com/watch?v=v1YUApMYXO4&feature=fvwrel

• Algorithms Lesson 10: Heapsort

http://www.youtube.com/watch?v=6NB0GHY11Iw

• Heapsort

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family
has the advantage of a more favorable worst-case O(n log n) runtime


Heapsort is a two step algorithm.
The first step is to build a heap out of the data.
The second step begins with removing the largest element from the heap

http://en.wikipedia.org/wiki/Heapsort

• Heap Sort Algorithm

The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of heap sort is O(n log n) and like insertion sort, heap sort sorts in-place.
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Quicksort

• Algorithms Lesson 4: Quicksort

http://www.youtube.com/watch?v=y_G9BkAm6B8&feature=relmfu
partition step

• Visualization of Quick Sort

http://www.youtube.com/watch?v=vxENKlcs2Tw

• Quick Sort

http://www.youtube.com/watch?v=J7FTIe5y3Mw&feature=related

• QuickSort

http://www.youtube.com/watch?v=Fju_NstEy3M

• Lec-11 Mergesort And Quicksort

http://www.youtube.com/watch?v=KrjWloKRE2U&feature=related

• Quicksort

Quicksort is a sorting algorithm
In the worst case, it makes O(n2) comparisons
Quicksort is often faster in practice than other O(n log n) algorithms

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:
Pick an element, called a pivot, from the list.

Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

function quicksort('array')
      if length('array') = 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
          if 'x' = 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls
     
http://en.wikipedia.org/wiki/Quicksort

• Quicksort

Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice

Java

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
   
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
   
      return i;
}

void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

http://www.algolist.net/Algorithms/Sorting/Quicksort

• Quick Sort is a sorting algorithm which uses divide and conquer technique.

In quick sort we choose an element as a pivot and we create a partition of array around that pivot. by repeating this technique for each partition we get our array sorted

depending on the position of the pivot we can apply quick sort in different ways

taking first or last element as pivot

taking median element as pivot

Time Complexity Analysis of Quick Sort

The average time complexity of quick sort is O(N log(N)).

Best case Time Complexity of Quick Sort

O(Nlog(N))

the best case of quick sort is when we will select pivot as a mean element.

Worst Case Time Complexity of Quick Sort

O(N^2)

This will happen when we will when our array will be sorted and we select smallest or largest indexed element as pivot

Average Case Time Complexity of Quick Sort

O(Nlog(N))

Space Complexity

O(N)

https://iq.opengenus.org/time-and-space-complexity-of-quick-sort/