Assignments - Computational Thinking

Note: All assignments (unless otherwise noted) should be submitted in PDF form to the instructors email address no later than the time and date indicated for each assignment.

1. Definitions of Computer Science
Assigned: January 18 Due: January 20 (10AM)
Points: 5 Done by: individual
Assignment: Find other definitions of computer science and compare them to the class definition. Be prepared to discuss at next class meeting the differences and similarities that you find. Submit a PDF document with two or more other definitions of computer science and a list of at least four points of comparison with the working class definition.

2. Modeling State and Behavior
Assigned: January 20 Due: January 27 (10 AM)
Points: 15 Done by: two person team
Assignment:  Find artifacts or systems in real world to model and model them using finite state machine diagrams. Submit answers for at least two artifacts or systems. For each artifact or system, give a written description of the artifact or system being modeled and the corresponding finite state machine diagrem.
Optional question: Who are Mealy and Moore and what do they have to do with finite state machines?

3. Information Structure, Acceptors
Assigned: January 27 Due: February 1 (10AM)
Points: 10 Done by: individual
Assignment:  Use JFLAP to develop an acceptor for genes using the rules defined in our class notes for Acceptors. Test your acceptor on the gene available on our Class Notes page.  Submit (1) a document with a screen shot of your completed gene acceptor, and (2) the .jff file produced by JFLAP

4. Grammars
Assigned: February 1 Due: February 3 (10AM)
Points: 10 Done by: individual
Assignment:  Use ANTLRWorks to develop a grammar for US currency according to the following description. Submit the .g file produced by ANTLRWorks.

A string of symbols representing an amount of US currency begins with a dollar sign (“$”) and has exactly two digits, denoting cents, after the decimal point. Commas are used in the digits representing the dollars as follows:  there are always three digits between successive commas and between a comma and the decimal point;  commas are required to limit the number of successive digits to no more than three.  For example, $1,234.56, $1,234,567.89, $2.35 are valid dollar amounts while $2.3, $2,34.54, and $34567.25 are not valid. Finally, the first digit in the digits representing the dollars cannot be a zero except if it immediately precedes the decimal point. For example, $0,123.45 and $09.24 are not valid but $0.12 is valid.

5. Abstraction
Assigned: February 3 Due: February 8 (10AM)
Points: 15 Done by: two person team
Assignment:  Identify and briefly describe two different real-world objects. For each object define three different points of view related to that object. For each perspective define at least three items of information that are relevant to the object for the given point of view. Submit a PDF document with you answers. Be sure to identify both members of the team and follow the submission etiquette.

6. Instances and Types
Assigned: February10 Due: February 15 (10AM)
Points: 20 Done by: two person team

(7 points) Part 1: creating instances of an abstraction. Represent in XML four concrete instances of an abstraction of an inventory of automobiles from the point of view of a car salesman. Your abstraction must include at least four elements, one of which is an ennumerated value, one that is a string, one that is a whole number, and one that is a decimal number. An ennumerate value is like the "Genre" values in the "book catalog" example that we studied. Submit the .xml file produced by XMLSpear. Be sure to include comments that identify the team members.

(8 points) Part 2: defining the abstraction. Use BNF or EBNF to describe the "language of automobiles". In other words, write an E/BNF description of the XML markup used to represent concrete automobiles as developed in your answer in part 1.
Be sure to include E/BNF descriptions of the values that can be used in each element. Your E/BNF grammar should accept all valid automobile instances but may also accept instances that are not valid (see below). Submit the .g file produced by ANLRWorks. Be sure to include comments that identify the team members.

(5 points) Part3: analysis. Identify clearly and specifically ways in which your E/BNF grammar is not fully adequate. That is, if it accepts automobile instances that are not valid describe in what ways the instance may be invalid and why it is difficult to correct this problem. Can you think of a way, however inelegant, that this problem might be corrected? Submit your answer as a PDF file. Be sure to include the names of the team members.

Be sure to follow the submission etiquette.

7. Generalization
Assigned: February 17 Due: February22 (10AM)
Points: 15 Done by: individual
Assignment:  Define a hierarchy of abstractions for "Printed Material" similar to the ones developed in class. The generalization should include such abstracitons as books, magazines, textbooks, newspapers, and at least three others. Each abstraction must have at least two attributes (properties) defined for it. Your hierarchy must be at least three level deep (at least in some point). Represent your hierarchy using an XML schema, a Venn diagram, a tree diagram, and a UML diagram. Submit a PDF document with the three diagrams and .xsd file produced by XMLSpear.

Be sure to follow the submission etiquette.

8. Petri Nets
Assigned: March 24 Due: March 29 (noon)
Points: 20 Done by: team (required)
Assignment:  An intersection has two traffic lights with the normal red, yellow, and green light indicators. One light controls north-south traffic and one light controls east-west traffic. Each traffic light continuously cycles through its set of lights in the normal way. There is also a light for east-west pedestrian control light that signals “walk” or “wait”. The pedestrian control light continuously cycles through its two lights. There is no north-south pedestrian control light.

