Theory of Computation
Theory of Computation
TR 12pm-1:29pm in DRLB A8 (1/15 to 4/30)
Review of regular and context-free languages and machine models. Turing machines and RAM models, Decidability, Halting problem, Reductions, Recursively enumerable sets, Universal TMs, Church/Turing thesis. Time and space complexity, hierarchy theorems, the complexity classes P, NP, PSPACE, L, NL, and co-NL. Reductions revisited, Cook-Levin Theorem, completeness, NL = co-NL. Advanced topics as time permits: Circuit complexity and parallel computation, randomized complexity, approximability, interaction and cryptography. Discrete Mathematics, Automata theory or Algorithms at the undergraduate level.
511 is the least amount of work. knowing finite automata and definitions of P and NP is plenty of background
- 80 6HW+project, group
- 20 final exam
There will be no midterms, a single final exam, and homework problems (some challenging).
PART 1: Languages and Automata
PART II: Models of Computation, Undecidability, Basics of Recursive Function Theory
PART III: Computational Complexity
A Word of Advice
Expect to be held to high standards, and conversely! In addition to transparencies, I will post lecture notes. Please, read the course notes regularly, and start working early on the problems sets. They will be hard! Take pride in your work. Be clear, rigorous, neat, and concise. Preferably, use a good text processor, such as LATEX, to write up your solutions.
Due to the difficulty of the homework problems and in order to give you an opportunity to learn how to collaborate more effectively (I do not mean "copy"), I will allow you to work in small groups. A group consists of AT MOST THREE students.
You are allowed to collaborate with the same person(s) an unrestricted number of times.
Only one homework submission per group. All members of a group will get the SAME grade on a homework or a project (please, list all names in a group).
It is forbidden to use solutions of problems posted on the internet. If you use resources other than the textbook (or the recommended textbooks) or the class notes, you must cite these references.
关于就业我觉得21届的同学在美国的基本90%去了Amazon剩下的（据我所知）有去一些初创公司和一些传统行业也有少数选择继续深造的回国的同学不是很了解但是也都是有了中国的offer后回的国关于MCIT这个项目我不是很熟悉我认识一些很厉害的大神也认识一些学起来比较struggle的同学；总的而言还要看个人的努力关于MCIT的具体问题请参见官网关于选课我本人推荐CIS550 555 557 505 530和519请前往UPenn CIS的官网了解这些课程的具体名称和介绍我个人倾向选一些实用的课程所以你的目标如果是科研/进一步读博士那么请忽略以上推荐值得说明的是每个人的兴趣爱好可能不太一样所以在选修课上面可能有不同的倾向个人建议选课要结合自己的兴趣和基础如果仅凭兴趣选一些之前没有接触过的领域那么风险还是挺大的因为研究生级别CIS基本都是偏高阶的课程
30+去了g数量还是不少
前辈们推荐的课程有：505 software system， 555 Internet and web system, 502 Analysis of Algorithms 以及其他和自己兴趣相符合的选修课。等到下个学期结束的时候可以更深入的谈一下选课以及上课的感受。CIS项目需要10门课（10个course units）毕业：必修课包括1）至少一门理论课 2）至少一门system的课 3）最多一门machine learning的课，外加剩下的cis的选修课；7门课必须为cis开头的课程，外加3门cis批准的其他学院的选修课。当然如果你要是剩下的三门想继续上cis的课程也是绝对可以的，但是来一次UPenn如果一届Wharton的课都不上感觉有点可惜。此项目基本大概2年（4个学期）来完成，学校推荐的选课数目时：3 + 3 + 3 +1 或者 3 + 3 + （2+1）+ 2；第二种是指在第三学期的时候上两节cis或者cis批准的课程，外加一个EAS 896。EAS 896 是一个不算毕业学分但是能够维持full-time student身份的课程，大概是你需要去听一些讲座然后写一些summary之类的东西。
Graduate Students First Destinations – Career Services | University of Pennsylvania
CIS Common Teaching Assistant Application
resentation