This course has concluded and all grades have been posted.
Reminder that we have our last test on March 25th, in class. The test is made up of 4 Fill in the Blank, 27 Multiple Choice, 4 True or False, and 5 Short Answer questions.
The Test 3 Check List is now complete.
Assignment 3 is now available.
I have started to work on the Test 3 Check List and will advise once it is complete.
There will be no tutorial this week.
I have posted the solutions to Assignment 2 as well as the slides from our review.
I have finalized Test 2, and it is comprised as follows: 4 fill in the blank (4 points), 27 multiple choice (27 points), 4 true or false (4 points), and 3 problem/ short answer questions (15 points).
The Check List for Test 2 is now available.
The slide deck with some simple examples from the tutorials is here.
I have now published Assignment 2. Please note that the due date is 4 PM on 26 February, the day before Test 2. I have chosen this due date, so that I can review the solutions during the tutorial sessions that day. This gives you 11 days to do this assignment, which should be more than sufficient if you commit some daily effort to it. It will be important for test 2 that you know how to do the things on this assignment, so work on it early and be sure to gain these skills.
As discussed in class, there will not be a tutorial this week. Next week, the tutorial will focus on working through a number of reductions - the key skill we need to develop at this point in the course.
I have marked Assignment 1 and Test 1, and you should all have received a personalized email with your scores. If you did not get either email, please let me know.
With respect to Test 1, the scores were good and well distributed. View the histogram here.
The slides for the Tutorial sessions today, based on the questions posted so far, are here. I will likely update these during the sessions.
I promised a demo of TSP's intractability. Have a look at this program.
I have almost finished putting together test 1. It will be comprised of 3 fill in the blank (3 points), 26 multiple choice (26 points), 4 true or false (4 points), and 3 problem/short answer questions (17 points).
I have posted my solutions to Assignment 1 at this link. I will mark your assignments over the next week or so. Also, with respect to the test on 30 January, I have decided to limit its scope to Chapters 1 through 6 inclusive. The Test Checklist for this test is now finalized. A reminder again, that this is not a comprehensive checklist. Please read the preamble.
A number of you missed the lecture yesterday because of the snowstorm. I have had a request to cover the lecture again during the first tutorial session this Wednesday. Anyone who was unable to attend the class is welcome to attend that session.
Also, a reminder that we have an upcoming test on January 30. I will be publishing a list of what to know early next week. We will also use the tutorial time for January 29 as a review session for those who would like it.
I have decided how to deal with our scheduled tutorial time. Please have a look at the newly added Tutorial Guide page. I also clarified the requirements for the first question on Assignment 1.
I made a slight amendment to Assignment 1 (removing the first question). Apologies for any inconvenience.
Assignment 1 is now available. As you will see in the Course Schedule, it is due by 11:59 PM on Thursday January 23.
I corrected an error in the Grade Distribution. I am sure you are all comforted by this exhibition of my fine mathematical skills. :).
There will be no tutorials this week. We need to learn a bit of stuff first.
Please read this page with details applicable to all my courses.
This course introduces students to some of the fundamental ideas in theoretical computer science: functions and relations, formal languages, finite automata, regular languages, context-free grammars, context-free languages, push-down automata, pumping lemmas, Turing machines, the Church-Turing thesis, recursive and recursively enumerable languages, the Chomsky hierarchy, the halting problem and other unsolvable decision problems, problem reducibility, and fundamental computational complexity classes.
(These are at a high level, and put together with Bloom's Taxonomy in mind)
Understand and be able to explain what types of computations can be performed in theory and in practice.
Understand and be able to explain abstract computational models (such as Turing machines and finite automata), elementary notions of universality and undecidability, and their significance for practical computing.
Understand and be able to explain elementary notions of complexity theory, including complexity classes P, EXP, NP, and the concept of NP-completeness.
Be able to make rigorous mathematical arguments about computations.
CS 1073, CS 1303, and 30 ch.
Class meetings (lectures) will be on Tuesday and Thursday from 9:30 - 10:50 in Ganong Hall 215.
A set of tutorials will be held on certain Wednesdays, to be scheduled, from 16:00 - 16:50 for section 1 and 17:00 to 17:50 from section 2, in K.C.Irving Hall 104. Once scheduled, details will be the subject of an announcement and posted on the CS 2333 Course Schedule page.
All sessions will be in-person as a default.
Please consult the CS 2333 Course Schedule page for all specific scheduling details for this course, including:
Suggested reading relating to a specific meeting.
Topics to be covered at a class meeting.
Links to the slides.
The timing of tutorials.
The timing of the release of assignments and their due dates.
The dates for the three tests.
Please note that deliverable timing details and test dates are subject to change as a result of weather impacts on the class schedule or other intervening events.The Course Schedule page will be updated accordingly or as required. Please consult it often.
The textbook for this course is What Can Be Computed? A Practical Guide to the Theory of Computation, by John MacCormick. A digital version has been made available by our wonderful UNB librarians: https://unb.on.worldcat.org/oclc/1354949427 If you want a hard copy, the university bookstore will shortly have copies available: https://unb-saint-john.shoplightspeed.com/what-can-be-computed-a-practical-guide-to-the-theo.html
A free point to get you started (1 point)
Assignments (two at 9 points each, and one (the last one) at 15 points) for a total of 33 points)
In class tests (three at 22 points each, for a total of 66 points)
Note that there is no final exam.
The third assignment will be due on the last day of classes.
There will be 3 assignments. They will take some time to complete. Don't leave them to the last minute. Assignments will be posted on the course page on the date in the Course Schedule. Due dates are also posted there. Assignments must be submitted by email to the instructor no later than 11:59 p.m. on the day they are due. Please ensure you use a descriptive subject line for the email (for example: CS 2333 Assignment 1).
For the limited amount of coding in assignments etc, please use Python 3.x.
For most of the in class demos etc., I will use Jupyter Notebooks, a great free platform for editing and running Python. I recommend it for your use also.
There are a number of ways to implement/access Jupyter Notebooks. I recommend you use Google Colab (cloud based). You will need a Google account: https://colab.research.google.com/
For notebook storage, you can use GitHub or if you are using Colab, Google Drive.
All assignments must be done individually.
Three tests will be held in class on the dates set out on the Course Schedule page. Details of the structure of each test will be provided in advance of each test. Each test will cover a designated portion of the material. A study checklist will be provided for each test.