Induction

Prove the following using induction:
(a) For all natural numbers $n>2,2^n>2n+1$.

We proceed by induction on the variable $n$.
Base case$(n=3)$:$8>7$, which is correct.
Inductive Hypothesis:For arbitrary $n=m>2$, assume that $2^m>2m+1$.
Inductive Step: Because $m$ is positive number, then we have $2m>1$, so:
$$2^{m+1}=2\cdot 2^m > 2 \cdot (2m+1) = 4m+2 =2m+2m+2>2m+3$$
So we have $2^{m+1}>2(m+1)+1$,which completes the inductive step.

LATEX

(a) $\forall x\exists y((P(x)\land Q(x,y)) \Rightarrow x\le \sqrt y)$
(b) $\sum_{i=0}^k i = \frac {k(k+1)} 2$

Contraposition

Prove the statement “if $a+b<c+d$, then $a<c$ or $b<d$”.

The implication we are trying to prove is $(a+b<c+d)\Rightarrow((a<c)\land(b<d))$, so the contrapositive is $((a\ge c)\land(b\ge d)) \Rightarrow (a+b \ge c+d)$. The proof is straightforward, since we have both that $a\ge c$ and $b\ge d$,we can just add these two inequalities together, giving us $a+b\ge c+d$, which is exactly what we want to prove.

Writting in Propositional Logic

For rach of the following sentences,translate the sentence into propositional logic using the notation introduced in class,and write its negation.

(a) The square of a nonzero integer is positive.

We can rephrase the sentence as “If n is a nonzero integer, then $n^2>0$”. Which can be written as
$$\forall n \in \mathbb{Z},(n \neq 0) \Rightarrow (n^2>0)$$
or equivalently as
$$\forall n \in \Bbb{Z},(n = 0) \lor (n^2>0)$$
The latter is easier to negate, which is given by
$$\exists n \in \Bbb{Z},(n \neq 0) \land (n^2<=0)$$

This article focuses on how to use hexo to generate our static content management system, which is mostly from Youtube channel Mike Dane.Thanks for him!

Compiling and Running a C Program

In this lab, we will be using the command line program gcc to compile programs in C. The simplest way to run gcc is as follows (note that there is no file called program.c given in the lab files, this is just an example for your information).

1

$ gcc program.c

This compiles program.c into an executable file named a.out. This file can be run with the following command.

1

$ ./a.out

Problem 2: Picking representations

Assume we are working with 8-bit numbers for the entirety of this question.

For each part below, you will be given a choice between unsigned and two’s complement. It’s your job to pick the better number representation for the given criteria, or denote that both representations are equally good. Explain your answer in one sentence or less.:

You would like to represent the temperature in degrees Celsius:

We need 2’s complement becauseo of negative temperature.

Q1 Uncommented Code? Yuck!

The following functions work correctly (note: this does not mean intelligently), but have no comments. Document the code to prevent it from causing further confusion.

1
2
3
4
5
6

/*
*   recursively calculate array first n term sum
*/
int foo(int *arr, size_t n) {
    return n ? arr[0] + foo(arr + 1, n - 1) : 0;
}

1
2
3
4
5
6
7
8
9
10

2. /*
*   By reversed order to calculate the sum when current term is zero(i.e. if there's zero, plus 1).return bitwise invert plus 1 result(i.e. two's complement).The whole function calculate zero's count times -1.
*/
int bar(int *arr, size_t n) {
    int sum = 0, i;
    for (i = n; i > 0; i--) {
        sum += !arr[i - 1];
    }
    return ~sum + 1;
}

1
2
3
4
5
6
7
8

/*
*   some xor operations, does nothing.
*/
void baz(int x, int y) {
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
}

Q2 Programming with Pointers

Implement the following functions so that they perform as described in the comment.

1
2
3
4
5
6

/* Swaps the value of two ints outside of this function. */
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

1
2
3
4
5
6

/* Increments the value of an int outside of this function by one. */
void increment(int *x) {
    *x += 1;
    // (*x)++;
    // x[0]++;
}

1
2
3
4
5
6
7
8

/* Returns the number of bytes in a string. Does not use strlen. */
int mystrlen(char* str) {
    int count = 0;
    while (*str++) {
        count++;
    }
    return count;
}

Q3 Problem?

The following code segments may contain logic and syntax errors. Find and correct them.

1
2
3
4
5
6
7

/* Returns the sum of all the elements in SUMMANDS. */
int sum(int* summands) {
    int sum = 0;
    for (int i = 0; i < sizeof(summands); i++)
        sum += *(summands + i);
    return sum;
}

sizeof returns number of bytes in object,so we need to give the array length in parameters.The following is corrected answer.

1
2
3
4
5
6
7

/* Returns the sum of all the elements in SUMMANDS. */
int sum(int* summands, int len) {
    int sum = 0;
    for (int i = 0; i < len; i++)
        sum += *(summands + i);
    return sum;
}

1
2
3
4
5
6

/* Increments all the letters in the string STRING, held in an array of length N.
* Does not modify any other memory which has been previously allocated. */
void increment(char* string, int n) {
    for (int i = 0; i < n; i++)
        *(string + i)++;
}

Because of ++ operator has higher precedance than , So we can simply insert parenthesis around * operator.(i.e. ((string + i))++);and we can also exploit the association between array and pointer.The follwing are corrected answers.

1
2
3
4

void increment(char* string, int n) {
    for (int i = 0; string[i] != 0; i++)
        string[i]++;
}

1
2
3
4

void increment(char* string, int n) {
    for (int i = 0; i < n; i++)
        (*(string + i))++;
}

1
2
3
4

/* Copies the string SRC to DST. */
void copy(char* src, char* dst) {
    while (*dst++ = *src++);
}

This has no errors.suffix increment first use * operator then execute plus operation,while loop stops until there is a zero which means string end.

Yelp Maps

简介

• 目的：运用机器学习和Yelp学术数据集创建餐馆评分可视化界面

• 描述：Berkeley被划分成不同的区域，每个区域由最近的餐厅的预测评分被描画出不同颜色的阴影，黄色是5星，蓝色是一星。每一个点代表一个餐厅，并且其颜色由所在位置决定。比如：市中心的餐厅是绿色的。

  Read more »

Introduction

In this lab, you will learn about Unit Testing, JUnit, the 61B style checker, and we’ll also get a bit more debugging experience.

What is JUnit?

JUnit is a Unit Testing Framework for Java.