Search the whole station

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

229

## 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.

• 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 w1, w2 S, then 0 · w1 · w2 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.

The prev:

### Related recommendations

• #### 高性能计算机架构代写 Computer Architecture代写

658

ECE/CS 570 – High Performance Computer Architecture Homework #2 高性能计算机架构代写 1.Consider a shared-memory multiprocessor that consists of three processor/cache units and where cache co...

View details
• #### 计算机科学的数学表达与推理代写 CSC 165 H1代写 数学代写

227

CSC 165 H1 Term Test 3 — Question 1 of 4 计算机科学的数学表达与推理代写 Aids Allowed: Your own notes taken during lectures and office hours, the lecture slides and recordings (for all secti...

View details
• #### 计算机网络代做 CS 158A代写 计算机网络代写 计算机作业代写

128

CS 158A Computer Networks Problem Set 1 计算机网络代做 Problem 1 (0.5 pt each, no partial credit) Carefully read the following statements. If the statement includes incorrect information, ...

View details
• #### 数据分析工具代写 MAT 170代写 MATLAB代写 LATEX代写

420

MAT 170 FINAL PROJECT 数据分析工具代写 All Final Projects need to be done individually. No teams are allowed. We will refer all suspected acts of collaboration to student judicial All Final ...

View details
1