CENG 512
Advanced Theory of Computation
This course will begin by explaining the different models of computation. It will then address the Church-Turing thesis. The course also will cover the topics of decidability and reducibility. Finally, detailed information is provided about complexity and related concepts.
| Topics |
| Introduction and Overview |
| Math Review |
| Finite Automata and Regular Languages |
| Context-Free Languages and Pushdown Automata |
| Turing Machines and the Church-Turing Thesis |
| Decidability |
| Catch-up and review |
| Reducibility |
| Time complexity, P, and NP |
| NP-completeness |
| Catch-up and review |
| Space complexity |
| Randomization |
| Parallel complexity |
Other MS Courses
- CENG 500
- CENG 501
- CENG 502
- CENG 503
- CENG 504
- CENG 505
- CENG 506
- CENG 507
- CENG 508
- CENG 509
- CENG 511
- CENG 513
- CENG 514
- CENG 515
- CENG 516
- CENG 517
- CENG 518
- CENG 521
- CENG 522
- CENG 523
- CENG 524
- CENG 525
- CENG 531
- CENG 532
- CENG 533
- CENG 534
- CENG 541
- CENG 542
- CENG 543
- CENG 544
- CENG 551
- CENG 552
- CENG 555
- CENG 556
- CENG 557
- CENG 561
- CENG 562
- CENG 563
- CENG 564
- CENG 565
- CENG 566
- CENG 590
- CENG 608
- CENG 611
- CENG 612
- CENG 613
- CENG 631
- CENG 632
- CENG 641
- CENG 642
- CENG 643
- CENG 651
- CENG 661
- CENG 662
- CENG 663