计算理论导论代写 CSC236H代写 LaTeX代写 计算机作业代写

CSC236H-Assignment 1

计算理论导论代写 • For this assignment, you must work individually, produce a PDF file named a1.pdf, and submit it to MarkUs. Submissions must be typed.

• For this assignment, you must work individually, produce a PDF file named a1.pdf, and submit it to MarkUs. Submissions must be typed.

• Please refer to the course information sheet for the late submission policy.

• For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

In particular, keep in mind that one of the objectives of this assignment is to get you to practice writing proofs. This means that a good amount of marks are allocated to the structure of your proofs and how they were written up.

1. Consider the following solitaire game, played with a collection of n identical coins. 计算理论导论代写

• At any time during the game, the coins are divided into a number of groups. At the beginning, all the coins are in the same group.

• The game is played in rounds. During each round, you pick one of the existing groups (any one) that contains more than one coin and you split it into two smaller groups (in any way you like).

• Your gain in that round is the product of the sizes of the two new groups, in dollars!

• The game is over once every group contains exactly one coin.

For example, suppose you start with 13 coins. For your first round, you may decide to split the group into a group of 6 and a group of 7: this pays 6 × 7 = 42 dollars. In the next round, if you break the 7-coin group into a group of 2 and a group of 5, you will get 10 more dollars (for a total of 52 dollars so far). And so on.

Use induction to prove that for any natural number n ≥ 1, if you start the game with a single group of n coins, then regardless of how you play the game (i.e., no matter how you choose to split up the groups), you always win a total of exactly n(n − 1)/2 dollars.

Page limit for this question : 1 Page (the sample solution is less than a page). Any material after the first page will NOT be marked.

3. Consider the set of binary strings S defined recursively as follows: 计算理论导论代写

• 1 ∈ S;

• if w₁, w₂ ∈ S, then 0 · w₁ · w₂ ∈ S (a · b denotes concatenation of two strings a and b).

Let Z(v) denote the number of occurrences of 0 in the binary string v and O(v) denote the number of occurrences of 1 in v.

Use structural induction to prove that, for every string w ∈ S and every proper prefix u of w, O(u) ≤ Z(u).

(The string u is a prefix of the string w iff there exists a string v such that w = u · v. It is a proper prefix of w iff neither u nor v is the empty string).

Page limit for this question : 2 Pages (the sample solution is less than tow pages). Any material after the second page will NOT be marked.

更多代写：prolog代写  雅思作弊被抓  英国EE代写  论文字体要求  如何写literature review  review essay怎么写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写