Post is pinned.
Reading schedule:
Languages & Countability :
Ch 0 Strings and Languages section, Ch 1.1 Finite Automata, Ch 1.2 Nondeterminism, and Ch 4.2 The Halting Problem ITC 
Ch 4.2 some of this depends on the next section, focus on Diagonalization Method through R is Uncountable theorem

Turing Machine:
Ch 3.1 Turing Machines ITC  

The Church-Turing Thesis:
Ch 3.2 Variants of Turing Machines ITC
Ch 3.3 The Definition of an Algorithm ITC  

Ch 4 Decidability ITC 

Ch 5 Reducability ITC 

P and NP:  
Ch 7.2 The Class P ITC
Ch 7.3 The Class NP ITC  

Ch 7.4 NP Completeness ITC 
Ch 34 NP Completeness IA  

NP-Complete Problems:
Ch 7.5 NP Complete Problems ITC
Ch 34.5 NP Complete Problems IA  

Dynamic Programming:
Ch 15 Dynamic Programming IA  

Ch 30 Polynomials and the FFT IA  

Maximum Flow:
Ch 26 Maximum Flow IA 

BP matching:
Ch 26.3 Maximum bipartite matching IA 

Linear Programming:
Ch 29 Linear Programming IA 

Ch 29.4 Duality IA 

Source:  Ethan Shepherd's comment on this post by +Jon Keller -

Disclaimer : Unofficial, and is made by a student

I have a brand new, bubble-wrapped, copy of the international version of Sipser I'm looking to sell reasonably...I somehow ended up ordering two when I did my order a while back. Let me know if interested.


If I overlooked this on the boards my apologies. During Spring 16 semester in Software Analysis and test one of the students posted a set of questions that the 6505 instructor said students shoul dbe able to solve (they posted with permission from the instructor)

These aren't the same as the 5 quick questions on the cca wiki page but rather two pages of questions that students could prepare for. Would anyone here be able to post those questions as we prepare for the fall semester?


Post has attachment
I created this temporary community for anyone that wants to discuss CCA in preparation for taking the class this fall of 2016. There is a rough schedule for going over the relevant (most) parts of the Rosen book. Tried to pick the chapters covering material from the readiness assesment, course description and syllabus. Plan is to have hangouts to discuss problems from the Rosen book and swap online resources for CCA. Anyone from OMSCS is invited...

Post has attachment

Post has attachment
I'm starting a study group, we are going over Problem Set 01- Countability for our first meeting.

Its this thursday at 8pm PST if your interested!

Based on the reading list, I noticed that we go through DFAs, NFAs, e-NFAs (epsilon closure  NFAs) and regular languages, and then jump to Turing Machines... Does this mean it is safe to assume other than basic automata and Turing Machines the class will not cover PDAs (Push down automaton) and CFLs (context free languages) or would it be a good idea to review those as well? I know the new instructor of the class may change some stuff up, but I thought I'd ask

Hi all,

I am curious, when writing proofs for this class, do you write on paper and scan, or do you use something more sophisticated, like LaTeX? Does the instructors and TAs care what format the submitted assignments are in?


Hello Everyone,

I'm considering this course for Spring 2016 and am wondering what the Fall 2015 schedule looks like in terms of due dates and exams. I have a trip booked in February and am trying to get a sense of when to expect the midterm exam in hopes that it would not coincide with the trip.

Also, who administers this course now? It lists the course creator on the course page, but the link goes to his LinkedIn profile where it appears that he now works for Udacity. Does he still administer the course?


Hi All,
I am planning to take this course for Spring 16. I have already started to go through books and videos related to the course to give me a head start.
I want to know questions format of the midterm and final exams. What types of questions should I expect? Do i need to write detailed proofs or draw diagrams? I have never used computer to do any math assignments so I am also looking for inputs on tools also that will help during the course and exams to write mathematical expressions.

If anyone share some sample questions, provided if it is not against the policy, that will be good.

Wait while more posts are being loaded