# computer science

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

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
• 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

• 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