Duke ECE551K

Sept. 30th 2023,从今天开始好好记笔记。
开学一个多月，我的评价是快乐不会消失只会转移，一点也乐不出来力。
All of Programming

Introduction

How to write a program

---

Algorithms

An algorithm is a clear set of steps to solve any problem in a particular class.

have at least one parameter (algorithms with no parameters exist)

everything is a number which is a key principle in programming.

This figure shows how u should approach designing your algorthim.上图表示了该如何实现一个算法。 However, note that “translate to code” comes only after you have an algorithm that you have tested by hand—giving you some confidence that your plan is solid before you build on it.只有当手动执行过了之后才去翻译algorthim为code。

It would seem that writing a correct algorithm to make a sandwich from an arbitrary list of ingredients is quite a complex task. Even if we did not want to implement that algorithm in code, but rather have it be properly executed by a person with no common sense (or a professor with a comedic disregard for common sense), this task is quite challenging to do correctly. How could we go about this task and hope to get a good algorithm?

The wrong way to write an algorithm is to just throw some stuff on the page, and then try to straighten it out later. Imagine if we approached our sandwich example by writing down some steps and having someone (with no common sense) try them out. After the kitchen catches on fire, we try to go in and figure out what went wrong. We then tweak the steps, and try again. This time, the kitchen explodes instead. We repeat this process until we finally get something that resembles a sandwich, and the house did not burn down.

1. Step1: Work an Example Yourself
   The first step in trying to design an algorithm is to work at least one instance of the problem— picking specific values for each parameter—yourself (by hand). 设计算法的第一步是手动做一个例子

假如卡在了这一步，一般说明有两个问题：

• the first case is that the problem is ill-specified - it is not clear what you are supposed to do. 不知道你该做什么 问需求去
• the second case where step1 is difficult is when u lack domain knowledge. 知道该做什么也不会做 学知识去

2. Step2: Write Down What U just Did
   U must think about what you did to solve the problem and write down the steps to solve that particular instance. 写下解决这个“特定实例”的步骤。another way to think about this step is to write down a clear set of instructions that anyone else could follow to reproduce your answer for the particualr problem instance that u just solved. 写下一组清晰的说明，其他人可以按照这些说明来重现你刚刚解决的特定问题实例的答案。

难的部分是think about exactly what you did to accomplish the problem

3. Step3: Generalize yours Steps
   Having solved one or more problems from the class we are interested in and written down the particular steps we executed to solve them, we are ready to try to generalize those steps into an algorithm. 把数个已经成功的步骤考虑实现为一个算法。

4. Step4: Test ur Algorithm
   测试第三步generate的算法有没有问题，可能会出现的错误有misgeneralizing，还有可能出现的错误有the casese we did not consider in designing our algorithm (即corner case)。解决这些问题的方法是回到第一步和第二步。

---

Reading Code

Variables

declaration

When executing code by hand, the effect of a variable declaration is to create a new box, labeled with the name of the variable. 创建一个新盒子，给盒子标记变量名

在C语言中，一个新申明的变量是uninitialized的，which means its value是undefined的。当这代码被电脑执行的时候，会从有限的盒子中分配一个目前没有在用的给这个变量 （has a finite (but quite large) number of boxes (memory locations), and the variable will be given one that is currently not in use）。这时候，这个盒子就被assign给了这个变量，但是box里的value是没有被初始化的，box里的value碰巧是多少，那这个变量目前就是多少，这是cannot predict的。

---

assignment

在创建完变量之后，使用assignment statements，改变box中的value。

an assignment statement starts with an lvalue 左值 on the left. an lvalue must be sth that “names a box” - indicating which box the assignment statement will change.

After the lvalue, comes a single equals sign (called the assignment operator), followed by an rvalue on the right, then a semicolon at the end. 左值之后跟着一个等于号，再跟着右值，最后是冒号结尾。The rvalue must be an expression, and its value will be placed in the box.

最简单的左值是variable, which names the variable’s own box.

An expression is a combination of values and operations that evaluates to a value.

int x;
x = 4;
int y = 6;
// 这line1+line2是line3相同的效果， declaration和initialization可以同时实现
// 也可以分开作为两个进行操作

---

Expressions

Expression is a combination of values and operations that evaluates to a value.

int x;
x = 4 + 3 * 2;
int y = x - 6;
x = x * y;

---

Functions

A function gives a name to a parameterized computation—it is the implementation in code of a specific algorithm. 函数为参数化计算提供了一个名称——它是特定算法的代码实现。

该说的其实在学java python的时候也都知道，看看就行了

---

Scope

The scope of a variable is the region of code in which it is visible. 变量的作用域是它在其中可见的代码区域。

其实也就是变量的作用范围，比如全局变量在所有的地方都可以使用，局部变量只在部分地方可以使用。

下图很清晰的展示了不同变量的使用范围的例子（即使他们都有相同的名字x）。

---

Printing

int x = 3;
int y = 4;
printf("x + y = %d", x + y);

