A course on computation, computability, and complexity.
Message Of The Day
12/16 Last Rites
The final exam will be held in Metcalf Research room 129 on Thursday from 2:00-5:00 PM.
12/3 Homework 11
Homework 11 has been posted, and so have lab assignments for this week.
11/24 Homework 10, etc.
Homework 10 has been posted. Labs are not mandatory this week; however we will be holding labs from 5-7 on Sunday Nov. 30 and 5-7 on Monday Dec. 1. Email Sarah with your preference if you plan on going and she'll assign you a problem. Also there will be a make up lecture on Friday December 5th same time same place because class was cancelled on 11/10.
11/12 Take-home midterm out
Midterm 2 is out and is due before class on Wednesday Nov 19th. There is no regular homework or labs this week.
11/5 Homework 9
Homework 9 has been posted, and so have lab assignments for this week.
10/29 Homework 8
Homework 8 has been posted, and so have lab assignments for this week.
10/28 Midterm 1 Solution Online
Anna's midterm is online in the assignments tab.
10/22 Homework 7
Homework 7 has been posted, and so have lab assignments for this week.
10/20 Old Midterm Online
2007's Midterm 1 is online in the assignments tab along with the solution. Note that last year the exam was earlier in the semester, before we had a chance to cover reductions in as much depth and before we had covered CFGs.
10/8 Homework 6
Homework 6 has been corrected since it was posted this morning, and lab assignments for Columbus Day weekend have been posted. Please check to make sure you have been assigned to a lab that you can make.
10/1 Homework 5
Homework 5 and its lab assignments have been posted. Problem numbers have changed once again, so please check your section and problem number.
10/1 Midterm 2 moved to October 21st 7-9PM
Due to a conflict with CS31, the midterm has been moved to Tuesday, October 21st from 7-9PM. If you have a conflict, please email the TAs right away!
9/24 Homework 4
Homework 4 and its lab assignments have been posted. Once again, problem numbers have changed from last week.
9/17 Homework 3
Homework 3 has been posted, as have the lab assignments for it. Note that problem numbers have once again changed from last week.
9/10 Homework 2 Problems and Labs
Homework 2 has been modified to clarify the definitions of difference and exclusive or. Also, the lab assignments for homework 2 are up. Note that you may not be assigned the same problem as last week.
9/3 Lab Assignments Posted
The lab assignments are up!
8/30 Time and Space
Class will be on Mondays and Wednesdays from 9:30 to 10:50 AM in CIT 368.
8/27 Welcome to Models of Computation!
CSCI0510 (also known as CS51) is a core undergraduate Computer Science course on the foundations of computing. A variety of formal models for machines and languages are explored including machines with memory (the finite-state, random-access and Turing machines), language models (regular expressions and formal languages) and complexity classes identifying problems with the same general complexity, such as the NP-complete problems. In particular the course covers one of the great mathematical theorems of the 20th century, the halting problem, and what (we hope) will be one of the great mathematical theorems of the 21st century, P != NP.
The course has lectures, written assignments, labs, and exams. Its prerequisite is CSCI220, Introduction to Discrete Mathematics. CSCI510 serves as a prerequisite for higher level CS classes.