Scribd Logo
Upload

Welcome to Scribd!

  • 51 views

    Homework 4: You Are Allowed To Have at Most 4 Collaborators

    Uploaded by

    mah
    This document provides the instructions and problems for Homework 4 of COMPSCI 311: Introduction to Algorithms. There are 5 problems related to algorithms and data structures. Students are allowed to work in groups of up to 4 people and must list any sources of help. Solutions must be submitted as a PDF file by April 5th, 2021.

    Copyright:

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

    Homework 4: You Are Allowed To Have at Most 4 Collaborators

    Uploaded by

    mah
    51 views1 page
    This document provides the instructions and problems for Homework 4 of COMPSCI 311: Introduction to Algorithms. There are 5 problems related to algorithms and data structures. Students are allowed to work in groups of up to 4 people and must list any sources of help. Solutions must be submitted as a PDF file by April 5th, 2021.

    Original Title

    hw4

    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 provides the instructions and problems for Homework 4 of COMPSCI 311: Introduction to Algorithms. There are 5 problems related to algorithms and data structures. Students are allowed to work in groups of up to 4 people and must list any sources of help. Solutions must be submitted as a PDF file by April 5th, 2021.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    51 views1 page

    Homework 4: You Are Allowed To Have at Most 4 Collaborators

    Uploaded by

    mah
    This document provides the instructions and problems for Homework 4 of COMPSCI 311: Introduction to Algorithms. There are 5 problems related to algorithms and data structures. Students are allowed to work in groups of up to 4 people and must list any sources of help. Solutions must be submitted as a PDF file by April 5th, 2021.

    Copyright:

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

    COMPSCI 311: Introduction to Algorithms Spring 2021

    Homework 4
    Released 3/23/2021 Due 4/5/2021 11:59pm in Gradescope

    Instructions. You may work in groups, but you must write solutions yourself. List collaborators on your
    submission. You are allowed to have at most 4 collaborators. Also list any sources of help (including online
    sources) other than the textbook and course staff.
    If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words
    of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the
    running time of your algorithm and (e) justification for your running time analysis.
    Submissions. Please submit a PDF file. You may submit a scanned handwritten document, but a typed
    submission is preferred. Please assign pages to questions in Gradescope.

    1. (20p) Best Tree Nodes. You are given a binary tree (every node has at most 2 children) where each
    node has a positive integer value. Your goal is to pick either one or two of the nodes such that you
    maximize your score. Your score is calculated as the sum of the values of your picked nodes, minus a
    cost c for each edge on the paths to those nodes from the root of the tree. If an edge is on both of the
    paths, you only subtract c once for that edge.
    Design an algorithm that determines which node(s) to pick to maximize your gain. Determine the
    asymptotic complexity, and argue that this is the best possible.
    2. (20p) Recurrences Give asymptotic upper and lower bounds in the following recurrences. Assume
    appropriate base cases. Make your bounds as tight as possible and justify your answers.
    a) T (n) = 2T (n/2)(1 + log1 n ).
    Hint: You might need to add a linear term to either upper or lower bound for your proof to work.
    b) T (n) = maxn/3≤k≤2n/3 {T (k) + T (n − k) + n}
    3. (20p) Winning Moves You have 2n coins of arbitrary values placed in a row. You and a devious
    mathematician play a game where you alternate taking a coin from either of the ends. You start.
    For instance, with the row of coins 5, 3, 7, 10, you can take the 10, the mathematician might take the
    7, then you can take the 5 and gain 15 in total, while the mathematician would only have 10.
    Write a dynamic programming algorithm that precomputes the moves to maximize your winnings.
    Assume the devious mathematician tries the best moves to stop you.

    4. (20p) Proper Mixing. Charlie, a beginner student of cryptography tries to design an original
    encryption scheme (warning: do not try this at home). One step is mixing two streams of hexadecimal
    digits (0 to 9, A to F). The digits of each stream must appear in the same order in the output, but
    may be arbitrarily mixed with each other; such a mix is called a proper mix. In his attempt to mix
    things up well, Charlie might have coded the algorithm improperly. Given two streams of m and n
    digits respectively, and an output of m + n digits, determine whether the output is a proper mix of the
    two input streams or not.
    5. (20p) Max-Value Tree We are given an array of positive numbers a1 , a2 , ...an . We want to construct
    a binary tree that has these numbers as leaves, in the given order, from left to right. (Any non-leaf
    tree node must have two children). The value of a tree is the square root of the sum of the values of
    its two subtrees, and the value of a leaf is its number ai . Design an algorithm that constructs a tree of
    maximum possible value from the given leaves.

    You might also like