Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    算法设计与分析作业1

    Uploaded by

    王铭珺
    C++ homework

    Copyright:

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

    算法设计与分析作业1

    Uploaded by

    王铭珺
    15 views2 pages
    C++ homework

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    C++ homework

    Copyright:

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

    算法设计与分析作业1

    Uploaded by

    王铭珺
    C++ homework

    Copyright:

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

    081203M04001H - Algorithm Design and Analysis

    Assignment 1 September 21, 2022

    Divide and Conquer


    a. You can choose three from problems 1-6.
    b. For problems 1-6, you should do at least the following things:

    (1) Describe your algorithm in natural language AND pseudo-code;


    (2) Draw a “subproblem reduction graph”, where nodes represent subproblems, and edges
    describe the “reduction relationship” between them for every problem you choose in
    problems 1-6;
    (3) Prove the correctness of your algorithm;
    (4)Analyse the complexity of your algorithm

    Question1

    You are interested in analyzing some hard-to-obtain data from two separate databases. Each
    database contains n numerical values, so there are 2n values total and you may assume that no
    two values are the same. You’d like to determine the median of this set of 2n values, which
    we will define here to be the nth smallest value.

    However, the only way you can access these values is through queries to the databases. In a
    single query, you can specify a value k to one of the two databases, and the chosen database
    will return the kth smallest value that it contains. Since queries are expensive, you would like
    to compute the median using as few queries as possible. Give an algorithm that finds the
    median value using at most O(log n) queries.

    Question2

    Given a binary tree T, please give an O(n) algorithm to invert binary tree. For example below,
    inverting the left binary tree, we get the right binary tree.
    Question3

    There are N rooms in a prison, one for each prisoner, and there are M religions, and each
    prisoner will follow one of them. If the prisoners in the adjacent room are of the same religion,
    escape may occur. Please give an O(n) algorithm to find out how many states escape can
    occur.

    For example, there are 3 rooms and 2 kinds of religions, then 6 different states escape will
    occur.

    Question4

    Given a binary tree, suppose that the distance between two adjacent nodes is 1, please give a
    solution to find the maximum distance of any two node in the binary tree.

    Question5

    Please implentment QuickSort with a 3-way partition

    Question6

    There are n ropes with different length. If m ropes of the same length are cut from them,
    please find the longest length of each of these m ropes

    You might also like