CMSC 208: Grammars, Languages, Automata
(Spring 2017)


MWF 3 - 3:50 pm Ruffner 350


Course Information Handout/Syllabus

Academic Honesty in Programming
Linz text
Instructor:
Scott McElfresh
x2249       Ruffner 346
ProfScottMcElfresh @ gmail.com
Website

Office Hours:
(no appointment needed,
just drop by during these times)


yellow divider
Calendar

Mon, Jan 16

MLK Holiday
Tue, Jan 17

Wed, Jan 18

Topics:
  • Introduction
  • Sets review
Inclass work:
Assigned:
  • Continue work on Wed review exercise for Friday
  • Watch these videos for review
  • Review HW (due Mon, Jan 23, beginning of class)   Do NOT print this on two pages and squeeze all of the answers into the space provided.   You will need more space, so use additional pages.
Thu, Jan 19

Fri, Jan 20
DUE:  Inclass review exercise (not to be handed in, but checked for preparedness)

Topics:
  • Sets
  • Logic
yellow divider
Mon, Jan 23
DUE: Review HW

Topics:
  • Proofs
Assigned:
Tue, Jan 24

OPTIONAL:
Computer Science internship presentations
3:30pm
Ruffner 356
Wed, Jan 25

Topics:
  • induction
Thu, Jan 26

OPTIONAL:
Computer Science internship presentations
3:30pm
Ruffner 356
Fri, Jan 27

Topics:
  • induction
Assigned:
  • induction exercise
  • Do as much of this exercise as possible by the start of class on Monday.
yellow divider
Mon, Jan 30
DUE:  the induction exercise for inclass presentation and discussion

Topics:
  • induction
Tue, Jan 31

Wed, Feb 1

class cancelled due to instructor illness

Assigned via email:
  • Read about Racket. You only need to read about half of the page until you see the heading "Complex Data Types: Structs"
Thu, Feb 2

Fri, Feb 3

QUIZ

Topics:
  • Intro to functional programming languages
yellow divider
Mon, Feb 6

Topics:
  • working with Racket


Tue, Feb 7

Wed, Feb 8

Topics:
  • structural induction
  • lists in Racket
Resources:
Thu, Feb 9

Fri, Feb 10

Topics:
  • strings and sequences
Assigned:
For Monday:
  • Read section 1.2 of the Linz text on "Three Basic Concepts" 
  • Look at exercises 1-13 at the end of section 1.2 (on pages 27 and 28). Come to class on Friday with the following on paper:
    • a list of the exercises that you understand the question (but may not know how to solve) 
    • a list of the exercises that you do not understand the question at this time 
  • Read section 2.1 of the text. Come to class on Friday with 3 questions about this reading on paper.
For Fri, Feb 17
yellow divider
Mon, Feb 13

class cancelled

Assigned via email:
  • Read Section 2.1 of the text on DFAs. Consider the following problems on pages 47 and 48: 2, 5a and b, 7a and b, 9, 11, 12. Work on understanding the question, and for each write down at most two sentences as to how you might approach the problem. (not asking for an actual solution yet) This will be handed in on Wed.
  • Get the JFLAP software. It is on the CD that comes with the textbook, but you can also download it for free from this site. I am using the version May 15, 2011 - JFLAP Version 7. http://www.jflap.org/ Explore what you are able to do after you click on the Finite Automaton button. Try to create one of the pictures from the reading in Section 2.1.
Tue, Feb 14

Wed, Feb 15

Topics:
  • DFAs
  • the JFLAP software
Assigned:
The following problems:
2 (all parts), 5 (a, b, and c) and 7 (a, b, and c)
Thu, Feb 16

Fri, Feb 17
DUE: beginning of class:  Racket HW  (postponed until Mon, Feb 20)

Topics:
  • more DFA examples
  • regular languages

Assigned (Due Monday)
Problems  9 (all parts), 11, and 12
yellow divider
Mon, Feb 20
DUE:  
  • Racket HW
  • Problems 9, 11, and 12 from the book


Tue, Feb 21

Wed, Feb 22

In-class exam
Thu, Feb 23

Fri, Feb 24

Topics:

Assigned:  due Monday, Feb 27 beginning of class
  • using JFlap
    • Use JFlap to create an automaton for 9d on page 48.
    • Create a text file with at least 20 reasonable test cases for your automaton.
    • Hand these in to Canvas.
  • Non-determinism
    • Read section 2.2 of the text
    • Consider Problems 4-12 on page 55.  Be prepared to discuss the questions,even if you don't know how to do solve them yet.
