3 credits, 2 for lecture, 1 for lab, 4 hours per week.  Prerequisites: CS203 Data Structures andAlgorithm Analysis. This course introduces the theoretical foundations ofcomputer science. The first part of the course focuses on computability theoryi.e., “what is computable”. Students will learn the notions of computation andappreciate what can and what cannot be computed in principle. Computationalmodels of increasing complexity will be rigorously defined and analyzed toidentify the classes of problems that the respective models can solve and whichclasses of problems they cannot solve. Students will learn to appreciate to whatextent an increase in computational power allows a computational model to solvelarger classes of problems, and what problems, instead, are not solvable by anyreasonable computational model independent of the amount of finite availableresources. The second part of the course focuses on complexity theory i.e.,“what is computable efficiently”. Students will learn what classes of problemscomputational models can solve when provided with reasonable finite resources(time and space) and which classes of problems cannot be solved efficiently byany reasonable computational model. During the course students will encountersome of the most important open problems in computer science. Students willalso learn to appreciate why the notions of optimality are relaxed to seekingapproximate solutions and fixed parameter tractable solutions, rather thanoptimal ones, in the advanced algorithm design courses they study throughouttheir degree program. Overall, the course provides a thorough grounding intothe theoretical foundations of computer science and prepares students for moreadvanced theory courses.

展开英文描述 Expand English Description