A joke The boss wants to produce programs to solve the follow two problems Euler circuit problem given a graph G, find a way to go through each edge exactly once Hamilton circuit problem given a graph G, find a way to go through each vertex exactly once The two problems seem to be very similar Person a takes the first problem and person b takes the secon Outcome: Person a quickly completes the program, whereas person b works 24 hours per day and is fired after a few months 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 16 A joke: The boss wants to produce programs to solve the following two problems Euler circuit problem: • given a graph G, find a way to go through each edge exactly once. Hamilton circuit problem: • given a graph G, find a way to go through each vertex exactly once. The two problems seem to be very similar. Person A takes the first problem and person B takes the second. Outcome: Person A quickly completes the program, whereas person B works 24 hours per day and is fired after a few months
Euler Circuit: The original Konigsberg bridge Land Rive Isand onigsberg grap 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 17 Euler Circuit: The original Konigsberg bridge
Hamilton circuit Traveling salesman problem(tsP), 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 18 Hamilton Circuit
A joke(continued) Why? no body in the company has taken C$4335 Explanation: Euler circuit problem can be easily solved in polynomial time Hamilton circuit problem is proved to be NP-hard So far, no body in the world can give a polynomial time algorithm for a np-hard problem Conjecture: there does not exist polynomial time algorithm for this problem 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 19 A joke (continued): Why? no body in the company has taken CS4335. Explanation: Euler circuit problem can be easily solved in polynomial time. Hamilton circuit problem is proved to be NP-hard. So far, no body in the world can give a polynomial time algorithm for a NP-hard problem. Conjecture: there does not exist polynomial time algorithm for this problem
Evaluation of the course Course work 30 Four assignments(25%) 5 points for each of the first three assignments 10 points for the last assignment One term paper(5%) Find an open problem from internet State the problem definition in English Write the definition mathematically Summarize the current status No more than I page a final exam 70% 2021/26 CS4335 Design and Analysis of
2021/1/26 CS4335 Design and Analysis of Algorithms /Shuai Cheng Li Page 20 Evaluation of the Course Course work: 30% Four assignments (25%) • 5 points for each of the first three assignments • 10 points for the last assignment One term paper (5%) • Find an open problem from internet. – State the problem definition in English. – Write the definition mathematically. – Summarize the current status – No more than 1 page A final exam: 70%