• %d means this is a decimal number. 一说打印整数如int
• %f 用于打印浮点数，如float或double类型。
• %c 用于打印字符，如char类型。
• %s 用于打印字符串，如字符数组或指向字符串的指针。
• %x 用于打印十六进制整数。
• %o 用于打印八进制整数。
• %u 用于打印无符号整数。
• %p 用于打印指针地址。

int main (void) {
    int a = 42;
    int b = 7;
    printf("hello world\n");
    printf("a is %d\n", a);
    printf("b is %d, a+b is %d\n", b, a+b);
    return 0;
}
// \n用来换行
// \\用来打出一个实际上的\。

---

Conditional Statements

if else

下面是一个ifelse例子

if (x==3){
    y = z+1;
}
else if (x==2){
    y = z+2;
}
else{
    z = x-2;
    x = x+1;
}

switch case

switch (expression) {
    case value1:
        // 如果expression等于value1，执行这里的代码
        break;
    case value2:
        // 如果expression等于value2，执行这里的代码
        break;
    // 可以有更多的case
    default:
        // 如果expression与任何case都不匹配，执行这里的代码
}

注意在执行的过程中，假如有一个case符合了条件，并不代表后面的case就不会被expression便利，所以假如需要找到一个case就直接跳出，需要用break停止便利之后的case。

default是可选的，假如case都没有符合的话，可以执行default的内容。

---

Shorthand

---

Loops

while loops

while (x < n){
    y = y * x;
    x++;
}

do-while loops

do {
    y = y * x;
    x++;
}while (x < n);

for loops

for (int i = 0; i < n; i++){
    y = y * i;
}

continue & break

• break用于完全退出循环或switch语句。
• continue用于跳过当前迭代中的剩余代码，然后继续下一次迭代。

break是直接全部跳出，continue只是跳出这一轮的迭代

---

Types

Hardware Representation

Binary Numbers

二进制数，懂得都懂

---

Looking under the hood

Abstraction: the separation of interface (what sth does or how u use it) from implementation (how sth works).

Hex: 16进制，0-9代表0-9，A-F代表10-15。

---

Basic Data Types

char

char是最小的data type，只有8个bits。

---

int

int是32个bits构成，有signed和unsigned两种。

unsigned int组成中32位全部是数字，能表示的所有内容均为positive number。

signed int组成中第一位是符号为，后面31位为数字，所以有positive number （最左位为0）也有negative number（最左位为1）。

---

float & double

• Standards
  IEEE754 【IEEE754单精度浮点数的转换，32位浮点数】
• Precision
  A double offers more precision than a float. and A double takes up twice as much space as a float.

---

Expression have Types

Type conversion

假如有一个double加上int，处理器如何处理？
处理器有四种指令

1. add two 32-bit integers
2. add two 16-bit integers
3. add two 32-bit floats
4. add two 64-bit doubles

其他的都需要转变成这四个进行计算，比如double+int就会变成两个double相加

有时候会出现问题

unsigned int bigNum = 100;
int littleNum = -100;
if (bigNum > littleNum) {
    printf ("Obviously, 100 is bigger than -100!\n") ; else
} else {
    printf ("Something unexpected has happened!\n") ;
}

结果会是sth unexpected has happened，因为在signed int里负数最高位会被填充为1.

overflow & underflow

strings

a string is a sequence of characters that ends with a special character called the null terminator which is \0
string是使用第一个字符的位置在内存里，然后每8bits阅读直到读到了\0。

---

Complex, custom data type

struct

typedef

enumerated types

---

Writing Code

1. Step1: Work an example yourself
2. Step2: Write down what you just did
3. Step3: Generalize your steps
   • Generalizing values
   • Generalizing repetitions
   • Generalizing conditional behavior
   • Generalization: an iterative process
4. Step4: Test your algorithm
5. Step5: Translate your algorithm to code

---

Compiling and Running

---

Testing and Debugging

---

Recursion

head recursion

they perform a computation after they make a recursive call. 先递归call再计算。

tail recursion

page118
recursion call is the last thing the function does before returning. 递归call是return之前的最后操作。

补充一个对于head recursion和tail recursion的区别理解，head recursion是先调用再return value，tail recursion是在return的时候调用func

mutual recursion

互相递归（mutual recursion）是指两个或多个函数之间相互调用，形成一种递归循环的情况。这些函数彼此依赖，它们交替地调用对方来完成一项任务。互相递归通常用于解决问题，其中问题可以自然地分为几个相互关联的子问题。
two or more functions that call each other

def fibonacci_even(n):
    if n == 0:
        return 0
    else:
        return fibonacci_odd(n - 1)

def fibonacci_odd(n):
    if n == 0:
        return 1
    else:
        return fibonacci_even(n - 1)

Pointers

Pointer Basics

Pointers are a way of referring to the location of a variable.
int * x = &y
&的作用就是取地址运算符，所以指针x指向y的地址

const