First Term, Academic Year 2020/2021 M 416  - Theory of computation

Helwan University Faculty of science Math. Department

 

Course Description

This module introduces the theory of computation through a set of abstract machines that serve as models for computation - finite automata, pushdown automata, and Turing machines – and  examines the relationship between these automata and formal languages. Additional topics beyond the automata classes themselves include deterministic and nondeterministic machines, regular expressions, context free grammars, undecidability, and the P = NP question.

Course Objectives:

Finite automata are useful models for many important kinds of hardware and software. Here are the most important kinds: Software for designing and checking the behavior of digital circuits; The “lexical analyzer” of a typical complier, that is, the compiler component that breaks the input text into logical units, such as identifiers, keywords, and punctuation; Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns; Software for verifying systems of all types that have a finite number of distinct states, such as communication protocols or protocols for secure exchange of information.

 

Course Components

1.     Basic concepts and definitions; Set operations; partition of a set

2.     Equivalence relations; Properties on relation on set.

3.     Proving Equivalences about Sets.

4.     Central concepts of Automata Theory.

5.     Regular Expressions; Operations on Regular expressions

6.     Finite Automata and Regular Expressions.

7.     Conversion from FA and regular expressions.

8.     Deterministic Finite Automata (DFA); Minimization of DFA.

9.     Non-Deterministic Finite Automata (NDFA).

10.  Equivalence of Deterministic and Non-Deterministic Finite Automata.

11.  Equivalence between DFA,NFA, NFA-Λ

12.  Context-Free Grammars.

13.  Parse Trees; Ambiguity in Grammars and Languages.

14.  Standard Forms; Chomsky Normal Forms;

15.  Greibach normal Forms.

16.  Minimization of CFG’s.

17.  Pushdown Automata (PDA).

18.  Deterministic and Non-Deterministic (PDA); Formal definition of NPDA.

19.  Transition functions of NPDA; NPDA Execution.

20.  Accepting Strings with NPDA; Equivalence of PDAs and CFG.

21.  The Turing Machine.

22.  Programming Techniques for Turing Machines; Formal definition of TM’s.

23.  TM’s as acceptors; TM’s as transducers; Recognizing Languages with TM’s.; Sorting with

24.  TM’s.; Programming in TM’s.

25.  Multiple Tracks, Subroutines, Complexity issues and analysis

 

Text book:

Title: Introduction to Computer Theory

Author: Daniel I. A. Cohen

Publisher: Prentice-Hall, Second Edition, 1997.

 

In addition to the above, the students will be provided with handouts by the lecturer.

Recommended:

 

 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Second Edition, Prentice-Hall, 2001

 

Learning Outcomes:

Knowledge and understanding

- Acquire a full understanding and mentality of Automata Theory as the basis of all computer science

languages design

- Have a clear understanding of the Automata theory concepts such as RE's, DFA's, NFA's, Stack's,

Turing machines, and Grammars

 

Cognitive skills (thinking and analysis).

- Be able to design FAs, NFAs, Grammars, languages modelling, small compilers basics

- Be able to design sample automata

 

Communication skills (personal and academic).

- Be able to minimize FA's and Grammars of Context Free Languages

 

Practical and subject specific skills (Transferable Skills).

 

Evaluation Method:

Method	Percentage
Quizzes & Assignments	10%
Projects	10%
Mid Test	10%
Final Examination	70%

 

Course Topics

 

Week	Basic and support material to be covered	Slides	Homework
(1)	Basic concepts and definitions Set operations; partition of a set Equivalence relations; Properties on relation on set; Proving Equivalences about Sets. Central concepts of Automata Theory.	Lecture 1
(2)	Regular Expressions; Operations on Regular expressions Finite Automata and Regular Expressions. Recursive definitions; Conversion from FA and regular expressions; Kleen’s Theory; Mealy Moore Machines. Conversion from Mealy to Moore and vice versa.	Lecture 2a	Sheet 1
(3)	Deterministic Finite Automata (DFA). Minimization of DFA; Non-Deterministic Finite Automata (NDFA).	Lecture 2b
(4)	Equivalence of Deterministic and Non- Deterministic Finite Automata.	Lecture 3a	Sheet 2
(5)	Finite Automata with Epsilon-Transition. Equivalence between DFA,NFA, NFA-Λ	Lecture 3b	Assignment 1
(6)	Pumping Lemma for Regular Languages. Closure Properties of Regular Languages.	Lecture 4	Sheet 3
(7)	Context-Free Grammars; Regular Grammars; Parse Trees.	Lecture 5
(8)	Ambiguity in Grammars and Languages. Standard Forms; Chomsky Normal Forms; Greibach normal Forms.	Lecture 6	Sheet 4
(9)	Pumping Lemma for Context-Free Languages; Closure Properties of Context-Free Languages; Minimization of CFG’s.	Lecture 7
(10)	Pushdown Automata (PDA).	Lecture 8	Sheet 5
(11)	Deterministic and Non-Deterministic (PDA); Formal definition of NPDA. Transition functions of NPDA; NPDA Execution; Accepting Strings with NPDA; Equivalence of PDAs and CFG.	Lecture 9
(12)	The Turing Machine.	Lecture 10	Sheet 6
(13)	Programming Techniques for Turing Machines; Formal definition of TM’s. TM’s as acceptors; TM’s as transducers; Recognizing Languages with TM’s.; Sorting with TM’s.; Programming in TM’s	Lecture 11
(14)	Multiple Tracks, Subroutines, Complexity issues and analysis	Lecture 12	Sheet 7
(15) Specimen examination (Optional)	Equivalence of PDA’s and CFG.	Lecture 13
(16) Final Examination	Revision

 

 

