Algorithms in the News

An algorithm is a detailed procedure -- stated in enough detail that it can be executed on a computer. He is a rare event -- an algorithm in the news [ story.php?storyId=114259241 ] (How Do You Find A Job? Ask The Algorithm).

Introduction -- Business Rules and Procedures

All enterprises have there own way of doing things. These are often very well defined. In many cases they are complex legal requirements. Your new software etc. must fit with the rules and implement the procedures. One problem that a software developer or development team must solve is being able to capture rules and procedures. Luckily there are many tools you can use. The best of these are covered in these notes. The same tools/techniques can be used to plan what parts of a system will have to do -- specify the requirements for hardware and software.

Notice that a detailed model can include assumptions about the technology used to implement the model: this is a Physical Model. It can also be independent of the technology and so have a longer useful life -- these are called Logical Models. In these notes mentally classify each technique or tool as best for either logical or physical models.

There are four skills that you need what ever techniques you use. (1) defining the possible scope for the rules and writing rules/procedures that fit within these possibilities. (2) covering every possibility -- this is called completeness. (3) giving only one response for any possibility -- this is know as consistency. (4) Getting the rules right -- this is correctness.

You will find that writing correct, complete and consistent rules/procedures to be be harder than you might think.

Example -- DiscountsR'Us

A certain department store has a complicated scheme for calculating discounts. Here are the rules:
1. RULES::=following
   Net
   1. (R1): If a person has a club card and today is a Tuesday then the discount is 10%.
   2. (R2): If a person has a club card and today is not a Tuesday then the discount is 5%.
   3. (R3): If a person is a senior and has a club card then the discount is 10%.
   4. (R4): If a person is a senior and has not got a club card then the discount is 5%.
   5. (R5): If a person is not a senior and has not got a club card then the discount is 0%.

   
   (End of Net RULES)
   
   

   I'm glad that I don't have to program these discounts into the Point Of Sale terminals! The RULES have a problem -- they are inconsistent: sometimes they give two discounts to a person (exercise: when?). It is also difficult to find out if the rules are complete -- is every possible case covered?

   Introduction to Capturing Rules and Procedures

   Complex rules and conditions need precise notations: decision tables, and/or tables, logic trees, Karnaugh maps, activity diagrams/flow charts, mathematical logic, ... plus other techniques discussed in [ ../cs556/ ] Formal Methods. Some of the best known are discussed below. Formalizing and checking procedures and rules is time consuming but essential. Once found, there are many ways of resolving inconsistencies and completing the rules. However these should not be invented by a programmer or an analyst -- you need to talk to the people involved in the system -- the stakeholders -- to resolve inconsistant and incomplete rules and procedures.

   Notations and Tools for Capturing Rules and Procedures

   Choose the notation and media that fits your needs now and in the future. This means being prepared with several techniques/tools. Here is quick list of the techniques covered below.
   
   1. Text
      
      1. User Stories
      2. Scenarios
      
      
   2. Diagrams
      
      1. Plans
      2. Activity Diagrams
      3. Earlier Flowchart-like notations
      
      
   3. Pseudocode and Structured English
   4. Symbolic Logic and Mathematical Formula
   5. Tables
      
      1. Truth Tables
      2. Karnaugh Maps
      3. Function Tables
      4. Decision Tables
      5. And/Or Tables
      6. Extended Entry Tables
      
      
   6. Tree Diagrams
   7. Prototypes
   
   

   Text

   Text is natural. But it is hard to read and difficult to write clearly. There are few tools for analyzing text data. It is almost impossible to read a complex set of rules or a description of a complex procedure and spot errors and inefficiencies in it. There are horror stories of teams face with a thousand pages of densely written rules and procedures that have to be embedded in their software.

   On the other hand, you should include text in requirements documentation to explain the thinking that goes into the more formal definitions, tables, diagrams, and formulas.

   User Stories

   Writing a one paragraph description of a feature or property that the use has asked for is a a popular and agile requirements technique. I essence a "user story" is a short, one paragraph description of something that the user wants. If it can not fit on a 3><5 card then it is too long. If it has lots of technical details it is not a "user" story. User stories are simple enough not to need much coverage here. You can get details from the Wikipedia, link below.

   Scenarios

   A scenario is another simple text based technique: Scenarios are a list of actions by various actors. They give a single possible execution of a process. They should not be used to define algorithms or logic. They just show one possibility not all the variations. loops, etc.

   . . . . . . . . . ( end of section Text) <<Contents | End>>

   Diagrams

   Plans

   When you have a set of activities that must be completed but you have no required order then you can use Network Planning and the Critical Path Method [ c3.html ] to document, plan, manage, and control them.

   Network plans are essentially specialized [ Activity Diagrams ] (below).

   Tree Diagrams

   Sometimes you have a complex decision to capture in your requirements. Tree diagrams are a popular way of mapping out a complex sequence of conditions. You can use an activity diagram or a notation like this

   

   If you want to learn more you can use the Wikipedia. I don't require you to use these in quizzes, finals, or exercises. You may find them helpful in presenting your project. Tree Diagrams are essentially specialized [ Activity Diagrams ] (next).

   Activity Diagrams

   Activity diagrams are one of the thirteen UML diagrams. They are an excellent way to record existing procedures, new procedures, programs, and processes. They can show both complex logic and complex interactions between activities in a process.

   

   Here is an example of these symbols in use describing a procedure for handling Customer Orders.

   

   Here is the same example procedure with swim lanes that allocate the activities to different parts of the system or to different actors.

   

   There are a lot more features available to you in the standard, for example here is a link to an example of a data store.

   There are a dozen different UML diagrams. One of these, the activity diagram, is designed to replace flowcharts!

   Flowcharts -- Activity Diagrams before the UML

   

   The Dia and Visio graphic programs provide ready-made palettes of these symbols when you need to produce a final/pretty diagram. Or when you know the procedure is going to change and so want an editable format.

   The simplest set of symbols is the ASME standard set. It has precisely five symbols: operation, delay, inspect/test, store/retrieve, and transport. An efficient process minimizes everything but operations!

   

   An important rule for flowcharts and activity diagrams

   They always have a special START node to get the activity/process started. They usually have a number of STOP nodes to terminate the activity.

   A Flow Chart is not a DFD

   Do not confuse these. A flowchart shows the sequences of activities. A DFD shows parts of a system and how they are connected. A flow chart can have decisions and branches but a DFD does not. A flowchart has a start and a finish, a DFD is running all the time.

   Use flow charts and activity diagrams to document the detailed behavior of processes inside a DFD -- if the process is complicated and interesting.

   State Charts and Protocol Machines

   Sometimes a business will have rules that determine the order in which events must occur. This is subtly different to describing the sequences of activities. Here we want to be sure that someone does not draw a pension before they retire or after they are dead, for example. The natural way of handling these rules is to define states (nodes in the diagram) and the events that change states (arrows with [conditions] and event names on them).

   The UML provides a type of diagram -- a State Machine or State chart. It shares a lot of features with an activity diagram. The key difference is the appearance of events on the transitions. Here is an example from the draft UML2.0 standard.

   

   These state machines are studied in great detail in Computer Science theory. In this class they won't appear in quizzes or the final, however you may find a use for them in the projects. They do appear in CSCI375 (requirements analysis).

   Decisions in Diagrams

   Notice that complex decisions sometimes appear in flow charts and activity diagrams. In activity diagrams the conditions are written in square brackets on the transitions: [x>5], [x<5], [x=5]. In flowcharts the condition is written inside the diamond and the transitions are typically labbelled "yes" and "No" or "True" and "False". Sometimes the conditions can be difficult to document. Give them a meaningful name ([no discount]) and use the other techniques described here to document the details.

   . . . . . . . . . ( end of section Diagrams) <<Contents | End>>

   Pseudocode and Structured English

   In the 1960s Computer Scientists proved hat we only need three structures to express any algorithm. They are: Sequence, Selection, and Iteration:

   

   Programmers have since learned to use them and to express required algorithms and program designs using a structured version of English. Pseudocode (sue-do-... not suede-oh...) is an imitation structured programming language. It typically mixes a natural language and structures like IF-THEN-ELSE-END IF and WHILE-DO-END WHILE.

   Here is a sample of traditional Pseudocode:

    IF person has club card THEN

    	IF today = Tuesday THEN

    		discount := 10%

    	ELSE

    		discount := 5%

    	END IF

    ELSE discount := 0%

    END IF

   The use of "=" is not like it is in C/C++/Java/PHP/... but more like that of the 1960s. In the above ":=" indicates that a new value is assigned to the variable on the left hand side. The "=" is a test for equality. Using "==" is an error.

   Here is an example with a WHILE loop.
   (Algorithm_F):

     	factorial := 1

     	WHILE n > 1 DO

     		factorial := factorial * n

     		n := n - 1

     	END WHILE

   Notice that you can write and process Pseudocode with your favorite programming editors. What makes it "Pseudo" is that you can not compile or interpret it. On the other hand it has equally strict rules:
   

   1. Use capital letters to show structure.
   2. Every IF has a THEN.
   3. Every IF has an END IF.
   4. Every WHILE has a DO.
   5. Every WHILE has an END WHILE.
   
   

   Here is the BNF syntax for

