Welcome to ESC190: COMPUTER ALGORITHMS AND DATA STRUCTURES

• Goals
• Learn the C Programming language
• Learn more advanced algorithms
• This week
• Start writing in C
• Differences between C and Python
• VS Code, VS Code with C
• Please install VS Code, C extensions for VS Code, MinGW-w64 on Windows/Developer tools on Mac
• Use https://www.onlinegdb.com/ for now

​

Python vs C

• Python is a high-level language
• Python is an interpreted language (although in principle you could write a compiler that converts Python to machine code)
• C is a lower-level language than Python
• C is a compiled language (although in principle you could write an interpreter that runs C code)
• C code can be much faster than Python code
• But can be slower to write

Thinking about ESC190: why?

• C programs can be much more efficient than the equivalent Python programs
• Compiled languages generally faster
• The flexibility allows for some shortcuts to be made
• C programs expose more of how code "really" runs on the computer
• You will be learning even more in second year, and ESC190 is preparation for that

Types in C

• Unlike in Python, every C variable needs to be declared -- you need to pre-specify what type of data is stored in the variable
• Types:� int: integer� double: double-precision floating point (like float in Python)

char: a character (e.g., ‘@’, ‘b’)

int *: address of int

char *: address of char

Strings in C

• C does not have a string type
• Instead, C represents strings as the address of the first character in the memory table where the string starts. The end of the string is the special ‘\0’ character�

@1032 is the address of the first character of the string “hi”�We can store @1032 in a variable of type char *

(coming up: const)

Note that “hi” is really of type const char *. More on that later

Literals in C

• Reminder: literals are data that is inputted directly into the code
• Integers and doubles work as in Python
• Symbols in single quotes are of type char
• Strings in double quotes are of type const char *: what’s stored is the address of the first character

Lecture 2

Goal: understand and practice the basic semantics of pointers C: arrays, strings, passing values to functions����Memory model sheet: https://docs.google.com/document/d/1ArkXvLQUWFbHNb_wwd_cdTB9RoOHKF0usXx7p1Bf-H4/edit?usp=sharing

Variable declaration in C (overview)

​

int a = 42;�long int la = 2103984203948L;�char c = ‘@’; // character: a single character

char *s = “abs”; //"string": the address of a first character in the

// sequence 'a', 'b', 's' '\0'

�char *p_c = &c; //& (called the ampersand) means "address of"

Arrays in C

int arr[] = {5, 10, 2}; // can use braces in initialization but not elsewhere�arr[0] = 3;

int arr2[10]; // an array of size 10

//cannot say: arr = {1, 2, 3}; // can only use {} notation for initialization

Overview: pointers

int a = 42;

int *p_a = &a; // p_a is the address of a��char *s = “abc”; // s is the address where the ‘a’ is��*p_a = 43; // put 43 in address p_a

Functions

// add takes in two integers, and returns an integer�int add(int a, int b)

{

return a + b;�}

Functions and pointers

int f(int *p_a)�{

*p_a = 43�}�// the function f takes an address, and puts 43 there

​

// analogous to passing a list in Python

Arrays and pointers

When used, arrays are generally converted to the pointer to the first element�(assume int a[])

�a[0] is the same as *(a+0), the first element of a

a[1] is the same as *(a+1), the second element of a

Lecture 3

More pointers!

Rules -- take 3

• All variables need to be declared� int a = 42;� char *s = “xyz”;� int arr[] = {4, 5};

int *p_a = &a;

• char * means a value of type “address of char”
• Array elements and string elements are stored in consecutive cells in memory
• s is the address where ‘x’ is stored
• arr gets converted into the address where the 4 is stored
• &a is the address where a is stored

Rules -- take 3

int a = 42;� char *s = “xyz”;� int arr[] = {4, 5};

int *p_a = &a;

​

• &a is the address where a is stored
• *p_a is the value at address p_a
• *arr is the value at address arr (same as arr[0])

Rules -- take 3

void f(int a)

{� a = 42;

}���f(43) copies 43 to local variable a. The variable a is local, so f has no effect.

Rules -- take 3

void f(int *p_a)

{� p_a = 0;

}���int a = 45;��f(&a) copies &a to local variable p_a. The variable p_a is local, so f has no effect.

Rules -- take 3

void f(int *p_a)

{� *p_a = 0;

}���int a = 45;��f(&a) copies &a to local variable p_a. The variable p_a is local, but *p_a is the same as a, so f does have an effect

Storing blocks of values

