×
Log in to StudySoup
Get Full Access to Lehigh - CSE 340 - Class Notes - Week 1
Join StudySoup for FREE
Get Full Access to Lehigh - CSE 340 - Class Notes - Week 1

Already have an account? Login here
×
Reset your password

What are algorithms?

What are algorithms?

Description

School: Lehigh University
Department: Computer Science and Engineering
Course: Design and Analysis of Algorithms
Professor: Professor korth
Term: Fall 2016
Tags: InsertionSort, Time_Complexity, and Correctness_Proof
Cost: 25
Name: CSE 340, Week 1
Description: Lecture Note - 8/30/2016 Contents include: insertionSort algorithm, proofs of correctness (Init., Main., Term.), and time complexity terminologies.
Uploaded: 09/24/2016
2 Pages 208 Views 1 Unlocks
Reviews


.lst-kix_uisk01xwt0ie-1 > li:before{content:"○ "}.lst-kix_uisk01xwt0ie-2 > li:before{content:"■ "}.lst-kix_uisk01xwt0ie-0 > li:before{content:"● "}.lst-kix_uisk01xwt0ie-4 > li:before{content:"○ "}.lst-kix_uisk01xwt0ie-3 > li:before{content:"● "}ul.lst-kix_uisk01xwt0ie-4{list-style-type:none}ul.lst-kix_uisk01xwt0ie-3{list-style-type:none}ul.lst-kix_uisk01xwt0ie-2{list-style-type:none}ul.lst-kix_uisk01xwt0ie-1{list-style-type:none}ul.lst-kix_uisk01xwt0ie-0{list-style-type:none}.lst-kix_uisk01xwt0ie-8 > li:before{content:"■ "}.lst-kix_uisk01xwt0ie-5 > li:before{content:"■ "}.lst-kix_uisk01xwt0ie-6 > li:before{content:"● "}ul.lst-kix_uisk01xwt0ie-8{list-style-type:none}.lst-kix_uisk01xwt0ie-7 > li:before{content:"○ "}ul.lst-kix_uisk01xwt0ie-7{list-style-type:none}ul.lst-kix_uisk01xwt0ie-6{list-style-type:none}ul.lst-kix_uisk01xwt0ie-5{list-style-type:none}

CSE 340 Lecture 1We also discuss several other topics like What is the conversion of light energy to electrical to chemical energy?

Algorithms

  • Formal connectedness
  • Scalability (run times of f(n))

Input: sequence of n numbers <a1, a2, ...a3>If you want to learn more check out What is a gibbs free energy?

Output: a permutations of <a1, a2, ...an>We also discuss several other topics like What are the four different eras of marketing?

        <a1’, a2’, ...an’> so that a1’ <a2’ <a3’

Don't forget about the age old question of In what part of the old testament did Jesus had a reluctance to reveal his identity?

Insertion sort (A)                                cost                number of times

For j = 2 to A. length                                C1                nDon't forget about the age old question of What do you mean by a covalent bond?

K = a[j]                                        C2                n - 1Don't forget about the age old question of the ethics of belief

I = j - 1                                                C4                n - 1

While i > 0 and A[j] > K                        C5                j = 2 tj

A[i+1] = A[i]                                        C6                j = 2 (tj - 1)

I --                                                                j = 2

A[i + i7 = k                                        C8                n -1

T(n) = C1n+C2(n - 1) + C (n+)+ …+ CBcn -1

Best case: C1n1+(2+CB)(n-1)+C5

Worst case: j = 2 =

Proof:

Initialisation: true before 1rst iteration

Maintenance: true before an iteration then true after. That

Termination: keep terminates when it does show that the invariant show correctness

A[1...j-1] consists of elements originally in A[1...j-1]

But on sorted order

Initialization: j = 2

Maintenance: invariant holds from j = n → holds for j = n + 1

A[1, ...n - 1] is sorted

The while shifts A such that

A[i...x - 1] holds values < k

A[x + 1...n] holds value > k

And k is placed in A[x]

Termination

J = A. length + 1 so A[i...A. length] is sorted and a permutation of the original

0(f(n))

O(f(n)) upper bound worst case

(f(n)) lower bound at least as fast

Page Expired
5off
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here