2. Pseudocode::syntax=following,
   Net
   1. condition::given.
   2. variable::given.
   3. expression::given.
   4. assignment::= variable "=" expression.
   5. sequence::= statement # statement.
   6. statement::= line | loop | selection.
   7. loop::= "WHILE" condition "DO" eol sequence "END WHILE" eol.
   8. selection::= "IF" condition "THEN" eol sequence O("ELSE" eol sequence) "END IF" eol.
   9. line::= (assignment | other action) eol.
   10. eol::=end of line.
   11. O(x)::=x is optional.

   
   (End of Net)
   
   

   Not following this syntax in this course is an error.

   Symbolic Logic and Mathematical Formula

   Some rules are best expressed using traditional mathematics and Boolean expressions. For example, in a game, a missile will follow a trajectory described by
   Net
   1. y = y0 + v t - g t^2 / 2,
   2. x = x0 + u t.

   
   (End of Net)
   
   These are precise and short. They may not be user friendly.

   Story -- Do the Math

   In "Imperial Chemical Industries" (UK) in the 1960's the Sodium Production group asked Computer Services to find the optimal rate of flow of mercury through their sodium electrolysis bath. A young co-op student (me) was tasked to work with them, develop a model, solve it, use the mainframe to implement the solution, and provide results that let them choose the best flow. I talked with the people and developed a special kind of model: (a Partial Differential Equation), looked up the formula solving the equation in a text book, translated the formula into code, and tested it (worked second time). This took about less than 3 days (one test per day). But I had a whole week before I met the clients again so I modified it to give graphic output.

   When I showed it to the user he: (1) gave me the correct parameters for the model, (2) rejected the results with four decimals of accuracy -- he could only measure to 1 place, and (3) said the graphics were more help. I removed the figures.... and the result was a program that solved their problem.

   Summary: by using mathematics and three iterations the whole project was finished in 2 weeks.

   Mathematical Logic

   In business most rules have conditions have "If .... then ...." in them and so you need a way to express conditionals. Symbolic or mathematical logic can help.

   So the example RULES (above) we might be expressed in logic like this. (the '@' indicates a true/false proposition)
   Net

   1. p::@, the person has a club card.
   2. q::@, today is Tuesday.
   3. r::@, the person is a senior.
   4. s::@, the discount is 10%.
   5. t::@, the discount is 5%.
   6. u::@, the discount is 0%.

      And then the requirements might be written something like this
      (r1): p /\ q => s
      (r2): p /\ q' => t
      (r3): r /\ p => s
      (r4): r /\ p' => t
      (r5): r' /\ p' => u

   
   (End of Net)
   
   Notice that this approach does not help the typical stakeholder.

   More, it does not help the typical programmer either. There have been experiments in using logic and discrete math to describe the behavior of a system in abstract form and then to analyze the model to see if the ideas work or to search out unwanted behaviors. We have tools that test logical statements for completeness and consistency. These are a part of [ ../cs556/ ] Formal Methods. They have been used successfully to debug real projects.

   Tables

   Tables are an excellent way of analyzing and expressing complex logical rules. I've used them for 30+ years. They have the precision of symbolic logic but they are also client friendly. This section of notes shows how the DiscountsR'Us RULES can be expressed using several tabular notations. Some of these notations uncover the problems with the rules.... which?

   Truth Tables

   These have one column for each variable. Each row lists the values of the variables: T=true, F=false. The following table shows the possibilities for a discount of 10%.
   Table

   Club card	today=Tuesday	Discount=10%	Result
   T	T	T	T
   T	T	F	F
   T	F	T	F
   T	F	F	T
   F	T	T	F
   F	T	F	T
   F	F	T	F
   F	F	F	T

   
   (Close Table)
   Each column that you add doubles the number of rows. So if we documented all the given RULES we would need 32 rows. This is good for symbolic logic but clumsy and verbose used for software requirements. The table does not help discover inconsistencies and incompleteness in a set of conditions.

   Karnaugh Maps

   By using two dimensions, we can save space and compress all 8 cases into a "matrix" of possibilities. For each case we put the result(T/F) in it's cell:
   Table

   -	-	Club card	no club card
   Tuesday	Discount=10%	T	T
   Tuesday	Discount!=10%	F	T
   not Tuesday	Discount=10%	F	F
   not Tuesday	Discount!=10%	T	T

   
   (Close Table)
   

   But this is still clumsy and unhelpful. The full example has 5 variables and 32 cells. Karnaugh maps with more than 4 T/F variables are complex.

   Function Tables

   A famous computer scientist and software engineer, David Lorge Parnas, in the 1990s, made the next step: extend the table to allow non-truth-values in the cell. These tables are used to describe functions: rules that map conditions into results. We make one cell for each combination of the inputs and put the result in the cell. This makes it easy to check the requirement for completeness (no blank cells), and consistency (one value per cell).

   For example

   1. percent_discount::=following,
      Table

      Club Card	Age	Tuesday	Not Tuesday
      Club Card	Senior	10%	10% ??? 5% ???
      Club Card	not Senior	10%	5%
      no Club Card	not Senior	0%	0%
      no Club Card	Senior	5%	5%

      
      (Close Table)
      Notice that recording all the rules in this kind of table instantly identifies the problem with RULES. Key point -- a function table exposes an inconsistency. It will also show up incompleteness. It lets us discover and display to the stakeholders, the problem with their requirements. It is a good tool for improving them.

      Decision Tables

      These date back to the 1960's and are a semi-formal notation. This means that they have a well-defined mathematical base but they were used before the theory was invented. Each decision table has two parts. The top half lists the conditions and values like a truth table -- but many use Y=Yes, and N=No instead of "T" and "F". Conditions are also be shown as "-" which means "don't care". The bottom half indicates the actions. An action to be executed is marked with an "X". An extra row counts how many cases are covered in each column. Each don't care doubles the number of cases in that column. These numbers are used to check the table for completeness and consistency:

      
      Table

      Condition	1	2	3	4	5
      club card	T	T	T	F	F
      Tuesday	T	F	-	-	-
      Senior	-	-	T	T	F
      Action
      discount=10%	X	-	X	-	-
      discount=5%	-	X	-	X	-
      discount=0%	-	-	-	-	X
      Count	2	2	2	2	2

      
      (Close Table)
      Each column describes a condition and the actions that are required. In general, several actions can be done (several X's in a column) for a set of conditions. Indeed you use "A", "B",... to indicate the sequence of actions to be executed.

      Notice that each column covers 2 cases and so there are 10 cases covered in the table, even tho' there are only 8 possible combinations of T and F! This simple check should make us search for the inconsistency in the original requirements. Again a table proves helpful in spotting incomplete or inconsistent rules.

      The main advantage is that users and managers have no problem understanding them. The main problem with these tables was maintaining them in parallel to source code. To fix this problem people developed decision table compilers. These generate source code from decision tables (one written in COBOL by a BS student of mine in the 1970's).

      And/Or Tables

      A piece of research (the Traffic Collision Avoidance System -- TCAS II in 1995... at UC Irvine ) rediscovered the value of tables. They used "And/Or" tables to document the conditions for states to change. Their clients liked them. The key idea is that each column is "and-ed" together, the columns are "or-ed". The researchers developed tools to check And/Or Tables for completeness and consistency.

      

      A graduate student at CSUSB has developed web-based tool to generate AND/OR tables from formulas. I have been working on algorithms that can carry out Boolean operations on And/Or tables. A BA student has developed an initial C++ API framework for manipulating And/Or tables.

      Extended Entry Tables

      Notice that all types of tables that only use "T" and "F" can be extended to tables that use other values for variables. This reduces the size of the table but makes them harder to check.

   . . . . . . . . . ( end of section Tables) <<Contents | End>>

   Prototypes

   One way of exploring complicated requirements is to program them in a throw-away (Bread board) prototype. Review [ a6.html#Prototypes ] to see what I mean.

   Notice that prototypes are OK for checking out how obvious requirements work. They can not help with checking for obscure conditions that are inconsistent or cases that are not defined. The tables and other techniques in this set of notes can do this.

   Hint -- Reify Complex Rules -- encode them as data

   When you have a complex piece of logic to express it may pay to encode it as data. This typically simplifies the algorithm. If the data is held on a data base then it can slow down the program. But when the rules change (and most rules in real life change) all you have to do is change the data. This can even be set up as a process done by a stakeholder. This simplifies maintenance and reduces the total cost of ownership.

   Here is an example: the rules of Tic-Tac-Toe are simple to state in English. Consider just the rules that determines if x has won: There must be a row with 3 xs, a column with 3 xs or a diagonal with 3 xs. It is easy to encode the board as an array of 9 characters. Writing out the rule for winning in a table or in symbolic logic takes time (exercises below). Diagrams, pseudocode, and coding are worse. One technique is to list the the 8 winning configurations (3 rows, 3 cols, 2 diagonals) in a constant array and just run through them in a simple loop. The program is much simpler because part of the logic is now data.

   Here is an example where putting part of the program in a data base makes sense. The fair on our local bus system depends on the type of pass (one trip, one day, ...) and the type of person (senior, disabled, student, other). More ... the values change every year. It would be a mistake to code this in a program:

    		IF person is senior AND pass is 31-day

    		THEN cost is 23.50

    		...

   Instead add entities to the data base and look up the value. Add a simple process that lets the right person in the bus company change the values. You can now use the same data to prepare flyers, fare sheets, and time tables....

   Hint -- Use tables to sort out rules first

   In my experience complex logic is nearly always best analyzed using one or more tables. This will tell you if any cases are missing, or if the logic is inconsistent.

. . . . . . . . . ( end of section Processes, Procedures, and Logic) <<Contents | End>>

Frequently Asked Questions on Detailed Models

What tools should I use to draw diagrams?

Any CASE or graphics tool can be used. But low tech tools are better for generating ideas. For example, a chalkboard is vital when a team is thinking together. But it doesn't store the ideas well. A camera or a special electronic board can help with this. Personally, I do a lot of very messy diagrams on the back of printed reports using a pencil etc. I am forced to switch to Visio, Dia, or Word Perfect to present ideas in class or seminars. I have been forced to use Microsoft Office to get some figures published. A nasty bug fouled them up. I would like to experiment with a tablet + pen system -- if I had the money. Use computerized tools once the ideas are firmed up and you need to present to other people or store for future reference.

Is there professional standard software package for producing diagrams

Not as far as I know. There are half-a-dozen companies that might claim that they sell the standard, but I don't believe them. On the other hand -- find out what your company/enterprise uses and fit in.

What is the cheapest graphic tool

Dia is Free! And not bad.

What is the cheapest CASE tool

I'm not sure but there is a good open source product.... Umbrello tends to crash. Argo is at [ http://argouml.tigris.org/ ] but does not support the latest standard UML2.

Is advanced modeling terribly difficult

By the end of CSci375 you'll find modeling a simple process. The catch is that getting a useful and correct model can take time and thought. Modeling is a disciplined way of thinking. Of course, any kind of thinking tends to be hard work.

How does a DFD differ from an activity diagram?

A DFD is made of stores and processes. An activity diagram has activities, objects, and decisions. Activities do something and then cease to exist. When an activity outputs an object it outputs just one. It acts as a signal to a new activity to take over and absorb the object. The processes in a DFD always exist, they just pause when there is no data to process. In a DFD the data flows are buffered. Thinking electricity in a wire or water in a pipe. They show a sequence of objects moving from a process or store that does not go away -- the parts continue to exist and continue to work until the system is destroyed. A DFD shows the processes and data that exist and has no starting point or stopping point. The parts of the system: stores, processes, flows, and entities are assumed to neither stop or start, however they may rest for a while when nothing has to be done. They are like parts of a mechanical clock.

As a rule an activity diagram shows a lot more detail than a DFD. One process in a DFD may take a whole activity diagram to describe in detail. An activity diagram and a flowchart always has a START node. And nearly all of them have a STOP node. DFDs don't have these nodes.



How do you show how control flow is implemented in a DFD

You don't! If control flow is needed use an activity diagram.

What you can do in a DFD is show a process with a flow of data entering it and two flows leaving, and each item in the flow is sent out on one or other of the outputs. Here are two example DFD processes.



Here is what happens when you draw a DFD of a process that can produce different sets of outputs depending on the values that are input:



Who designed activity diagrams and when where they designed

The group working for the Object Management Group (OMG) developed the specifications from about 2000 to 2004. It is a an industry sponsored standard based on unifying several previous ways of showing complex processes and protocols.

Is there a fork and join in old fashioned flowcharts

Yes. They are just like the ones in UML Activity diagrams. Fork and Join date back to the 1970s.

. . . . . . . . . ( end of section Questions on Detailed Models) <<Contents | End>>

Online Resources and Exercises

User Stories on the Wikipedia

[ User_story ]

Scenarios on the Wikipedia

[ Scenario ]

Decision Trees and diagrams on the Wikipedia

The Wikipedia article [ Decision_trees ] is about the use of decision trees in artificial intelligence and data mining. However [ OBDD ] Describes a version of tree diagrams that have been extensively analyzed by computer scientists called "Ordered Binary Decision Diagrams". We don't have time to chase OBDDs any further. I cover them in my formal methods [ cs556/ ] class.

Big Activity Diagram

It shows an Activity Diagram with Swim Lanes showing how faculty and students interact over assigned work. Please printout this (large) graphic: [ 07ActivitySwimLane.gif ] as part of this set of notes. When you want to know more about activity diagrams for a project, see [ umlnut2-CHP-9 ] (UML 2.0 in a Nutshell) and [ ch20lev1sec1 ] (Part of chapter 20 of the UML2.0 reference manual).

Object Management Group on the web

1. OMG::= See http://www.omg.org/

   Flowcharts

   Here is a web site [ whatis.htm ] recommended by Mark Doernhoeffer in his "Surfing the Net for Software Engineering Notes" in ACM SIGSEN.

   The earlier notations where ANSI/ECMA/IBM standard Flowcharting symbols. Here is a template or stencil for the symbols that you can get from [ http://www.draftingsupplies.com/ ] (if you ever need to!).

   Tutorial on ANSI Flowcharts

   If you want to learn how to do ANSI (American National Standard) flowcharts then start by studying the PDF found here [ citation.cfm?id=356566.356570 ] (you'll need to join ACM or be on campus...).

   Buying an ASME template

   [ 1218i.jpg ]

   State Charts on the web

   If you want to know more check out the 3rd edition of Fowler's "UML distilled" or [ stateMachineDiagram.htm ] (Ambler's Agile Modeling Site).

   Pseudocode on the Wikipedia

   The Wikipedia [ Pseudocode ] entry is an excellent resource.

   Writing Mathematics on a computer

   For my ideas on expressing symbolic logic and mathematics on computers see [ ../maths/intro_logic.html ] and [ ../maths/intro_characters.html ]

   Traditional mathematical Notation needs tool like Donald Knuth's more complex Τ_ΕΧ language. See my notes [ ../samples/languages.html#TeX ] or the "Equation Editor" found in most word processors from [ http://www.mathtype.com/ ] Also see [ TeX ] on the Wikipedia.

   Venn Diagrams

   Venn diagrams are an excellent presentation tool for simple logic with no more than three (3) sets or predicates. However they are no help in more complex situations. Interesting examples of Venn Diagrams and graphs can be found at [ watch?v=lWWKBY7gx_0 ] and [ http://thisisindexed.com/about/ ] (blog). Note -- I do not endorse the content in these web sites. They just show some informal ways of using mathematics.

   Tables on Wikipedia

   The Wikipedia has notes on [ Truth_table ] and [ Decision_table ] if you need to find out more.

   More on tables

   Look at [ notn_9_Tables.html ] for more on tables.

. . . . . . . . . ( end of section Online Resources and Exercises) <<Contents | End>>

Review Questions and exercises

1. Check the formulas, diagrams, and tables in this handout for mismatches with the Discounts'RUs requirements.
2. List the 15 or so techniques in this set of notes (from memory). Which are best for physical models and which for logical models?
3. Here TBA is a set of requirements expressed informally. Use any techniques that you know do discover any incompleteness and/or inconsistencies in these requirements.
4. Here are two sets of requirements concerned with the encoding of Universal Resource Locators in the HTML. Do they always describe the same encoding? If they don't give an example and how it is different.
   • URL_encoding::=
     Net
     Each character in the string is encoded as follows: If it is a letter or a digit it is copied, if it is a space then it is replaced by a plus sign. Otherwise the character is replaced by a percent sign followed by the hexadecimal code for the ASCII code of the character.

     
     (End of Net)
     
     
   • IE4_URL_encoding::=
     Net
     Each character in the string is encoded as follows: If it is a letter or a digit it is copied, if it is a space then it is replaced by a plus sign. Plus signs are copied as is. Otherwise the character is replaced by a percent sign followed by the hexadecimal code for the ASCII code of the character.

     
     (End of Net)
     
     
5. Find a set of complicated requirements like the Discounts'RUs example and attempt to use any of the techniques in this section of notes to document it. Can you discover any inconsistencies or any incompleteness?
6. Here [ hailstone.png ] is an activity diagram describing the Hailstone sequence. Work out a scenario that shows all the successive values of n if the value input is 17.
7. Write out some Pseudocode for the Hailstone sequence (above).
8. Draw an activity diagram for calculating the factorial of n from the Pseudocode Algorithm_F in the page above.
9. Here [ activitydiagram.gif ] is an activity diagram. Translate into English!
10. Take the two example DFDs that split up data flows. Draw an activity diagram for separating even and odd numbers. Write Pseudocode for separating undergraduates from graduates.
11. What do you use an activity diagram or flowchart for?
12. How does a DFD differ from an activity diagram -- list all the ways.
13. How does a ERD differ from an activity diagram -- list all the ways.
14. How does a state machine differ from an activity diagram -- list all the ways.
15. What items of metadata need to be stored in a data dictionary about a simple element like a social security number?
16. What items of meta-data are needed to document a record?
17. What is a scenario?
18. Describe Pseudocode.
19. How is logic and mathematics be used in detailed models?
20. We encode a TicTacToe board as an array of 9 boolean variables which are true if x has played on them:
    Table

    x[0]	x[1]	x[2]
    x[3]	x[4]	x[5]
    x[6]	x[7]	x[9]

    
    (Close Table)
    Write down the logical formula describing a win for x.
21. What is a tree diagram? Include an example in your definition.
22. Draw a tree diagram that determines if a year (A.D.) is a leap year or not.
23. What do we call a program that is not useful but demonstrates some of the requirements on a system? How does this differ from an iteration?
24. Draw a flowchart/activity diagram that models cost benefit analysis.
25. Explain and define an algorithm for solving the quadratic equation a x^2 + b x + c = 0 for all possible cases with real a,b, and c. See the DFD [ SolveQuadDFD.png ]