Welcome

Tel-Aviv University
School of Computer Science
Computational Models (or more accurately, Introduction to the Theory of Computation)
0368.2200
Spring Semester 2010

# News

### Moed B published

Exam and solutions.

Took Moed B?
Find suggested answers on the exam page.
Didn't take Moed B?
Find how awful and difficult1 was it on the exam page.
Just got here by mistake?
Go to the exam page, everyone is there. No one comes here for the main page anyway.

(10 Aug 2010 12:49)

We finished grading the exam. The average was 78 and the median grade 81.

(11 Jul 2010 10:27)

### Answers for closed questions published

exam page

(05 Jul 2010 11:12)

### Recurring errors in HW #4

Words of wisdom from our grader.

Our grader provided us with a list of some of the common errors in HW #4.
If points were taken off and you don't understand why, try here.

(general) prove why your reduction works (or don't complain that you get no explanation why it's wrong).
(1b) missing explanation of why the model has a finite number of TMs for some specific $\Sigma$ (or that we need to deal with a specific $\Sigma$.
(3c) making a serial rather than parallel computation.
(3d) making a serial rather than parallel computation; using a non-constant number of tapes.
(4a) picking languages not in $\mathcal{RE}\setminus\mathcal{R}$ or not proving they're in $\mathcal{RE}\setminus\mathcal{R}$.

(24 May 2010 21:37)

### HW #6 published

HW #6 published

HW #6 published.
And yes, it's the last one.
Word of advice: some of you might be tempted to not submit since you already have 5 exercises.
Nonetheless, this is the main exercise that deals with complexity. Complexity will comprise a major part of the final exam and so it's quite important to know this material, whether you submit or not.
As always, have fun!

(23 May 2010 14:41)

### HW #5: a small correction.

Replaced 1-tape TMs by 2-tape TMs in Q6.

To avoid some complication, question 6 in HW #5 was amended and now speaks of two-tape TMs.

(16 May 2010 14:56)

### HW #5 extension

Following your requests we have decided to allow submission until Monday, May 24th, 1800 to the TAs post box.
We do not allow any e-mailing of any sort. Anyone who has a problem to reach the university on Monday, will have to submit the HW eariler.

(11 May 2010 21:34)

We hope you enjoy your 6.2 points (on average).

some stats:

Average: 62
Median: 60
stdev: 20

0: 2
10: 1
20: 5
30:15
40: 21
50: 34
60: 41
70: 44
80: 23
90: 12
100: 8

(27 Apr 2010 11:29)

### הגשת שיעורי בית בזוגות

אפשר להגיש שיעורי בית בזוגות

עקב צוק העיתים
וריבוי בסטודנטים
החלטנו בזאת
שיוגשו בזוגות
שיעורי בית ויוקל לבודקים

And it's optional - if you prefer submitting alone that's fine.

(26 Apr 2010 05:24)

Why wait for the university scanner?

Find our midterm quiz, with brief answers, on the Midterm page.

(23 Apr 2010 16:38)

### HW #4 published

HW #4 published

HW #4 published

(21 Apr 2010 10:11)

### About HW #3 submission date

Postponing just the TM questions.

Hello,

Several of you asked to submit HW #3 late.
This is not possible since we want to publish the solutions before the midterm quiz (read: at 18:00, just after I collect all submissions from Jonathan's box and mine).
However, we decided to allow you to submit just the TM questions (6,7,8) on Sunday (until 18:00). Obviously, we'll not publish those answers yet.

Also, let me point out that question 1(c) was worded somewhat ambiguously, so you might have gotten the wrong impression, i.e., that $L_3 = \Sigma^* \setminus\{\epsilon\}$. If so, please read the clarification.

(14 Apr 2010 23:08)

### HW #3 was revised

Hi all,

Q3(b) seems too difficult, so we replaced it by a simpler one.
We also threw in a bonus question (3$\frac12$). You don't have to do it, but you know you want to.…who am I kidding?

Get your fresh copy from the Home Assignments page.

(08 Apr 2010 23:45)

### HW 3 published

HW 3 published

HW 3 published

(06 Apr 2010 10:03)

### Myhill-Nerode exercise

The exercise not completed in Jonathan's class 14-15 is attached

Hi all,
Since we didn't complete the exercise for Myhill-Nerode I intended to show today, and I would like to continue with some more stuff on context free languages next time (after passover), I wrote it down and attach it here: Myhill-Nerode exercise.

Have a nice vacation.
Jonathan.

(18 Mar 2010 16:01)

### HW #2 extension and CNF definition

Due to some MOED B exams: extension until 28/3

Hi all,
Due to some MOED B exams of many of you we graciously give you 3 more days for HW #2 (until 0600pm). Notice that this date is already Passover vacation, and so if you wish not to arrive just for sumbission you should hand it by this Wednesday. No scanning/e-mailing of HW will be accepted.

Regarding question 7: the definition of CNF will be given in the lecture this week but for those of you who wish to solve it this weekend you can look at its simple definition in lecture 4, slide 48 (slides). This is all you need to know to solve the question.

(18 Mar 2010 14:34)

### HW #2 is published

Due in two weeks. Enjoy.

Hi all,

Please find homework #2 in the Home Assignments page.

Note that the due date, two weeks from today, is the first day of the Passover break.
Unless you absolutely need the entire fortnight, it'd probably be easier to finish everything and submit by Wednesday.

(11 Mar 2010 21:41)

### Due date of HW #1 is strict

No 2nd extension, but a creative ad-hoc solution.

Some ~5 students asked us whether it would be possible to submit HW #1 on Tuesday since they're not in TAU on Sundays and Mondays.
I would like to stress that this is not a valid reason for late submission. You can submit earlier or via a friend.

However, as a one-time remedy we will allow these students to submit either typed or scanned solutions via e-mail until Sunday at 18:00 and I will print them out. Send to Rani's email.

Obviously, this offer is intended for those specific few students. I do not expect 100, nor even 10 emails.

(11 Mar 2010 13:36)

### Overlap resolved

Recitation group 13 (Wed 14-15) rescheduled just after Computer Structure (Wed 17-18).

We managed to reschedule one of the Wednesday recitations, saving you the need to be in more than one place in the same time.
(Or, as the case seems to be in Thursday recitations, the need of more than one of you to occupy one seat in the same time…)

See the new hours and location in the Course Schedule page.

(09 Mar 2010 12:27)

### Location of recitation has changed

Thu 12-13 recitation has moved to Orenstein 103 Thu 14-15 recitation has moved to Dan-David 001

Hi all,
As you know Thu recitations are packed and we are trying to figure out a solution.

As a first step the venue of the recitation has changed:
We will meet on Thursdays between 12-13 in Orenstein 103 and between 14-15 in Dan-David 001. So please spread the rumor among your friends so people don't accidentally go to Shenkar 104.

However, although the classroom will be bigger, we strongly encourage you to try and attend the recitations on Wednesdays. Currently the consequence of this imbalance is that the recitation on Thu is much slower than the one on Wed. However, both groups will have the same exam at the end of the semester. So it is in your best interest to try and even things out.

Thanks.

(07 Mar 2010 15:48)

# Recent Forum Posts

{"module":"feed\/FeedModule","params":{"src":"http:\/\/tau-cm.wikidot.com\/feed\/forum\/cp-107255.xml","limit":"10","module_body":"+++ %%linked_title%%\n[[span style=\"color: gray; font-size: smaller\"]]By %%custom wikidot:authorName%% on %%date%%[[\/span]]\n%%long%%"}}