In the name of ALLAH, the most beneficient, the most merciful

Theory of Computation (CS701)

Handouts | Lectures | Contents | Books

Handouts / Power Point Slides

Lectures (video/audio/download)

Download Video Lectures

Watch Video Lectures

Download Audio Lectures

Course Contents

Introduction, Set Thoery, Sequences, Tuples, Functions, Relations, Graphs, Turing Machines, Enumerators, Dovetailing, The Church-Turing Thesis, Hilbert Tenth Problem, Decidable Languages, The Acceptance Problem for DFAs, The Halting Problem, Universal TM, Undicidability of the Halting Problem, Linear Bounded Automata, Computation Histories, Context Free Grammars, Russell Paradox, Emptiness Problem, Post Correspondence Problem, Computable Functions, Reducibility, Recursion Theorem, Logical Theories, Godels Theorem, Oracles, Turing Reducibility, A definition of Information, Incompressible Strings, Complexity Theory, Big Oh and Little Oh Notations, Time Complexity, Non-Deterministic Time, The Class P, The Class NP, Polynomial Time Verifiers, Subset Sum Problem, Satisfiability, NP-Completness, 3-Color Problem, The Cook-Levin Theorem, Independent Sets Problem, Clique, Vertex Cover, Hamiltonian Path Problem, The Subset Sum Problem, The Traveling Salesman Problem, Space Complexity, Relationship between Space and Time Complexity, PSPACE-Completeness, TQBF, Prove that TQBF is PSPACE-Complete, FORMULA-GAME, Generalized Geography, LOGSPACE Transducer, Prove the Theorem: NL = co-NL.

Recommended Books


Relevant Material

Course Codes

ACC311 ACC501 BIF401 BIF402 BIF601 BIF731 BIF732 BIF733 BIO101 BIO102 BIO201 BIO202 BIO203 BIO204 BIO301 BIO302 BIO303 BIO502 BIO731 BIO732 BIO734 BIT701 BIT703 BIT710 BIT715 BNK601 BNK603 BNK604 BNK610 BNK611 BNK612 BNK613 BNK701 BNK703 BNK704 BNK725 BT101 BT102 BT301 BT302 BT605 BT731 BT732 BT733 BT734 BT735 CS001 CS101 CS201 CS202 CS206 CS301 CS302 CS304 CS310 CS311 CS312 CS314 CS315 CS401 CS402 CS403 CS405 CS407 CS408 CS409 CS410 CS411 CS431 CS432 CS435 CS501 CS502 CS504 CS506 CS507 CS508 CS510 CS601 CS602 CS604 CS605 CS606 CS607 CS609 CS610 CS611 CS614 CS615 CS701 CS702 CS703 CS704 CS706 CS707 CS708 CS709 CS710 CS711 CS712 CS713 CS716 CS718 CS721 CS723 CS724 CS726 ECO302 ECO303 ECO401 ECO402 ECO403 ECO404 ECO406 ECO501 ECO601 ECO602 ECO603 ECO704 EDU101 EDU201 EDU301 EDU303 EDU304 EDU305 EDU401 EDU402 EDU403 EDU405 EDU410 EDU411 EDU430 EDU431 EDU501 EDU505 EDU510 EDU512 EDU515 EDU516 EDU601 EDU602 EDU603 EDU604 EDU654 EDU702 EDU705 ENG001 ENG101 ENG201 ENG301 ENG401 ETH201 ETH202 FIN611 FIN621 FIN622 FIN623 FIN624 FIN625 FIN630 FIN704 FIN711 FIN722 FIN723 FIN725 FIN730 GEN731 GSC101 GSC201 HRM611 HRM613 HRM617 HRM623 HRM624 HRM625 HRM626 HRM627 HRM628 HRM713 HRM724 HRM727 ISL201 IT430 MCD401 MCD402 MCD403 MCD501 MCD502 MCD504 MCM101 MCM301 MCM304 MCM310 MCM311 MCM401 MCM404 MCM411 MCM431 MCM501 MCM511 MCM514 MCM515 MCM516 MCM517 MCM520 MCM531 MCM532 MCM601 MCM604 MCM610 MGMT510 MGMT611 MGMT614 MGMT615 MGMT617 MGMT622 MGMT623 MGMT625 MGMT627 MGMT628 MGMT629 MGMT630 MGMT631 MGMT723 MGMT725 MGMT727 MGMT728 MGMT729 MGMT730 MGT101 MGT111 MGT201 MGT211 MGT301 MGT401 MGT402 MGT404 MGT411 MGT501 MGT502 MGT503 MGT504 MGT510 MGT513 MGT520 MGT522 MGT601 MGT602 MGT603 MGT604 MGT610 MGT611 MGT612 MGT613 MGT621 MGT703 MGT704 MGT705 MGT711 MGT713 MGT722 MKT501 MKT529 MKT530 MKT610 MKT611 MKT621 MKT624 MKT625 MKT627 MKT630 MKT703 MKT711 MKT721 MKT724 MKT725 MKT730 MKT731 MTH001 MTH100 MTH101 MTH201 MTH202 MTH301 MTH302 MTH303 MTH401 MTH403 MTH501 MTH601 MTH603 MTH701 MTH706 MTH721 PAK301 PAK302 PHY101 PHY301 PSC201 PSC401 PSY101 PSY401 PSY402 PSY403 PSY404 PSY405 PSY406 PSY407 PSY408 PSY409 PSY502 PSY504 PSY505 PSY510 PSY511 PSY512 PSY513 PSY514 PSY515 PSY610 PSY631 PSY632 SOC101 SOC401 SPT730 STA301 STA304 STA404 STA406 STA408 STA630 STA730 STAT730 URD101 ZOO731