# 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.

 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.

 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. 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)) 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 ) 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 ) 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.