Section outline

  • Welcome to the Theory of Computing course.

    Collapse all Expand all

    CSE221: Theory of Computing


    Course Information:
    Course Code: CSE 221
    Course Title: Theory of Computing
    Program: B.Sc in Computer Science and Engineering (CSE)
    Faculty: Faculty of Science and Information Technology (FSIT)
    Semester: Fall
    Year: 2022
    Credit: 3.0
    Contact Hour: 6 Hours/ Week
    Course Category: Core Engineering
    Section: A+B


    Course Teacher Information:
    Rashidul Hasan Hridoy
    Lecturer, Department of Computer Science and Engineering
    Daffodil International University
    Office: Academic Building 04, Room 739
    Mobile: 01714969317
    Email: rashidul.cse0394.c@diu.edu.bd
    LinkedIn: https://www.linkedin.com/in/rashidulhasanhridoy
    ResearchGate: https://www.researchgate.net/profile/Rashidul-Hasan-Hridoy
    Google Scholar: https://scholar.google.com/citations?user=9o4uHPsAAAAJ&hl
    Website: https://rashidulhasanhridoy.com


    Course Rationale:

    The course is intended to teach the students the basic techniques that underlie the practice of Compiler Construction. The course will introduce the theory and tools that can be standard employed in order to perform syntax-directed translation of a high-level programming language into an executable code.These techniques can also be employed in wider areas of application, whenever we need a syntax-directed analysis of symbolic expressions and languages and their translation into a lower-level description. They have multiple applications for man-machine interaction, including verification and program analysis.


    Course Objective:

    The main objective of this course is to introduce the major concept areas of language translation and compiler design and to develop an awareness of the function and complexity of modern compilers. This course is a study of the theory and practice required for the design and implementation of interpreters and compilers for programming languages.


    Course Outcomes (CO’s):   

    After successful completion of this course, the students should be able to,

    • CO1 :Able to learn variety of issues in the mathematical development of computer science theory, particularly finite representations for languages and machines.
    • CO2 : Efficient problem can be solved on a model of computation.
    • CO3 :  Apply relation and function to solve a problem of NFA & DFA.
    • CO4 : The model Turing Machine is implemented to analyse and use to prove result.
    • CO5 : Be able to construct pushdown automata and the equivalent context free grammars.


    Grading Scheme (Theory Class):

    • Attendance: 7%
    • Class Tests/Quizzes: 15%
    • Assignment: 5%
    • Presentation (using video/ppt): 8%
    • Midterm Exam: 25%
    • Final Exam: 40%


  • Week 1

    Topics of discussion

    • What is theory of computing?
    • Contribution of theory of computing to computer science.
    • Importance of theory of computing in computer science.
    • Basic terminologies of theory of computing.
    • Research opportunities in theory of computing.


    Expected Learning Outcome
    Students will get a small introduction to theory of computing, and also learn its usage and importance. 

    • assign icon
      Week 1 Assignment
      Opened: Monday, 15 August 2022, 12:00 AM
      Due: Monday, 10 October 2022, 12:00 AM
      Students must
      Mark as done

  • Week 2 : Introduction

    Discussion Topics: 

    • Strings, Alphabets and Language
    • Graphs and Trees
    • Set Notation 
    • Relations

    Expected Learning Outcomes:

    • Basic Concept.
    • How to make relation among the symbols

    • folder icon
      Supporting study materials Folder
      Students must
      Mark as done
    • assign icon
      Week 2 Assignment
      Opened: Wednesday, 14 September 2022, 12:00 AM
      Due: Monday, 10 October 2022, 12:00 AM
      Students must
      Mark as done

  • Week 3 : Finite State Systems

    Discussion Topics: 

    • Finite State Systems
    • Basic Definitions / Finite Automata 
    • Nondeterministic Finite Automata

    Expected Learning Outcomes:

    • How to design a DFA and NFA
    • Create Transition Table

    • folder icon
      Supporting study materials Folder
      Students must
      Mark as done
    • assign icon
      Week 3 Assignment
      Opened: Wednesday, 14 September 2022, 12:00 AM
      Due: Monday, 10 October 2022, 12:00 AM
      Students must
      Mark as done

  • Week 4 : Conversion of DFA and NFA

    Discussion Topics: 

    • Conversion of DFA and NFA
    • The Equivalence of DFA’S and NFA’S
    •  Finite Automata with Epsilon-Moves
    •  Discuss about Quiz Test.

    Expected Learning Outcomes:

    • Know the difference between NFA and DFA
    • How to convert NFA to DFA

    • folder icon
      Supporting study materials Folder
      Students must
      Mark as done
    • assign icon
      Week 4 Assignment
      Opened: Wednesday, 14 September 2022, 12:00 AM
      Due: Saturday, 15 October 2022, 12:00 AM
      Students must
      Mark as done

  • Week 5 : Review Class and Quiz

    Quiz 1 and Solve Class


    Quiz Syllabus: Week 1, Week 2, Week 3 and Week 4
    Date: Friday, 9 September 2022
    Time: 35 Minute
    Platform: BLC



    • quiz icon
      Quiz - 1
      Opened: Friday, 9 September 2022, 12:00 PM
      Closed: Friday, 9 September 2022, 12:45 PM
      Students must
      Mark as done
    • assign icon
      Week 4 - Assignment
      Opened: Friday, 9 September 2022, 12:00 AM
      Due: Friday, 16 September 2022, 12:00 AM
      Students must
      Mark as done

  • Week 6 : Regular Expression

    Discussion Topics: 

    • Regular Expressions
    • Finite Automata and Regular Expressions
    • Applications of  Regular Expressions
    • Algebraic Laws for Regular Expressions

    Expected Learning Outcomes:

    • How to implement regular expression and language.
    • How to implement the Algebraic Laws for Regular Expressions.

    • folder icon
      Supporting study materials Folder
      Students must
      Mark as done
    • assign icon
      Week 6 - Assignment
      Opened: Wednesday, 14 September 2022, 12:00 AM
      Due: Monday, 10 October 2022, 12:00 AM
      Students must
      Mark as done

  • Week 7 : Context Free Grammar

    Discussion Topics:
    • Simplification of Context-Free Grammars(Useless Symbols)
    • Derivation Left and Right most derivation

    Expected Learning Outcomes:
    • About some normal form Build the normal for

    • folder icon
      Supporting study materials Folder
      Students must
      Mark as done
    • assign icon
      Week 7 Assignment
      Opened: Wednesday, 14 September 2022, 12:00 AM
      Due: Monday, 10 October 2022, 12:00 AM
      Students must
      Mark as done

  • Week 8 : Review Class and Quiz

    Review Class : All previous weeks


    Quiz Syllabus: Week 3, Week 4, Week 5 and Week 6
    Date: 7 October, 2022
    Time: 12.00 PM
    Platform: BLC


    Submission File Name Format: Q2_CSE221_ID.pdf (Example: Q2_CSE221_221-15-1275.pdf) 


  • Week 9 : Midterm Examination

    Syllabus: Week 1 to Week 8
    The exam date and time will be notified shortly.

  • Week 10 : Left Recursion and Left Factoring

    Discussion Topics: 

    • Discuss and illustrate the rules for eliminating Left Recursion.
    • Discuss the techniques to do Left Factoring.

    Expected Learning Outcomes:

    • Eliminating Left Recursion
    • Construct Left Factoring

  • Week 11 & 12: LR0 Parser and Canonical Table

    Discussion Topics: 

    • Discuss and illustrate Kernel item, Non Kernel Item.
    • Discuss about Augmented grammar.
    • Discuss about Canonical Table.

    Expected Learning Outcomes:

    • Recognize kernel and non-kernel item.
    • Construct LR 0 Parser.
    • Design and construct canonical table.

  • Week 13 : Code Optimization

    Discussion Topics: 

    • Discuss about Machine independent code optimization.
    • Discuss and illustrate the techniques of code optimization.

    Expected Learning Outcomes:

    • Recognize machine independent code.
    • Able to apply techniques to optimize codes.


  • Week 14 : Presentation & Assignment

    Presentation topics will be provided after the midterm examination. Before that, you need to make a group of 3 people and submit the group list within Week 9.

    Assignment topics will be provided after week 11, you have to attend a viva and submit a short report on your assignment.

    • assign icon
      Assignment Submission
      Opened: Thursday, 1 December 2022, 12:00 AM
      Due: Tuesday, 20 December 2022, 12:00 AM
      Students must
      Mark as done

  • Week 15 : Review Class and Quiz 3

    Review Class : All previous weeks after midterm examination

    Quiz 3


    Date: 25-11-2022
    Time: 12 PM to 1 PM
    Platform: BLC


    Submission File Name Format: Q3_CSE221_ID.pdf (Example: Q3_CSE221_221-15-1275.pdf) 


    Copying answers from others is strictly prohibited.


  • Week 16 : Final Examination

    Syllabus: TBA
    The exam date and time will be notified shortly.