Description: What is computer science about? What is the difference between computers and other machines? What are the limits of computation? Are there computers that are not machines? Understand the basic issues of computability, complexity, and network effects, and learn to apply them in the practice of computation.
Objectives
Students encounter the basic models of data processing and computation, and are capable to perform high level analyses
Students understand the meaning and the consequences of reductions and equivalences between the basic models of data processing and computation
Students are familiar with the main hierarchies of classes of languages
Students gain a clear understanding of the idea of computation, as universal and partial evaluation of programs.
Students understand computational complexity and hardness, and are capable to perform basic complexity analyses.
Students are familiar with the role of randomness in computation.
Students understand the need and the techniques for building their solutions of hard engineering problems in computation on the solid foundations of computer science
Students are able to discern and analyze local aspects of computation from the network effects.
Students can function effectively in teams to accomplish a common goal.
Students have an understanding of social issues of computation.
Students can communicate effectively with a range of audiences concerned with the basic problems of computation.
Students can analyze the local and global impact of computation on individuals, organizations, and society.
Students can recognize the need for and an ability to engage in continuing professional and career development in the diverse areas of computer science and engineering.
Course Learning Outcomes: See objectives.
Program Learning Outcomes
Prerequisites: 141 or consent
Textbook(s): 1. Michael Sipser, Introduction to the Theory of Computation 2. John E. Savage, Models of Computation: Exploring the Power of Computing
Grading: 3 homework assignments (25%), midterm test (25%), project and class presentation (25%), final exam (25%)
Schedule