CS-C2150 - Theoretical Computer Science, 08.01.2019-10.04.2019
This course space end date is set to 10.04.2019 Search Courses: CS-C2150
Översikt
-
Compulsory course of the Computer Science and Engineering major.
Credits: 5
Level: Bachelor
Teacher: Prof. Pekka Orponen (professor responsible for the course)
Teaching Period: III - IV (Spring). The Course starts on Tuesday 08.01.2019, 10:15 - 12:00, T1 / C202 Tietotekniikka
Schedule:
- Lectures: Tuesdays 10:15 - 12:00
- Exercise sessions (starting Jan 14, 2019):
- Mondays 14:15 - 16:00 TU5 / 1194 TUAS Maarintie 8
- Tuesdays 16:15 - 18:00 T6 / A136 Tietotekniikka
- Wednesdays 10:15 - 12:00 T6 / A136 Tietotekniikka
- Thursdays 12:15 - 14:00 T6 / A136 Tietotekniikka
- Fridays 10:15 - 12:00 T5 / A133 Tietotekniikka
Workload:
- Lectures: 24h (2 hour lectures, once a week)
- Exercises in small groups
- Independent work
- Exam: 3h
Learning Outcomes: Theoretical computer science comprises the science of computation, and the science of software. Science is knowledge that helps us make predictions. The stronger the science, the stronger the predictions. The science of computation tells us what is computation, what are the different types of computing machines, and what are their computing powers. Using this science, we can predict (indeed, prove!) that some computational problems are easy, some are hard, and some are impossible to solve! The science of software allows us to make predictions about the programs that we write: will my program always terminate? might it crash? will it always produce the right result? etc. In this course you will learn the basic models of computation (finite automata, regular expressions, context-free grammars, Turing machines). You will solve a set of computerized assignments where you will build such computing machines and answer fun questions about them.
Content: Finite automata and regular languages. Context-free grammars and pushdown automata. Turing machines and computability.
Assessment Methods and Criteria: Exam, computerized assignments, and home assignments
Study Material: Lecture notes and slides; Textbook (recommended but not obligatory) Michael Sipser, Introduction to the Theory of Computation; and other separately announced study material
Substitutes for Courses: ICS-C2000 Theoretical Computer Science, T-79.1001 Introduction to Theoretical Computer Science T (4 cr), T-79.1002 Introduction to Theoretical Computer Science Y (2 cr)
Prerequisites: CS-A1110 / CSE-A1110 Programming 1 and CS-A1120 / ICS-A1120 Programming 2 or CS-A1111 / CSE-A1111 Basic Course in Programming Y1 and CS-A1121 / CSE-A1121 Basic Course in Programming Y2, MS-A0401/A0402/A0409 Foundations of discrete mathematics.
Grading Scale: 0-5
Language: English
Lecturer: Prof. Pekka Orponen
- Lectures: Tuesdays 10:15 - 12:00
-
-
-
-
This is your personal computerised assignments homepage. You must complete all the obligatory problem sets before participating in an exam of the course CS-C2150 Theoretical Computer Science. Otherwise your exam will not be graded. You cannot pass the course if you do not complete the compulsory computerised assignment problems assigned to you. The voluntary problems are not mandatory: it is recommended that you do them for your own benefit: for practice and fun!
Do not wait until the last minute to do the computerized assignments. The sooner you start the better. The more of these exercises you do now, the easier the rest of the course will be. Start now!
General Information
- Home assignments are automatically and personally generated for each student; everyone has their own assignments. In the case of assignments with verbal problem descriptions there will be some overlap. In fact, since the problems are generated independently of each other, it may sometimes happen that even the same person may get exactly the same problem twice. In this case just consider yourself lucky and submit the same solution twice.
- The submitted solutions are validated by the system automatically. When your solution has been checked, the system informs you by marking your solution as either correct or incorrect. In the latter case, the system also provides you with some feedback on why your solution is incorrect.
- You may resubmit solutions to each problem for a few number of times; when this upper limit is reached, the system automatically generates a new problem of the same type for you.
- Note: if you exceed the number of tries allowed for a problem, you
will get a new problem. You might need to refresh your browser (reload
the page) in that case, to get rid of cached information that your
browser stores, like previous solution attempts.
Honour Code
- You are expected to solve your assignments and submit the solutions personally. If you encounter problems, you are welcome to discuss the assignments with your fellow students and the course personnel. However, you should not make direct notes of these discussions, such that all you would need to do at the terminal is to copy the solution from the notes to the system input.
Troubleshooting
If you have problems with the computerized assignments, you can consult the course personnel as follows:- For general "how does this work" and "what does this mean" questions, you can ask the lecturer during the lecture breaks or consult the assistants on the tutorials.
- If you think you have encountered a technical problem or a bug in the assignment system,
please send email to markku.riekkinen
@aalto.fi and CC the course instructor ASAP. Provide a detailed description of the sequence of steps that causes the problem, as well as a screen-shot if possible. Please mention your student number in the message. Make sure you can reproduce the problem yourself: refresh your browser and repeat the steps to make sure the problem appears again.