Dry Running Algorithm

Latihan 1

Misalkan saja ada sebuah vektor \(x=[3,1,4,1,5,9,2,6,5]\), buat program untuk mengurutkan vektor tersebut dari kecil ke besar, kemudian bandingkan hasilnya dengan fungsi sort!

Jawaban:

Untuk melakukan pengurutan, iterasi yang akan digunakan terdiri dari dua tingkat,

1. iterasi untuk memastikan semua elemen diperiksa

2. Iterasi untuk mengakses elemen-elemen vektor yang digunakan untuk penukaran antar elemen

Pada iterasi tingkat kedua nilai-nilai yang besar akan semakin terdorong ke-belakang sehingga elemen-elemen belakang vektor tidak perlu diperiksa lagi. Misal pada saat iterasi tingkat pertama sama dengan 3 maka elemen yang akan dibandingkan hanya dari element 1 sampai 7 saja (ingat ada j+1). Semakin meningkat iterasi tingkat 1 maka banyaknya iterasi tingkat 2 semakin mengecil (pada kasus ini diakomodir dengan n_x-i).

x <- c(3,1,4,1,5,9,2,6,5)

# mendefinisikan objek baru yang akan digunakan untuk menampilkan hasil sortir
x_sort <- x

#jumlah amatan 
n_x <- length(x)

#iterasi tingkat 1
for(i in 1:(n_x-1)){
  #iterasi tingkat 2
  for(j in 1:(n_x-i)) {
    
    # Pemeriksaan kondisi apakah elemen ke-j+1 lebih kecil dari elemen ke-j
    if(x_sort[j+1] < x_sort[j]) {
      # jika terpenuhi
      # buat tempat sementara untuk menyimpan elemen ke-j yang akan ditukar
      tmp <- x_sort[j]
      # tukar nilai elemen ke-j dengan nilai yang ada pada elemen ke j+1
      x_sort[j] <- x_sort[j+ 1]
      # tukar nilai elemen j+1 dengan nilai yang ada dalam objek temp
      x_sort[j+1] <- tmp
    }
  }
}

x_sort

## [1] 1 1 2 3 4 5 5 6 9

sort(x)

## [1] 1 1 2 3 4 5 5 6 9

Latihan 2

Berdasarkan jawaban nomor 1, Buatlah fungsi yang bernama fungsi_urutan dengan yang memiliki input x dan outputnya merupakan vector yang sudah terurut!

fungsi_urutan <- function(x){
  n_x <- length(x)
  for(i in 1:(n_x-1)){
    for(j in 1:(n_x-i)) {
      if(x[j+1] < x[j]) {
        tmp <- x[j]
        x[j] <- x[j+ 1]
        x[j+1] <- tmp
      }
    }
  }
  
  return(x)
}

#mencoba menerapkan fungsi urutan
fungsi_urutan(x)

## [1] 1 1 2 3 4 5 5 6 9

Latihan 3

Bandingkan kecepatan running user-defined-function pada nomor 2 dan fungsi sort dengan menggunakan package microbenchmark.

microbenchmark::microbenchmark(sort(x),fungsi_urutan(x))

## Unit: microseconds
##              expr  min    lq   mean median   uq   max neval cld
##           sort(x) 38.5 39.60 42.956   40.4 41.5 155.8   100  a 
##  fungsi_urutan(x)  6.0  6.45  7.450    7.5  7.9  16.0   100   b

Latihan 4

Susunlah sintaks R untuk penjumlahan deret berikut!

\(z = 2-\frac{6}{5}+\frac{8}{10}-\frac{10}{17}+\frac{12}{26}-...\)

hint: Cari terlebih dahulu formula/rumus dari deret tersebut

Jawaban:

Rumus dari deret tersebut adalah

\(z= \Sigma_{n=1}^{\infty} (-1)^{n+1} \frac{2n+2}{n^{2}+1}\)

1. Menuliskan rumus fungsi dalam bentuk function

fz <- function(n){
  (-1)^(n+1)*((2*n+2)/((n^2)+1))
}

2. Mendefinisikan kriteria stopping

stopping_criteria <- function(y_current,y_before){
  abs(y_current-y_before)
}

3. Mendefinisikan nilai-nilai awal

#nilai awal kriteria stopping
error <- 10
#nilai awal deret
z0 <- 0
# nilai awal iterasi
n <- 1

3. Menuliskan iterasi untuk mencari jumlah deret

while (error>0.00001) {
  z <- z0 + fz(n)
  error <- stopping_criteria(z, z0)
  z0 <- z
  n <- n+1
}
# final result
cat("Nilai akhir adalah: ",  z)

## Nilai akhir adalah:  1.267197

# criteria stopping
cat("Kriteria penghentian iterasi adalah: ",  error)

## Kriteria penghentian iterasi adalah:  1e-05

Latihan 5

\(z = \frac{2}{5}+\frac{3}{40}+\frac{6}{135}+\frac{11}{320}+\frac{18}{625}+\frac{27}{1080}+...\)

hint: Cari terlebih dahulu formula/rumus dari deret tersebut

Jawaban:

Rumus dari deret tersebut adalah

\(z= \Sigma_{n=1}^{\infty} \frac{n^2 +2n + 3}{5n^{3}}\)

1. Menuliskan rumus fungsi dalam bentuk function

fz <- function(n){
  ((n^2) - 2*n + 3) / (5*n^3)
}

2. Mendefinisikan kriteria stopping

stopping_criteria <- function(y_current,y_before){
  abs(y_current-y_before)
}

3. Mendefinisikan nilai-nilai awal

#nilai awal kriteria stopping
error <- 10
#nilai awal deret
z0 <- 0
# nilai awal iterasi
n <- 1

3. Menuliskan iterasi untuk mencari jumlah deret

while (error>0.00001) {
  z <- z0 + fz(n)
  error <- stopping_criteria(z,z0)
  z0 <- z
  n <- n+1
}
# final result
cat("Nilai akhir adalah: ", z)

## Nilai akhir adalah:  2.159406

# criteria stopping
cat("Kriteria penghentian iterasi adalah: ",  error)

## Kriteria penghentian iterasi adalah:  1e-05