---
# System prepended metadata

title: Week 3
tags: [CS50’s Introduction to CS]

---

---
tags: CS50’s Introduction to CS
---
# Week 3
## Introductions of Algorithm
1. Times: 
    1. Upper bound: O(times) 
    2. Lower bound: Ω(times)
    * CS tends to throw away constant factors.
2. Algorithms:
    1. Search Algorithm
        1. Binary Search:
            1. Introduction: Binary search is used to search a number in a sorted array, Just like
                ![](https://i.imgur.com/1SGN83Z.png)
            2. Times:
                1. Worst-case performance: O(log n)
                2. Best-case performance: O(1)
                3. Average performance: O(log n)
    2. Sort Alorithm
        1. Selection Sort:
            1. Introduction: 
                ![](https://i.imgur.com/TldzPmx.png)
            2. Times:
                1. Worst-case performance: 
                    * Comparisons: О($n^2$)
                    * Swaps: О(n)
                2. Best-case performance:
                    * Comparisons: О($n^2$)
                    * Swaps: O(1)
                3. Average performance:
                    * Comparisons: О($n^2$) 
                    * Swaps: O(n)
        2. Bubble Sort:
            1. Introduction: Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order.
            2. Times:
                1. Worst-case performance: 
                    * Comparisons: О($n^2$)
                    * Swaps: О($n^2$)
                2. Best-case performance:
                    * Comparisons: O(n)
                    * Swaps: O(1)
                3. Average performance:
                    * Comparisons: О($n^2$)
                    * Swaps: О($n^2$)
        3. Merge Sort::
            1. Introduction:
                ![](https://i.imgur.com/GfD7XZw.png)
            2. Times:
                1. Worst-case performance: O(nlogn)
                2. Best-case performance: O(nlogn)
                3. Average performance: O(nlogn)
## Structure
1. Declaration:
    ```c
    struct name_of_the_struct
    {
        data_type 1 data_name 1;
        data_type 2 data_name 2;
        ...
        data_type n data_name n;
    }v 1,v 2, ... v n;
    ```
    1. The members of a structure are stored in memory in the order in which they're declared.
    2. Any names declared in structures won't conflict with other names in a program.
2. Initializing:
    ```c
    struct structure_name
    {
        data_type 1 v_name 1;
        data_type 2 v_name 2;
        ...
        data_type n v_name n;
    }v 1={v 1 a, v 1 b, ... v 1 n},
     v 2={v 2 a, v 2 b, ... v 2 n},
     ...
     v n={v n a, v n b, ... v n n};
    ```
    1. Expression used in a structure initializer must be constant. (This restriction is relaxed in C99.)
    2. An initializer can have fewer members than the structure it's initializing, and any "leftover" members are given 0 as their initial value.
    3. Write .v_name=v to assign a specific member.
    4. To initialize variables out of the structure definition, we can write
        ```c
        struct structure_name v={v 1 a, v 1 b, ... v 1 n};
        ```
3. Operation on Structures:
    1. To access a member within a structure, we write the name of the structure first, then a period, then the name of the member.
    2. The members of a structure are L values.
    3. The . operator takes precedence over & operator.
    4. Arrays can't be copied using the = operator, but an array embedded within a structure is copied when the enclosing structures is copied.
4. Using Typedef to Define a Structure Type
    ```c
    typedef struct
    {
        ...
    }type_name;
    ```
    type_name can be used in the same way as the built-in types.
    * ※There is another way to define a type:
        ```c
        struct structure_name
        {
            data_type 1 v_name 1;
            data_type 2 v_name 2;
            ...
            data_type n v_name n;
        }v 1={v 1 a, v 1 b, ... v 1 n},
         v 2={v 2 a, v 2 b, ... v 2 n},
         ...
         v n={v n a, v n b, ... v n n};
        typedef struct structure name v; 
        ```
5. Structures as Arguments and Return Values
    ```c
    //As arguments
    struct structure_name
    {
        ...
    };
    data_type function_name(struct structure_name variable_name,...)
    ```
    ```c
    //As Return Values
    struct function_name(...)
    {
        ...
    }
    ```
6. Compound Literals: A compound literal consists of a type name within parentheses, followed by a set of values in braces.
    ```c
    (struct structure_name){...}
    ```
7. Arrays of Structures:
    ```c
    struct structure_name
    {
       ...
    }
    struct structure_name array_name[size];
    ```
    1. size is optional.
    2. To initialize an array of structure, just use braces to enclose the members.

    