Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Blatt 02

    Uploaded by

    aueouaeou
    The document provides an exercise sheet for a lecture on advanced programming and algorithms. It includes 4 problems: 1) Analyzing the time complexity of selection sort, 2) Refactoring a Python implementation of selection sort for readability and reusability, 3) Analyzing the space complexity of selection sort, and 4) Proving correctness of an algorithm to find the maximum element in a sequence using a loop invariant.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Blatt 02

    Uploaded by

    aueouaeou
    15 views2 pages
    The document provides an exercise sheet for a lecture on advanced programming and algorithms. It includes 4 problems: 1) Analyzing the time complexity of selection sort, 2) Refactoring a Python implementation of selection sort for readability and reusability, 3) Analyzing the space complexity of selection sort, and 4) Proving correctness of an algorithm to find the maximum element in a sequence using a loop invariant.

    Original Title

    blatt02

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides an exercise sheet for a lecture on advanced programming and algorithms. It includes 4 problems: 1) Analyzing the time complexity of selection sort, 2) Refactoring a Python implementation of selection sort for readability and reusability, 3) Analyzing the space complexity of selection sort, and 4) Proving correctness of an algorithm to find the maximum element in a sequence using a loop invariant.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    15 views2 pages

    Blatt 02

    Uploaded by

    aueouaeou
    The document provides an exercise sheet for a lecture on advanced programming and algorithms. It includes 4 problems: 1) Analyzing the time complexity of selection sort, 2) Refactoring a Python implementation of selection sort for readability and reusability, 3) Analyzing the space complexity of selection sort, and 4) Proving correctness of an algorithm to find the maximum element in a sequence using a loop invariant.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Mathematisch-Naturwissenschaftliche Fakultät

    Institut für Informatik, Anja Rey

    Exercise Sheet 2
    for the lecture on

    Advanced Programming and Algorithms


    Submission until Monday, 31st October, 12:30 pm.
    Discussion in the exercise classes on 7th and 11th November, 2022.

    Problem 1 to hand in: Running Time


    The following pseudocode describes the selection_sort algorithm which solves the
    Sorting computation problem: Given a finite sequence A of distinct integers (and its
    length), return A sorted ascendingly.
    selection_sort(A[0..n − 1], n):
    1 for j ← 0 to n − 1 do
    2 min ← j
    3 for i ← j + 1 to n − 1 do
    4 if A[i] < A[min] then
    5 min ← i
    6 key = A[j]
    7 A[j] = A[min]
    8 A[min] = key
    9 return A

    a) How does selection_sort work in comparison to insertion_sort? Describe it


    intuitively in one or two sentences.
    b) Analyse the asymptotic worst-case running time of selection_sort:

    • For each line of code, write down the number of running steps (dependent on
    the input size) in the worst case.
    • Sum up the total number T (n) of steps the algorithm needs in the worst case
    for an input of size n.
    • Provide a function f (n) as a representative upper bound in O-notation.
    • Proof formally that T (n) ∈ O(f (n)) holds.
    Problem 2 for discussion: Refactoring
    Take a look at the following Python implementation of selection_sort.
    1 def selection_sort ( A ):
    2 for j in range ( len ( A )):
    3 m=j
    4 for i in range ( j +1 , len ( A )):
    5 if A [ i ] < A [ m ]:
    6 m = i
    7 key = A [ j ]; A [ j ] = A [ m ]
    8 A [ m ] = key
    9 return A

    How can we optimise the readability and reusability of this code with respect to the
    following criteria?
    • consistency (e.g. spacing)
    • expressivity (e.g. variable names)
    • function extendability (unique purpose, brevity, testability)
    • avoiding redundancy
    Discuss: How do these changes affect the running time of the algorithm?

    Problem 3 for discussion: Space Complexity


    Similar to the running time of an algorithm, the memory space required by an algorithm
    can be analysed theoretically.
    a) Define a formal notion of space complexity.
    b) Analyse the space complexity of selection_sort

    Problem 4 for discussion: Correctness


    The following algorithm returns the maximum element within a given sequence.
    maximum(A[0..n − 1], n):
    1 max_index = 0
    2 for i ← 1 to n − 1 do
    3 if A[i] > A[max_index] then
    4 max_index ← i
    5 return A[max_index]
    a) State a loop invariant that holds at the beginning of each iteration of the for loop
    (lines 2 to 4).
    b) Proof the loop invariant.
    c) Use the loop invariant to show that indeed the algorithm returns the maximum of
    the input sequence.

    You might also like