Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    Week 1

    Uploaded by

    arno.liut
    class note

    Copyright:

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

    Week 1

    Uploaded by

    arno.liut
    3 views4 pages
    class note

    Original Title

    week1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    class note

    Copyright:

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

    Week 1

    Uploaded by

    arno.liut
    class note

    Copyright:

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

    Comp 8900 Simple Practice Problems

    Questions:

    Consider the following algorithm.


    1. Algorithm CCS (A[0..n−1])
    2. for i ¬ 0 to n−1 do
    3. Count[i] ¬ 0
    4. for i ¬ 0 to n-2 do
    5. for j ← i+1 to n−1 do
    6. if A[i] < A[j]
    7. Count[j] ¬ Count[j]+1
    8. else
    9. Count[i] ¬ Count[i]+1
    10. for i ¬ 0 to n−1 do
    11. S[Count[i]] ¬ A[i]
    12. return S

    1. What does this algorithm do? What is the running time, expressed as the best big-O class?

    2. Consider an algorithm to insert an integer K into a sorted array of integers. We will make these assumptions about
    the algorithm:
    - we are working with primitive array types – not automatically resizable classes like ArrayList or Vector
    - the array contains n items prior to insertion (ie: size = n) ; after insertion the array will have size n+1
    - the array has space allocated for max items, where max >> n
    A prototype for the algorithm might be: Algo: Insert( A[0..n-1], K ) returns S[0..n]
    a. Write the pseudocode for this algorithm. Do not use any unstructured programming constructs in your solution
    (ie: no goto, break, or continue statements).

    b. What is the running time for this algorithm?

    Page 1
    Comp 8900 Simple Practice Problems

    3. What is the worst-case efficiency for each of these algorithms?


    int[] v = new int[n];
    for (int i = 0; i < n; i++)
    v[i] = i;

    --------
    ArrayList c;
    for (int i = 1; i <= n; i++)
    c.add ( new Integer(i) );

    Hint: ArrayList.Add is O(1) when adding at the end of the list, O(n) otherwise

    ----

    int sum = 0;
    int[]a = new int[n];
    int[]b = new int[10];
    for (int i= 0; i<n; i++) 1. algorithm abc( A[1..n] )
    for (int j = 0; j< 10; j++)
    sum += a[i] / b[j]; 2. bottom ¬ 1; top ¬ n
    3. swapped ¬ true
    -----
    4. while swapped is true do
    void f ( int[] a ) 5. swapped ¬ false
    {
    6. for i ¬ bottom to top-1 do
    Arrays.sort ( a );
    7. if A[i] > A[i+1]
    for (int i = 0; i<n; i++) 8. swap A[i] and A[i+1]
    a[n-i-1] = 3 * i -2; 9. swapped ¬ true
    10. // end for loop
    11. // end while loop
    12. // end algorithm
    for (int i = 0; i<n; i++)
    System.out.println ( a[i] );

    return a;
    }

    Note: you should assume that Arrays.sort() is O(nlogn).

    Also… what does this one do?

    Page 2
    Comp 8900 Simple Practice Problems

    Question 4:
    Consider the following problem, and answer the questions that follow.
    Minesweeper
    Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System. The goal of the game is to
    find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines
    there are adjacent to that square. For instance, suppose the following 4x4 field with 2 mines (which are represented by an * character):
    *...
    ....
    .*..
    ....
    If we would represent the same field placing the hint numbers described above, we would end up with:
    *100
    2210
    1*10
    1110
    As you may have already noticed, each square may have at most 8 adjacent squares.
    Input
    The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m <= 100)
    which stands for the number of lines and columns of the field respectively. The next n lines contains exactly m characters and
    represent the field. Each safe square is represented by an "." character (without the quotes) and each mine square is represented by an
    "*" character (also without the quotes). The first field line where n=m=0 represents the end of input.
    Output
    The output for each mine field consists of the n input lines with the "." characters replaced by the number of adjacent mines to that
    square. There must be an empty line between mine field outputs.
    Sample Input
    4 4
    *...
    ....
    .*..
    ....
    3 5
    **...
    .....
    .*...
    0 0
    Sample Output
    *100
    2210
    1*10
    1110

    **100
    33200
    1*100

    Page 3
    Comp 8900 Week 1 Algorithm Analysis

    Question 6a) Describe a solution to this problem in plain English.

    6b) Write pseudo-code for your solution. Note that your pseudocode will have 3 parts: Input from the file, processing, and
    output. You can attach a separate sheet of paper if you like.

    6c) Analyze your solution and determine it's big-oh efficiency class for an n by n matrix (for the processing of a single
    minefield).

    You might also like