In this course we will explore some of the fundamental concepts of computer science; specifically, formal languages (patterns of symbols, such as regular and context-free languages) and various machines that generate or recognize them (such as finite-state machines, pushdown automata, and Turing machines). Students will design simple mathematical machines that perform various tasks, such as recognizing strings in simple languages, manipulating strings, and computing numeric functions. We will explore the concept of undecidability to demonstrate that there are well-defined problems that do not admit general algorithmic solutions, and intractability to demonstrate that many problems possessing trivially expressed algorithmic solutions nevertheless remain unsolvable in practice. It will be assumed that students are familiar with at least one programming language and are acquainted with the basic tools of discrete mathematics (e.g. set theory and logic), fundamental algorithms (e.g. searching and sorting), and data structures (e.g. stacks, queues and graphs). Any student interested in this material is welcome to sit in on the class. The class will meet on Mondays and Wednesdays from 9:30 to 10:50 AM in ICS 180 . A discussion section will be held on Fridays from 10:00 to 10:50 AM in ICS 180. There will be no textbook for the class. Material discussed in lectures will be covered in greater depth by notes that will be distributed in class and made available in PDF format on the downloads page, which will also list homeworks and other handouts. Timely information concerning homeworks and lectures will be posted in the announcements section of the class discussion board; students will be expected to check the announcements periodically and are strongly encouraged to participate in discussions by posting questions and answers in appropriate threads within the discussion board. A detailed description of the grading and other policies will be maintained on the policies page. It will be assumed that each student is familiar with the posted policies, and will adhere to the principles of intellectual honesty to the best of their ability. Professor James Arvo email: arvo@uci.edu office: 4241 Bren Hall phone: (949)-824-9236 office hours: following class, or by appointment. Weng Leong Ng email: wlng@ics.uci.edu office: DBH 4091 hours: Friday, 11:00 AM to 12:00 noon