اين تمرين با يك مدل جديده!! چاره اي نيست. بايد ياد بگيرين كه اين جور تمرين‌ها رو هم بفهمين و حل كنين!! اين ها رو حل كنيد و جلسه آينده تحويل بدين.
حل تمرين‌ها رو زود شروع كنيد تا اگه اشكالي داشتين فرصت داشته باشين ايميلي از من بپرسين.
_________________________
3. Let L1, . . . ,Lr be r unsorted lists, whose elements hold integers in the range [0, k−1]. Let n be the total number of elements among all of the lists. That is, if ni is the number of elements in Li, then n = n1 + n2 + · · · + nr. Describe an algorithm with total worst-case asymptotic time complexity of O(r +k +n) for getting all of the r lists into sorted order. So your final output will be r sorted lists (containing L1,L2, . . . ,Lr in sorted order). Be sure to analyze the time complexity of your algorithm.
3-1. If you cannot think of an algorithm with the specified time complexity, then for partial credit describe the most efficient algorithm you can and correctly analyze its time complexity.
_________________________
4. Consider the problem of sorting an unsorted array A of n elements which take on only two different values (e.g. A = [37, 60, 37, 37, 60, 60, 60, 60]).Note that the two values are not known to the algorithm.
4-1. Briefly but clearly describe an O(n) comparison-based algorithm for solving this problem.
4.2. Why doesn’t the comparison sorting lower bound of (n log n) apply to this problem?
حل تمرين‌ها رو زود شروع كنيد تا اگه اشكالي داشتين فرصت داشته باشين ايميلي از من بپرسين.
1. Design a O(N log N) algorithm to read in a list of words and print out all
anagrams. For example, the strings "comedian" and "demoniac"
are anagrams of each other.
Assume there are N words and each word contains at most 20 letters.
Designing a O(N^2) algorithms should not be too difficult,
but getting it down to O(N log N) requires some cleverness.)
________________________
2. Prove a lower bound for the following two problems:2.1. You are given an array votes of size 4 with each element holding either a 1 or a 2 (which indicates the candidate for which a vote was cast). The goal is to determine if there is a candidate who received 3 or more votes. The output should either be the empty set if no candidate received at least 3 votes, or otherwise a set holding the indices in votes for a candidate with 3 or more votes.Consider a model of computation in which the algorithm can only access votes by asking if v[i] == v[j] for any i, j. You are to give the best lower bound you can on the number of comparisons.2.2. You are given n coins identical in appearance; either all are genuine or exactly one is fake. It is unknown whether the fake coin is heavier or lighter than the genuine ones. Your model of computation to solve this problem is as follows. You can only learn about the coins through a provided weigh(set1,set2) method that takes as input two sets of coins set1 and set2 and returns one of the three possibilities:the two sets of coins have the same weight, set1 is heavier, or that set2 is heavier.The problem is to determine if any coin is fake, and if so which coin is fake and whether it is heavier or lighter than the genuine ones.
_________________________
3. Let L1, . . . ,Lr be r unsorted lists, whose elements hold integers in the range [0, k−1]. Let n be the total number of elements among all of the lists. That is, if ni is the number of elements in Li, then n = n1 + n2 + · · · + nr. Describe an algorithm with total worst-case asymptotic time complexity of O(r +k +n) for getting all of the r lists into sorted order. So your final output will be r sorted lists (containing L1,L2, . . . ,Lr in sorted order). Be sure to analyze the time complexity of your algorithm.
3-1. If you cannot think of an algorithm with the specified time complexity, then for partial credit describe the most efficient algorithm you can and correctly analyze its time complexity.
_________________________
4. Consider the problem of sorting an unsorted array A of n elements which take on only two different values (e.g. A = [37, 60, 37, 37, 60, 60, 60, 60]).Note that the two values are not known to the algorithm.
4-1. Briefly but clearly describe an O(n) comparison-based algorithm for solving this problem.
4.2. Why doesn’t the comparison sorting lower bound of (n log n) apply to this problem?
poor me
پاسخحذف