| 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 |
| Assignment:
(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:
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.
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. |
|