Course
| code | CS704 |
| credit_hours | 3 |
| title | Complexity Theory and Applications |
| arbic title | |
| prequisites | None |
| credit hours | 3 |
| Description/Outcomes | This is a first course in complexity theory, with emphasis on the hardness and intractability of problems. Tools for identifying NP-complete problems as well as polynomial reductions between problems are given. Different strategies for dealing with NP hard problems are presented, this includes approximation techniques as well as randomization methods. Other complexity classes such as NC, BPP, RP will be defined and explained. |
| arabic Description/Outcomes | |
| objectives | The students will be able to:• Understand the principles of complexity theory and learn a few of the complexity classes.• Identify NP-complete problems in a variety of diverse fields and applications.• Find methods to deal with the hard problems and produce efficient solutions. |
| arabic objectives | |
| ref. books | Computers and Intractability – A guide to the Theory of NP-completeness: M.Garey and D. Johnson, Freeman, San Fransisco. |
| arabic ref. books | |
| textbook | |
| arabic textbook | |
| objective set | |
| content set | |