## Yawen Chen/Teaching - Welcome! You are the
Visitors!

## 341/Additional Learning Resources

Illustration Slides
(only used for illustration, to arise your insterest, or help you to understand during lectures. Don't take it as a burden at home or for your examination preparation.)

### Interesting and helpful learning resources (short videos, demostrations, animations, magic tricks and etc. )

Note!These resources are only used for the studetns who want more challenges or information, which may be helpful for understanding the contents of the notes. These resources have no relationship with the examination. You should not use these information as the guidance of your exam. So, when you prepare for the answers of your final exam, you need to follow the descriptions/guidelines/contents in lecture notes/tutorials/textbook, instead of this extra resources.

### Guidance for learning 341 and preparing exam

1. Attend each Lecture and Tutorial

2. Missing any one will make you get lost and cost you more time to learn by yourself

3. Look at past exam questions, and know what the questions would like look

4. Exam “reduces to” (Lecture+Tutorial Materials)

5. 57 marks for complexity theory part

6. Include question for concepts and questions with problem (straightforward)

7. Email me any of your questions (usually reply within 24 hours:)

### Lec 16

Hitler and P = NP

A Beginner’s Guide to Big O Notation

TSP string demo

TM simulator

TM simulator

Computational complexity of mathematical operations

Want to get US $1,000,000 prize? Solve P = NP

P vs. NP and the Computational Complexity Zoo

Introduction - Intro to Theoretical Computer Science (good short series)

### Tut 16

Binary Arithmetic

Depth/Breadth first search

Hamilton path

Plyominoes

### Lec L17

P vs NP in The Simpsons

List of NP-complete problems

### Tut 17

Fair division

### Lec 18

SAT problem explained

SAT sovler

Efficient SAT Solving

Verify Combinatorial CNF SAT Encodings?

Isomorphic graphs demo

### Tut 18

bipartite-graph

bipartite-graph

### Lec 19

Proof Cook's Theorem

Cook's Theorem

To sit or 2-SAT

NP-complete problems figure

### Lec 20

3-color NP-complete problems

3SAT to graph coloring demo

### Tut 20

3SAT to Clique demo

3SAT to Clique Proof

### L21 Lecture

A "Turing Award" paper

Brief overview of Vertex Cover

reduce from 3SAT to VC

reduce from 3SAT to VC

a very good note for NP-hard

A doctoral student in computer science with focus on Theoretical Computer Science

### Tut 21

Hamiltonian cycle

Eulerian path

### Lec 22

Embedding Np Complete Problems in Restaurant Orders

### Tut 22

Subset sum algorithm

Demo of the tutorial Subset-Sum matrix

A pseudo-polynomial time algorithm for Subset-Sum

Strongly NP-complete and Weak NP-complete

### L23 Lecture

Movie: Travelling Salesman - Official Trailer (Four mathematicians are hired by the US government to solve the most powerful problem in computer science history.)

Traveling Salesman Problem Visualization

Optimization Problems and Decision Problems

A compendium of NP optimization problems

Ticket to Ride (Hamilton circuit)

Binary Search (Tree Demo)

Map and Graph Corlor problem

Rectangle Packing Tool

the art of proving np-completeness

### L24 Lecture

Demo minimum spanning tree

Demo minimum spanning tree

Approximation TSP Demo

### TUT 24

2-approximation for Minimum Vertex Cover Problem

### Additional

Big O notation: What you have learned in 242

Algorithmic Complexity and Big-O Notation

Big O noation by Wiki

Complexity of simple algorithms

NP-Complete - A Rough Guide

I can't find an efficient algorithm, but neither can all these famous people.

A simple definition of P and NP

Best explanation of P=NP problem for a layman

List of NP-complete problems

An Annotated List of Selected NP-complete Problems

The P-versus-NP page

Computational Complexity

How to prove that a problem is NP complete?

2-approximation for Minimum Vertex Cover Problem

CHAPTER 37: APPROXIMATION ALGORITHMS

Turing Machines

Online Turing Machines simulator

Online Turing Machines simulator with digram/multi-tape

Proof That Computers Can't Do Everything (The Halting Problem)

Theory of Computation from other VIGINIA

Theory of Computation from udacity

Theory of Computation from MUN

Theory of Computation from mianmi

Theory of Computation from nthu

Theory of Computation from nthu

## Feel free to emal me know if I miss anything or you want me to add anything! I Love emails!

Education Wiki

Back to Yawen's Homepage

Back to CS Home Page