(a) Write a Petri net that models the operation of the two traffic lights (ignoring the pedestrian control). Specifically, each light should have places representing each of the three lights and it should not be possible for both green lights to be on at the same time.
(b) Add to the Petri net model developed in (a) the elements to model the operation of the traffic lights and the pedestrian control light. The “walk” light is turned on when the north-south traffic light is red and the wait light is turned on when the east-west traffic light turns yellow. The “walk” and “wait” lights cannot be on at the same time.

Note: For clarity arrange the graph in as regular a pattern as possible and label each place with a meaningful name (e.g., Red, Yellow, Green, Wait, Walk). You can label a place by: (1) make sure that the arrow is selected in the toolbar (no Graphelements are highlighted), and (2) double-click on the place to bring up a window with a Name field into which the name of the place can be entered.

Submit via email two file generated by Snoopy, one for part (a) and one for part (b).

Be sure to follow the submission etiquette.

9. Petri Nets - Reader-Writer Problem
Assigned: March 29 Due: April 1 (end of the day)
Points: 15 Done by: group
Assignment:  Develop a Petri net solution to the Reader-Writer Problem where there are two writers and three readers.

In this problem shared information (a data structure, database, or file system) is both read and written (modified) by concurrent activities. Readers only read the shared information. Writers modify the shared information.While the data structure is being written or modified it is necessary to prevent reading of the shared information, in order to prevent a reader from interrupting a modification in progress and reading inconsistent or invalid data. Readers and writers execute different code before and after accessing the shared infromation.

The Reader-Writer synchronization constraints are:
  1. Any number of readers can be reading the shared information simultaneously.
  2. Writers must have exclusive access to the shared information  (excluding all readers and also other writers).
In other words, a writer cannot modify the shared information while any other reader or writer activities are accessing the shared information, and while the writer is modifying the shared information, no other activities may access the shared information.

Note: you will need to use inhibitor edges to solve this problem.

Be sure to use the labeling and commenting features of Snoopy to make the meaning of your Petri net as readily evident as possible. Submit the extended Petri net file produced by Snoopy.

10. Lambda Calculus
Assigned: April 5 Due: April 7 (10AM)
Points: 15 Done by: individual
Assignment:  Answer each of the following questions about the λ calculus.
  1. For each of the following expressions list the free and bound variables (names); for each bound variable show the expression within which it is bound. For example, in the expression  (λ x . (λ y. x x y)  z ) both x and y are bound variables and z is a free variable. The variable y is bound in the expression (λ y. x x y) and the variable x is bound in the expression (λ x .(λ y. x x y) z).
    • (λ x . x y z)
    • (λ x .u x z) (λ y. y w) 
    • (λ x .y x z) (λ y. w y x) 
    • (λ x .(λ y. x x y) (λ z . x y z))
  2. For the following λ expression, show each step of applying a function to an expression successively until no more steps are possible: ((( (λ f . (λ x. f x)) (λ y. y y)) z )
  3. For the following λ expression, show each step of applying a function to an expression successively until no  more steps are possible: ( ( (λ f . (λ x . (λ y. y (f x)))) (λ a. a a ) ) g e )
  4. Explain what happens in reducing the expression:  ( (λ x . x x) (λ x. x x) )

Submit your answers in a PDF file. 

11. Lambda Calculus
Assigned: April 7 Due: April 12 (10AM)
Points: 15 Done by: team
Assignment:  Show that the λ calculus can represent both positive and negative numbers.

(a) Define a function that represents the programming construct "if c then expression1 else expression2" where c is a Boolean conditional and expression1 and expression2 are arbitary compuations. Show a function that takes three arguments whose computation models that of the if-then-else construct. [Hint: don't overthink this.]

 (b) Define a representation of positive and negative numbers. State the function that represents a positive number and the function that represents a negative number. Give examples to show how your representation would encode the numbers "+3" and "-3". [Hint: in computer architecture the representation of numbers involves a "sign bit"].

(c) Using your representation for positive and negative numbers and your answer to part (a) define a function that returns true if a number is positive and false otherwise and (b) define a fucntion that return true if a number is negative and false otherwise.

If possible submit your answers in a text file using the syntax of the Lambda Teacher tool otherwise submit your answers in a PDF file. 

12. Testing
Assigned: April 14 Due: April 19 (10AM)
Points: 15 Done by: individual
Assignment:  Develop a set of rules for testing software systems.

Using your experience with testing the triangle classifier develop a set of at least four  rules that should be used to guide the development of test cases for software systems. Your rules The rules should not refer to the specific characterisitcs of the triangle classifier problem  but should be stated as general guidlines for the kind of test cases to be included in a comprehensive test plan. Each rule should be given as a succinct statement describing the properties of a class of test cases.

Submit your answers in a text file.

13. Testing
Assigned: April 19 Due: April 22 (1:00 PM)
Points: 20 Done by: group 
Assignment:  see assignment web page. Each member of the class has an individual account on WebCAT for this assignment allowing everyone to experiment individually with the assignment in addition to working together as a team. The required format of the test case file is shown in this example test case file.

Submission:  Prior to the due date/time, a member of the team must send me an email (1) stating the members of the team, and (2) having as an attachment the best set of test cases developed by the team in the format described above.

14. Data structures
Assigned: April 28 Due: May 3 (noon)
Points: 10 Done by: individual 
Assignment:  Here are the assignment details.  Submit your answer was a simple text file.