First Term, Academic Year 2020/2021 M 418  - Computer Networks

Helwan University Faculty of science Math. Department

 

  Computer Networks  - M 418 

 

Course Description

This  course  presents  an  overview  of  the  technology,  architecture  and  software  used  by  systems  of network   connected   computers.   The   course   will   cover   data   transmission,   local   area  network architecture, network protocols, inter-networking and distributed systems.

Course Objective

After completing this course the student must demonstrate the knowledge and ability to:

1. Independently understand basic computer network technology.
2. Understand and explain Data Communications System and its components.
3. Identify the different types of network topologies and protocols.
4. Enumerate the layers of the OSI model and TCP/IP. Explain the function(s) of each layer.
5. Identify the different types of network devices and their functions within a network
6. Understand and building the skills of sub-netting and routing mechanisms.
7. Familiarity with the basic protocols of computer networks, and how they can be used to assist in network design and implementation.

References

Required:

1.     TB1:  Olivier Bonaventure. Computer Networking: Principles, Protocols and Practice Release 0.25. The Saylor Foundation.

2.     TB2: Douglas E. Comer. Computer Networks and Internets, with Internet Applications (5th edition). Prentice Hall.

 

Recommended:

Andrew S. Tanenbaum (2010). Computer Networks (5^th edition). Prentice Hall.

Prerequisite: None

Evaluation Method:

Method	Percentage
Quizzes & Assignments	10%
Projects	10%
Mid Test	10%
Final Examination	70%

 

Course Topics

Week	Topic Name	Sub Topic	Chapter
1,2	Communicating over the Network	• The structure of a network, including devices and media necessary for communications     • The advantages of using a layered model to describe network functionality     • The role of each layer in the OSI network model and the TCP/IP network model	TB2: Chapters 5&7
3.4	Application Layer Functionality and Protocols	• The functions of the three upper OSI model layers provide network services to end-user applications     • OSI and TCP/IP application layer protocols The functions of well-known TCP/IP applications, such as the World Wide Web   and   e-mail,   and   their   related services      (HTTP,      DNS,      DHCP, STMP/POP, and Telnet)	TB1: Chapters  3
5	OSI Transport Layer	·The role of the transport layer as it provides the end-to-end transfer of data between applications     ·The role of two TCP/IP transport layer protocols: TCP and UDP	TB1: Chapter 4
		Mid  Exam
7	OSI Network Layer	•        The method described by the network layer for routing packets     •        the Internet Protocol (IP)     •        How do routers use next- hop addresses to select a path for packets to reach their destination?     •        How do routers forward packets?	TB1: Chapter 5
8&9	OSI Data Link Layer	•        The role of data link layer protocols in data transmission     •        How does the data link layer prepare data for transmission on network media?     •        How do the types of MAC methods operate?     •        What is the purpose of encapsulating packets into frames to facilitate media access?	TB1: Chapter 6
10	OSI Physical Layer	•        Role do the physical layer protocols     •        What is the purpose of physical layer signaling and encoding used in networks?     •        What are the basic characteristics of copper, fiber, and wireless network media?     •        What are common implementations of copper, fiber, and wireless media in networks?	TB1: Chapter 6
11	Ethernet	•        How did Ethernet evolve?     •        What are the purposes of the fields of the Ethernet frame?     •        The function and characteristics of the media access control method.	TB1: Chapter  6
		Review
13	Ethernet	•        What are the physical and data link layer features of Ethernet?     •        How are Ethernet hubs and switches different?     •        What is the purpose of Address Resolution Protocol (ARP) and how does it operate?	TB1: Chapter 6
14	Addressing the Network: IPv4	•        What type of addressing structure does IPv4 use? What type of address is a given IPv4 address, and how is it used in a network?   How do administrators assign addresses –within networks?   How are addresses assigned by ISPs?   What is the network portion of the host address?   What is the role of the subnet mask in dividing networks?	TB2: Chapters 21&24
15		Final Exam

 

 

Course Slides and assignments

 

Weeks	Topic Name	Slides	Assignments
1,2	Communicating over the Network	• Lecture 1     • Lecture 2	Sheet1
3.4	Application Layer Functionality and Protocols	•       lecture 3     •       Lecture4	Sheet2
5	OSI Transport Layer	• lecture 5
7	OSI Network Layer	• lecture 6	Sheet3
8&9	OSI Data Link Layer	•       lecture 7	Sheet4
10	OSI Physical Layer	•       lecture 8
11	Ethernet	•       lecture 9
13	Ethernet	•       lecture 9	Sheet5
14	Addressing     the Network: IPv4	•    lecture 10
15		Final Exam