yellow divider
Mon, Feb 27
DUE:
  • JFlap and text file
  • Reading on non-determinism
Topics:
  • Non-determinism

Assigned (due Wed):
Problems 4-15 on page 55.  (written solutions to hand in)
Tue, Feb 28

Wed, March 1

Topics:
  • Non-determinism
Thu, March 2

Fri, March 3

Topics:
  • NP-completeness and optimization problems
yellow divider
Mon, March 6  - Friday, March 10

Spring Break

yellow divider
Mon, March 13

Topics:
  • introduction to regular expressions
Assigned:
  • Read Section 3.1 of the text
  • Look at problems 1-18.
  • To hand in on Wed, March 15.
    • Problem 5 on page 75 of the book.
    • Problems 13 and 14 on page 76
    • Problem 16 parts a, b, and c on page 76
    • Problem 17 parts a-e on page 76.
    • THIS MAY BE DONE IN PAIRS.  Turn in only one copy per pair.
Tue, March 14

Wed, March 15
Due:  Problems from section 3.1

Topics:
  • working with regular expressions

Due:  Fri, March 24 3pm
Thu, March 16


4pm:  Ruffner 356
Colloquium:  STEM careers at NSA
Fri, March 17

Topics:
  • quiz on regular expressions
yellow divider
Mon, March 20

Topics:
  • quiz on regular expressions
Assigned: for Wed
  • Read section 3.3 of the text
  • Be prepared to discuss exercises 1-10 on pages 96-97
Tue, March 21

Wed, March 22
Due: reading from Monday

Topics:
  • regular grammars
Thu, March 23

Fri, March 24
DUE: Simulate Automata 3pm

Topics:
  • intro to Lex and Yacc
yellow divider
Mon, March 27

Topics:
  • more with Grammars (including Context Free)
Assigned:
  • Read  sections 4.3 and 5.1 for Wednesday
Tue, March 28

Wed, March 29
DUE: read sections 4.3 and 5.1

Topics:
  • Pumping Lemma
Assigned for Fri:
  • Read 5.1
  • do problems 7a, 7b, 7c, 7d, 8a, 8c, 9, 19
Thu, March 30

Fri, March 31

Topics:
  • grammars
  • Context Free Languages
yellow divider
Mon, April 3

Topics:
  • Pushdown automata
Assigned for Wed:
  • Read section 7.1
  • Do problems 4a, 4b, 4c, 4d on page 183
Tue, April 4

Wed, April 5
Due:  problems 4a, 4b, 4c, 4d on page 183

Topics:
  • pushdown
Thu, April 6

Fri, April 7

In-class exam
yellow divider
Mon, April 10

Topics:
  • Intro to Turing Machines
Assigned for Wed:
  • Read about Alan Turing (eg  wikipedia)
  • Read section 9.1 of the text
  • Download the following files.  (You may need to right-click to save the link.)
    • Open them in JFlap and run them on different outputs.  Observe the behavior.
  • Be prepared to discuss problems 2,5,6,7,8, 9 starting on page 238.  
    • Be sure you understand what the question is asking (even if you don't know how to solve it).
Tue, April 11

Wed, April 12
DUE: assignment from Mon

Topics:
  • Turing Machines
Assigned for Friday:
  • Come to class with attempts at these problems on pgs 238 and 239:
  • 7e, 7f, 7g, 7h
  • 9
  • 11 a, b, c, d, e
Thu, April 13

Fri, April 14
due: problems assigned on Wed

Topics:
  • Group work on Turing Machines
yellow divider
Mon, April 17

Topics:
  • More examples with Turing Machines
Tue, April 18

Wed, April 19

Assigned:
Thu, April 20

Fri, April 21

Topics:
yellow divider
Mon, April 24
Due:  3pm:  Turing Machines hw
Topics:
Tue, April 25

Wed, April 26

Student Showcase Day

NO CLASS
Thu, April 27

Fri, April 28

Topics:
yellow divider
Mon, May 1

Topics:
Tue, May 2

Wed, May 3

READING DAY

NO CLASS
Thu, May 4

Fri, May 5

Final Exam
11:30-2pm
Details TBA

yellow divider
Mon, May 8


Tue, May 9

Wed, May 10


Thu, May 11

Fri, May 12


yellow divider