• Strings and arrays are examples of blocks of values
• Blocks of values are stored consecutively�
• 1032: ‘h’, 1033:’i’, 1034:’\0’ \\ “hi”
• 2064: 3 (2064+4): 4 \\ {3, 4}

Pointer arithmetic

• 1032: ‘h’, 1033:’i’, 1034:’\0’ \\ “hi”

​

char *s = “hi”; �s+1; // 1033�*(s+1); // ‘i’�

​

​

Pointer arithmetic

• 2064: 3 (2064+4): 4 \\ {3, 4}

int arr[] = {3, 4};�arr+1; // 2064+4�*(arr+1); // 4

Pointer arithmetic and arrays

arr[5] is the same as *(arr+5)

// syntactic sugar

// less used: “syntactic salt”: adding features to the syntax that constrain what can be said

// actual new syntax: L[3]

Summary

• int *, char*, …, int, char are types
• <LHS> = <RHS> copies the contents of <RHS> into <LHS>
• &a is "address of a"
• *p_a is "the contents at address p_a"
• p_a+i is the address i slots after p_a
• *(p_a+i) is the same as p_a[i]: the content at i slots after p_i
• void f(<type> a)�{� …

f(b) is the same as <local a> = b

• Arrays int arr[] gets converted to &(arr[0]) when used

Exercise 1

​

void change_a( )

{

​

}

int a;

change_a( ); // make a change.

// Now, write a function that wouldn't change a but

// change a local variable.

Exercise 1

​

void change_a(int *p_a )

{

// *p_a = 42; // would change

int b = 45;

p_a = &b;

}

int a;

change_a(&a); // make a change.

// Now, write a function that wouldn't change a but

// change a local variable.

Exercise 2

​

void change_arr0( )

{

​

}

int arr[3] = {5, 6, 7};

change_arr0( ); // make arr[0] change.

​

Exercise 2

​

void change_arr0(int *p_a )

{

*p_a = 42;

}

int arr[3] = {5, 6, 7};

change_arr0(&(arr[0])); // make arr[0] change. // change_arr0(arr)

change_arr0(&(*arr))

Lecture 4

Review: strings in C

• C does not have strings
• char s1[] = “abc”; // an array of type char, with the characters ‘a’, ‘b’, ‘c’, ‘\0’� // shorthand char s1[] = {‘a’, ‘b’, ‘c’, ‘\0’};
• char *s2 = “abc”; // put the block ‘a’, ‘b’, ‘c’, ‘\0’ somewhere in memory� // s2 is the address where the ‘a’ is stored
• Difference: an array is generally a local variable, only exists while the function is running. s2 stores the address of a memory block that will persist in memory�

const char *

• The literal “abc” is actually of type const char *
• The compiler will not let you modify values at addresses of type const char *
• But it will let you convert const char * to char * and then try to modify the values at the memory address�

char *s1 = “abc”; // warning: implicit conversion to char*�s1[0] = ‘x’; // will compile, but might crash at runtime�const char *s2 = “xyz”; // compiles with no warnings�s2[0] = ‘y’; // will not compile

const int, char, etc

const int a = 42;

a = 43; // error��const char c = ‘x’;

c = ‘y’; // error

char * const

char * const str = "hello";

str = “world”; //error

str[0] = ‘H’; // OK

​

const char * const

const char * const str = "hello";

str = “world”; //error

str[0] = ‘H’; // error���char s[] = “abc”;�s[0] = ‘x’; // fine�s = … // will not compile

The point of “const correctness”

• Less shooting yourself in the foot: if you know something is never supposed to be modified, you tell the compiler so that you don’t try to modify it by mistake

Why are string literals constant?

• May be more efficient: if you use the same literal in several different places, the compiler can choose to only store one copy
• But now all the copies are aliases, so dangerous to modify one
• Can unintentially modify several strings at once
• May be more cost-efficient: might like to store the string an an area of memory that is literally read-only

Lecture 5

Pointers: drills

Blocks of values + pointers

​

"C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off" Bjarne Stroustrup (inventor of C++)

​

(Python only lets you use a toy gun)

Summary: again

• int *, char*, …, int, char are types
• <LHS> = <RHS> copies the contents of <RHS> into <LHS>
• &a is "address of a"
• *p_a is "the contents at address p_a"
• p_a+i is the address i slots after p_a
• *(p_a+i) is the same as p_a[i]: the content at i slots after p_i
• void f(a)�{� …

f(b) is the same as <local a> = b

• Arrays int arr[] gets converted to &(arr[0]) when used
• (With few exceptions,) types on RHS and LHS must match

https://www.cs.toronto.edu/~guerzhoy/190/pointers/

Start Q1-Q10

Printf

printf is a variadic function

printf takes a format string, substitutes in values according to their types

​

printf("%d %c\n", 87, 87);

printf("%p\n", 87);

printf("%s\n", 87);

int x = 123;

printf("%ld\n", &x);

​

%d: decimal

%c: character

%s: string

%ld: long decimal

Lecture 6

What have we done so far?

• Basic C syntax
• Pointers (addresses of objects)
• address-of (&) and dereference (*) operators
• What printf does
• Functions, passing info to and from functions

Can now do anything -- but maybe not in the most convenient way!

​

​

Plan

• Custom data types
• Custom data types + pointers
• Memory management for custom data
• Comparison to Python

​

​

​

​

​

​

​

typedef

• typedef is a way to give names to types in C
• typedef int arr_sz_t;�arr_sz_t sz_of_arr = 15;
• Can be useful if you want to be able to later switch to using unsigned long int instead of int to store array sizes

​

Compound data structures

• Want to store several values that relate to the same object
• Acorn needs name, student number, GPA for each student�

struct student{

char name[200];

char number[11]; // why 11?� double GPA;�};

struct student{

char name[200];

char number[11]; // why 11?� double GPA;�};��int main()�{� // access fields of a struct using .� struct student s1 = {“John Doe”, “1234567890”, 3.3};� printf(“%s %f\n”, s1.name, s1.GPA);��}

structs and typedef

• Can use typedef to avoid having to repeat “struct”��typedef struct student{

char name[200];

char number[11]; // why 11?� double GPA;� } student;�� int main()� {� student s1 = {“John Doe”, “1234567890”, 3.3};� printf(“%s %f\n”, s1.name, s1.GPA);�� }�

Pointers to structs

typedef struct student{

char name[200];

char number[11]; // why 11?� double GPA;� } student;�� int main()� {� student s1 = {“John Doe”, “1234567890”, 3.3};� printf(“%s %f\n”, s1.name, s1.GPA);� student *p_s1 = &s1;� printf(“%s %f\n”, (*p_s1).name, (*p_s1).GPA); // *(p_s1.GPA)� }

Pointers to structs: ->

a->b is syntactic sugar for (*a).b�typedef struct student{

char name[200];

char number[11]; // why 11?� double GPA;� } student;�� int main()� {� student s1 = {“John Doe”, “1234567890”, 3.3};� printf(“%s %f\n”, s1.name, s1.GPA);� student *p_s1 = &s1;� printf(“%s %f\n”, p_s1->name, p_s1->GPA);� }

Sending integers, strings, and lists, in Python and C

Sending integers, strings, and lists, in Python and C

Sending integers, strings, and lists, in Python and C

Sending integers, strings, and lists, in Python and C

strlen

Starting at 1032, how many steps to get to '\0'?

​

Want: what is the length of the string starting at 1032?

A: 1 + [length of the string starting at 1033]

malloc

• Local arrays disappear once a function has finished running
• Arrays in C are not resizable
• malloc allocates space in the memory table to store a block of values

malloc

#include <stdlib.h>�int *block_int = (int *)malloc(sizeof(int) * 150); // allocate space for 150 integers

// malloc returns the address of � // element 0

// cast the address to int *

​

block_int[7] = 42;

*(block_int + 7) = 42; // REMINDER: those are the same

// block + 7 gets to the right location in the memory table

// because C knows how many cells ints take up

malloc example

// assume ints take up 2 memory cells each��������

​

int *block_int = (int *)malloc(sizeof(int) * 2); // block_int is 1032

block_int[0] = 5; block_int[1] = 7;

block_int + 1; // 1034�block_int[1]; // same as *(block_int+1)��

Thinking about ESC190

• C is more flexible than Python: need to decide if you need "address of" or "value at address" etc
• Needed to know this for tricky cases with output prediction in Python, but need to know this to get things to even compile in C!
• Need both practice and thinking through the conceptual framework: a little bit like math
• But C programming is like Python programming: you are solving a problem and expressing the solution in code
• In that sense, it's more of the same

sizeof

sizeof(int) // usually 4 bytes�sizeof(char) // always 1 byte

sizeof(char *) // usually addresses take up 8 bytes

// NOT the length of a string/array

sizeof(int *) // usually addresses take up 8 bytes� // NOT the length of a string/array��(When you get a choice between 32bit and 64bit downloads, that corresponds to differences in the size of the address

sizeof

int arr[] = {1, 2, 3};

sizeof(arr)/sizeoff(arr[0]) // length of the array

But note that if arr is passed to a function, it is converted to a pointer:

void sz(int *a) // int a[] is just syntactic sugar and won't help

{

sizeof(a); // 8

}

�int main()

{

int a[] = {1, 2, 3}

sz(a);

}

Lecture 7

​

sizeof

typedef struct student{

char name[200];

double GPA;

} student;

​

sizeof(student); // amount of space allocated for one student

malloc example

arrays vs memory blocks

• (local) arrays only exist until the function returns:
• Can try returning the address of an element of an array (or the address of another local variable, but behaviour is undefined
• Can create a memory block in a function, return and use it

// flip to VS Code for examples

free

• Good practice to free() memory blocks to you allocated
• C cannot use a malloc-ed block for something new until it's freed
• For continuously running programs, you might run out of memory
• On a modern OS, everything will be freed after the program terminates
• On less modern OSs, or on very light OSs, might not be the calse
• Memory leak: a situation where memory is allocated but never freed

int *block = (int *)malloc(sizeof(int) * 100)

// use block

free(block);

​

block[0] // undefined behaviour, might crash

Blocks of structs

typedef struct student{

char name[200];

int age;

} student;

// array:

student students[500];

student *students_block = (student *)malloc(sizeof(student)*500)

​

​

Dealing with strings

char s1[] = "hi"; // same as char s1[] = {'h', 'i', '\0'};

char s3[5]; strcpy(s3, s1);

char *s2 = 0;

// if "hi" is stored at addresses 1032, 1033, 1034�// the address of the 'h' is 1032, and s1 gets converted to 1032 when used

// s2 = s1; // legal, but strings are now aliases // s2 becomes 1032

strcpy(s2, s1); // not yet OK, since cannot copy to address s2

// same as s2[0] = s1[0], s2[1] = s1[1], ….�s2 = (char *)malloc(sizeof(char)*(strlen(s1)+1);

strcpy(s2, s1); // copy the contents of s1 into s2

Pointers to pointers

• Sometimes, want to change the value of a pointer inside a function��void set_to_0(int **p_p_a){

*p_p_a = 0; // set the value at address p_p_a to 0

// p_p_a happens to be of type int **

// so *p_p_a is of type int *

}�

int a = 42;

int *p_a = &a;

set_to_0(&p_a); // p_a is now 0. a is not affected!

Compilation

• The C compiler takes in C code and converts it to an executable file: something the operating system can run
• There are multiple C compilers
• gcc on ECF
• Can install gcc on OS X and Windows (as part of MinGW)
• VS Code runs the compiler when you press "Run", and then executes the executable

Running gcc manually

gcc myprogram1.c myprogram2.c -o myexec.exe

​

• The name of the executable is myexec.exe
• On Windows, executables have to have the extension .exe

Header files

• Can give the compiler instructions for tasks that are performed before compilation
• #include copy-and-pastes the file into the program

​

Flip over to example

Pre-processor

#define PI 3.14 → substitute 3.14 any time PI is in the program

• Different from defining PI as a variable -- this is simple search-and-replace
• Faster than defining a variable
• Can cause difficult-to-fix compile error (e.g., if there is a type and we write "3.14")

Pre-processor

• Can only define structs once
• Can use an "include guard" in an h file to avoid defining things twice if the header file is included multiple times

​

(switch to code)

Plan: Monday Jan 27

• Review of strings
• Strings and structs examples continued
• Back to basics: pointers
• Blocks of structs

Reminder: strings

char *name;

strcpy(name, "Alice"); // Bad: name is not a valid address, cannot copy "Alice" there

name = (char *)malloc(100*sizeof(char));�strcpy(name, "Alice"); //OK now

//name[0] = 'a'; // fine

name = "Alice"; // OK, but cannot modify name[0]; If didn't free name, that's a memory leak�name[0] = 'a'; // could crash

Reminder: strings

char name[200] = "Bob"; // same as {'B', 'o', 'b', '\0'}

strcpy(name, "Alice"); // fine, because there are are 200 spaces in name

//name = "Alice"; // Bad: cannot reassign to arrays

​

name[0] = 'a'; // OK

strings in structs

struct student1{

char *name; // we store the address where the name is stored

}

// need to allocate name for each student

struct student2{

char name[200]; // we store 200 characters

}�// don't need to allocate name for each student

Strings and structs

In VS Code

Handout

https://docs.google.com/document/d/1PJ5lHj7mU0v0-CQPHtuQyASbeyd2YIpN3q0Gn96zNmU/edit?usp=sharing

​

realloc

Can resize blocks of memory using realloc��char *str = (char *)malloc(100 * sizeof(char));

// want to make more space��str = (char *)realloc(str, 200 * sizeof(char));

Error checking

• malloc and realloc might not be able to find the amount of space you need

​

char *block = malloc(10000000);

if (block == NULL){

printf("Out of memory\n");

exit(1); // exit terminates the program. the 1 is sent to the operating system

}

Why exit()?

• Unclear what to do otherwise: trying to access a NULL pointer will lead to a crash without an error message
• But e.g. MS Word might just display an error message, refuse to do what you asked it to (e.g. open a huge document), and continue running
• The programs we are writing don't have the get input-> do what the user asks -> get more input loop, so we just crash as gracefully as we can

Should you do error checking?

• No error checking -> program may crash without a specific error message
• Program crashing may take down the whole computer with it
• For software that's intended to be used by others, the answer is obviously yes
• But if the point is to demonstrate a language feature in C, or to demonstrate a proof-of-concept implementation of an algorithm, error checking might just obfuscate the code + is annoying to do
• So in class we sometimes skip it
• But obviously it's necessary for real code!

Pointers :: units in physics

• Mass is expressed in Kg
• Acceleration is expressed in (m/s)/s
• Force is expressed in Newtons = kg*m/s^2
• If the acceleration of a falling object is 9.8 (m/s)/s and its mass is 1 kg, F = ma will produce an answer in Newtons
• If the units don't match, the calculation must be wrong!

create_str

​

Pointers :: Units in physics

char *str = 0;

create_str(&str, 100);

​

• Must send the address of str in order to change str
• The type of &str is address of char *, so char **

Aside: dimensional analysis in Physics is fake news

F = G*mM/R^2

F = k*qQ/R^2��The units only match because the units of G are magically N⋅m²⋅kg⁻²

^{and the units of k are magically}

strcat

Reminder:

• strcat(str1, str2) concatenates str1 and str2, assuming that str1 has enough space to accommodate extra characters from str2
• Will crash if not enough space: it does not check
• Again: C prioritizes efficiency, won't stop you from shooting yourself in the foot

Aside: ++

int a = 42;

int b = a++; // the value of a++ is the old value of a

// the effect of a++ is to increment a by 1

// the value of b is now 42, the value of a is 43

int c = ++b; // the value of ++b is the new value of b (i.e., b+1)

// the effect of ++b is to increment b by 1

// the value of b and c is now 43

strcpy and strcat with pointer arithmetic

*str2 = *str1 copies the value from address str1 to address str2

*str2++ = *str1++ copies values and then increments addresses

aside: value of assignment statement

the value of a = b is the new value of a

can do something like

while(a = b){ // stop if the new value of a is NULL

}

​

// we will not pursue this...

Blocks of structs + strings

Cleaning up mystr

https://www.cs.toronto.edu/~guerzhoy/190w23/lec/W07/adt.pdf

https://www.cs.toronto.edu/~guerzhoy/190w23/lec/W07/LL.pdf

​

Abstract Data Types:�Beyond Lists

Stack ADT

"LIFO": Last in, first out

Stack animation: https://www.cs.usfca.edu/~galles/visualization/StackArray.html

​

​

​

Stack operations

• push(elem): add elem to the top of the stack
• pop(): return the elem from the top of the stack, and remove it
• isEmpty(): return True iff stack is empty and element cannot be popped

Implementing the ADT

Can just use lists

• Python lists
• ArrayLists in C
• Linked Lists

The rest of the semester

• More specialized algorithms and data structures topics
• One way to look at it: techniques that have been proven effective at solving computational problems across several domains
• Another way to look at it: most problems are really difficult and have no known solutions, but computer scientists found a few domains where computer science is very effective

Aside

No known techniques to solve efficiently, and likely no possible techniques to solve efficiently:

• Determine if white or black wins in chess
• Find a proof for Fermat's Last Theorem
• Predict the weather on March 7, 2026
• Find the optimal timetable for EngSci 1S

Possible to do:

• Find (most) pages on the internet relevant to a query
• Generate all password of length 7
• Find a pretty good timetable for EngSci 1S

​

Python or C?

• It is easier to first prototype and debug conceptually-difficult algorithms in Python
• But many times the actually efficient solution is in C
• You need to know C
• Most Python in class, a mix of Python and Ci n the lab, C on Project 2

Today

Dynamic programming�https://www.cs.toronto.edu/~guerzhoy/190w23/lec/W10/DynamicProgramming.pdf

https://www.cs.toronto.edu/~guerzhoy/190w23/lec/W10/houses.py

�

Graphs

https://www.cs.toronto.edu/~guerzhoy/190w23/lec/W10/Graphs.pdf

​

What are we up to in ESC190?

• Practice programming
• The only way to understand what's really going on
• The only way to get to the point where you can recognize what's possible and not possible to do when faced with a new problem
• The only way to get to the point where you can create new things
• Understand how low-level programming
• Be able to optimize code when necessary
• Sometimes, just write part of the code in C
• Understand how computers work on a deeper level, prepare to understand hardware-level programming
• Understand how something like Python lists works under the hood
• See examples of algorithm design in action
• E.g., dynamic algorithms, graph algorithms today

ESC190 plans

• Finish up a few more examples of data structures/algorithms
• Talk about how generative AI works and how to use it
• Nobody really knows how to use it -- things are evolving
• Talk a bit about the bigger picture
• Moving from small programs to software
• Preparing for PEY interviews

(Min-)Priority Queue ADT

• A queue where each element has a priority
• Operations:
• enqueue(elem, priority): insert elem, with a given priority
• find_min: return the element with the smallest priority
• extract_min: remove the element with the smallest priority and return it
• Use: assign lower numbers to patients in the emergency room who need to be seen sooner

Shortest paths

https://www.cs.toronto.edu/~guerzhoy/190w23/lec/W13/Graphs3.pdf

​

https://www.cs.toronto.edu/~guerzhoy/190w23/labs/dijkstra.py

​

https://qiao.github.io/PathFinding.js/visual/

​

​

​

A* review

• Goal: find a cheap path from the start node to the end node
• Idea: explore a node that cheap to get to from start and looks like it's close to end
• Heuristic function: f(v) is small if v looks like it's close to end
• On a plane: can use the distance between the coordinates of v and end

Chess search graph

Nodes: game states

Edges: valid moves

Possible heuristic: quality of position ��

Math exams

Trying to find a path from �starting expression to "QED"

Nodes: equation�Edges: valid transformations���DFS: try to pursue each idea to the end�Dijkstra: visit every possible branch, find the shortest path to QED�A*: prioritize exploring states that are close to start and seem promising

Possible heuristic: length �of the expression��(Shorter expression probably�means you're close to something�you can assert as true)

Binary search trees

• Set ADT:
• Insert into the set
• Delete from the set
• Is the element in the set?
• Map ADT: [Python dictionary]
• Like set, but store a value associated with each key
• Binary Search Tree:
• The left descendents are smaller than the parent, the right descendants are larger than the parent

Is elem in tree?

Looking for 4��4 < 8, so look in the left subtree of 8�4 > 3, so look in the right subtree of 3�4<6, so look in the left subtree of 6�4==4, done

Complexity

Looking for 4��4 < 8, so look in the left subtree of 8�4 > 3, so look in the right subtree of 3�4<6, so look in the left subtree of 6�4==4, done��As many steps as the height of the tree�If the tree is complete, it has 2^h-1 elements and height h�O(h) = O(log n) steps

Complexity: worst case

Also a BST: �� 1

\

2

\

3

​

In the worst case, the "BST" is just a linked list, and the height is the same as the number of nodes (-1).

So look-up is O(n)

​

Making worst-case look-up O(log(n))

• There are ways to insert and delete that would keep the tree "almost" complete
• Requires more (but not much more) time for insertion and deletion, since the nodes may need to be rearranged
• Look up AVL trees and Red-Black Trees if you want to know more (not in this course)

class Node:

def __init__(self, key):

self.left = None

self.right = None

self.val = key

​

​

def make_tree():

root = Node(3)

root.left = Node(2)

root.right = Node(5)

root.left.left = Node(0)

root.left.right = Node(2)

# 3

# / \

# 1 5

# / \

# 0 2

return root

​

​

​

​

def in_tree(root, elem):

if root is None:

return False

if root.val == elem:

return True

if root.val < elem:

return in_tree(root.right, elem)

else:

return in_tree(root.left, elem)

​

Neural networks

https://docs.google.com/presentation/d/1C2DHNeDIHckku4Hbmq8UFPm1_JSDMGBr/edit#slide=id.p1

​