Scribd Logo
Upload

Welcome to Scribd!

  • 84 views

    Swe116 Tutorial Sheet I

    Uploaded by

    Afong Collins
    This document contains a tutorial sheet with 11 problems related to algorithms. Problem 1 asks to write directions and a recipe with algorithmic precision. Problem 2 involves finding the greatest common divisor of two numbers using Euclid's algorithm. Problem 3 proves a property of Euclid's algorithm. Problem 4 presents a logic puzzle that can be solved algorithmically. The remaining problems involve algorithms for finding roots of equations, binary representation, ATM cash dispensing, phone calls, graph coloring, and sorting arrays by counting elements.

    Copyright:

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

    Swe116 Tutorial Sheet I

    Uploaded by

    Afong Collins
    84 views3 pages
    This document contains a tutorial sheet with 11 problems related to algorithms. Problem 1 asks to write directions and a recipe with algorithmic precision. Problem 2 involves finding the greatest common divisor of two numbers using Euclid's algorithm. Problem 3 proves a property of Euclid's algorithm. Problem 4 presents a logic puzzle that can be solved algorithmically. The remaining problems involve algorithms for finding roots of equations, binary representation, ATM cash dispensing, phone calls, graph coloring, and sorting arrays by counting elements.

    Original Title

    SWE116 TUTORIAL SHEET I

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a tutorial sheet with 11 problems related to algorithms. Problem 1 asks to write directions and a recipe with algorithmic precision. Problem 2 involves finding the greatest common divisor of two numbers using Euclid's algorithm. Problem 3 proves a property of Euclid's algorithm. Problem 4 presents a logic puzzle that can be solved algorithmically. The remaining problems involve algorithms for finding roots of equations, binary representation, ATM cash dispensing, phone calls, graph coloring, and sorting arrays by counting elements.

    Copyright:

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

    Swe116 Tutorial Sheet I

    Uploaded by

    Afong Collins
    This document contains a tutorial sheet with 11 problems related to algorithms. Problem 1 asks to write directions and a recipe with algorithmic precision. Problem 2 involves finding the greatest common divisor of two numbers using Euclid's algorithm. Problem 3 proves a property of Euclid's algorithm. Problem 4 presents a logic puzzle that can be solved algorithmically. The remaining problems involve algorithms for finding roots of equations, binary representation, ATM cash dispensing, phone calls, graph coloring, and sorting arrays by counting elements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    UNIVERSITY OF BUEA

    COLLEGE OF TECHNOLOGY

    TUTORIAL SHEET I

    PROGRAM: HND

    COURSE CODE: SWE 114


    COURSE TITLE: Introduction to Algorithm
    Course Instructor: Humphrey OJONG

    1. a) Write down driving directions for going from your school to your home
    with the precision required by an algorithm.

    b) Write down a recipe for cooking your favorite dish with the precision
    required by an algorithm.

    2. a) Find gcd(83, 52)


    b) Estimate how many times faster it will be to find gcd(83, 52) by Euclid’s algorithm
    compared with the algorithm based on checking consecutive integers from min{m, n}
    down to gcd(m, n).

    3. Prove that for every pair of positive integers m and n, the equality
    gcd(m, n) = gcd(n, m mod n)
    Note: This problem requires you to prove the correctness of the Euclid’s algorithm.

    4. A farmer finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs
    to transport all three to the other side of the river in his boat. However, the boat has room
    for only the peasant himself and one other item (either the wolf, the goat, or the cabbage).
    In his absence, the wolf would eat the goat, and the goat would eat the cabbage.
    Solve this problem for the peasant or prove it has no solution.

    5. Write a pseudocode for an algorithm for finding real roots of equation


    a𝑥 2 + bx + c = 0
    for arbitrary real coefficients a, b, and c.

    6. Describe the standard algorithm for finding the binary representation of a positive
    decimal integer
    a) in English.
    b) in a pseudocode.

    1
    7. Describe the algorithm used by your favorite ATM machine in dispensing cash. (You may
    give your description in either English or a pseudocode, whichever you find more
    convenient.

    8. Describe the algorithm used by a telephone to place a phone call. (You may give your
    description in either English or a pseudocode, whichever you find more convenient.)

    9. Königsberg bridges The Konigsberg bridge puzzle is universally accepted ¨ as the problem
    that gave birth to graph theory. It was solved by the great Swiss-born mathematician
    Leonhard Euler (1707–1783). The problem asked whether one could, in a single stroll, cross
    all seven bridges of the city of Konigsberg exactly once and return to a starting point.
    Following is a sketch ¨ of the river with its two islands and seven bridges:

    a) State the problem as a graph problem


    b) Does this problem have a solution? If you believe it does, draw such a stroll; if you
    believe it does not, explain why and indicate the smallest number of new bridges that
    would be required to make such a stroll possible.

    10. Consider the following map:

    a) Explain how we can use the graph-coloring problem to color the map so that no two
    neighboring regions are colored the same.
    b) Use your answer to part (a) to color the map with the smallest number of colors.

    11. Consider the algorithm for the sorting problem that sorts an array by counting, for each of
    its elements, the number of smaller elements and then uses this information to put the
    element in its appropriate position
    in the sorted array:

    Algorithm ComparisonCountingSort(A[0..n - 1], S[0..n - 1])


    //Sorts an array by comparison counting

    2
    //Input: Array A[0..n - 1] of orderable values
    //Output: Array S[0..n - 1] of A’s elements sorted in nondecreasing order
    for i ← 0 to n - 1 do
    Count[i] ← 0
    for i ← 0 to n - 2 do
    for j ← i + 1 to n - 1 do
    if A[i] < A[j]
    Count[j] ← Count[j] + 1
    else Count[i] ← Count[i] + 1
    for i ← 0 to n - 1 do
    S[Count[i]] ← A[i]

    a) Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47
    b) Is this algorithm stable?
    c) Is it in-place?
    For further reading, see Section 2.1 Insertion Sort; Introduction to Algorithm.

    You might also like