12:25

ECS 120 0:7 combinatorics (discrete math review)

09:25

ECS 220 5b:6.6-4 two lemmas and full proof of…

ECS 220 5b:6.6-4 two lemmas and full proof of Ladner_s theorem

07:35

ECS 220 5b:6.6-2 almost proof of Ladner's…

ECS 220 5b:6.6-2 almost proof of Ladner's theorem

07:45

ECS 220 5b:6.6-1 Ladner's theorem, existence…

ECS 220 5b:6.6-1 Ladner's theorem, existence of NP-intermediate problems

07:59

ECS 220 5a:6.4-5 an oracle making P≠NP

ECS 220 5a:6.4-5 an oracle making Pâ‰ NP

04:04

ECS 220 3a:4-5.2 string representation of Turing…

ECS 220 3a:4-5.2 string representation of Turing machine

06:26

ECS 220 2b:4.3-1 formal definition of NP and NP…

ECS 220 2b:4.3-1 formal definition of NP and NP in EXP

09:53

ECS 220 1a:2.1 problems and solutions

02:12

ECS 120 9c:5 N vs. {0,1}*

11:52

ECS 120 8b:2 definition of polynomial-time…

ECS 120 8b:2 definition of polynomial-time reducibility

Errata: starting at 8:30, I show Python code with the function reduction_from_clique_to_independent_set. This should be reduction_from_independent_set_to_clique instead.

09:04

ECS 120 7a:2 definition of P, encoding of data…

ECS 120 7a:2 definition of P, encoding of data structures

07:44

ECS 120 6c:1 TMs versus code

11:34

ECS 120 6a:1 languages decided-recognized by TMs

08:00

ECS 120 5b:9 pumping lemma proof that (01)n(10)n…

ECS 120 5b:9 pumping lemma proof that (01)n(10)n is not regular

03:35

ECS 120 5b:8 pumping lemma proof that 0i1j is not…

ECS 120 5b:8 pumping lemma proof that 0i1j is not regular

05:07

ECS 120 5b:7 pumping lemma proof that 1n2 is not…

ECS 120 5b:7 pumping lemma proof that 1n2 is not regular

AggieVideo video portal by Academic Technology ServicesUC Davis | Information and Educational Technology | User Guides and Technical Documentation