Level 3 Digital Technologies 91636 44) Specific Assessment Guides Complexity and Tractability: 1–4 Formal Languages: 5–8 Graphics and Visual Computing: 9–12 Intelligent Systems: 13–16 Network Communication Protocols: 17–20 Software

Level 3 Digital Technologies 91636 (3.44) Specific Assessment Guide (Complexity and Tractability)

Title Demonstrate understanding of areas of computer science
Credits 4

Teacher introduction

Technology assessment guides have been produced to help teachers develop their own specific assessment guides. Examples of specific assessment guides, developed from the common assessment guide for each standard, have been produced as part of the external assessment resources for level 3 Technology.

The specific assessment guides also show a variety of ways (ie case study, research, practice) to produce external assessment material. The material in the candidate exemplars for each standard reflects the content and context of the specific assessment guides.

Teachers can adapt a common assessment guide and / or a specific assessment guide to suit the specific context of their course of teaching.

Candidate introduction

You will produce a report that demonstrates understanding of areas of computer science. To complete the report you will need to report on at least two of the Areas of Computer Science from explanatory note 3 in the standard.

This specific assessment guide is one of six. Each one of the specific assessment guides relate to one of the six Areas of Computer Science.

Candidate guidance for producing the report

There are some prompts and activities below that will assist you to write the part of your report on complexity and tractability. They will help you to produce a report that demonstrates the understanding expected in this assessment. The prompts also define the levels of description, explanation, and discussion that are expected at each grade.

To demonstrate understanding of areas of computer science at the Achieved level you will need to:

• 
  describe key problems that are addressed in selected areas of computer science
  
• 
  describe examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas.
  

To demonstrate in-depth understanding of areas of computer science at the Merit level you will need to:

• 
  explain how key algorithms or techniques are applied in selected areas
  
• 
  explain examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas.
  

To demonstrate comprehensive understanding of areas of computer science at the Excellence level you will need to:

• 
  discuss examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas
  
• 
  evaluate the effectiveness of algorithms, techniques, or applications from selected areas.
  

Possible Activities

The activities below are activities which generate specific content that you can use to develop your report. For example, if you were to investigate TSP (see activity 6 below) you could generate information related to several parts of the report.

1. 
   Evaluate how much time is needed to solve the TSP, and evaluate approximate solutions (such as nearest neighbour first).
   
2. 
   Investigate the graph colouring problem; a sample plan for this is at Computing Inside's Graph Colouring Activity, as well as the CS Unplugged's map colouring activity. It can be done online at http://gwydir.demon.co.uk/jo/games/puzzles/map.htm.
   
3. 
   Investigate the (intractable) Travelling Rock Band problem.
   
4. 
   Investigate the knapsack problem, and evaluate approximate solutions (such as decreasing order).
   
5. 
   Investigate the bin-packing problem, and evaluate approximate solutions (such as the first-fit algorithm).
   
6. 
   Investigate the progress researchers have made over the years finding improvements to algorithms for solving a particular problem (eg TSP, primality testing).
   
7. 
   Compare different algorithms with a variety of complexities for the same problem, particularly for large values of $n$, considering issues like how well they scale and how much memory they use.
   
8. 
   Compare the speed of ‘bogosort’ (an exponential time algorithm) with a conventional sorting algorithm (such as ‘quicksort’).
   
9. 
   Estimate the work involved for a computer to evaluate all possible timetabling options for your school.
   

Essential documents

The achievement standard governing this specific assessment guide can be found at
http://www.nzqa.govt.nz/nqfdocs/ncea-resource/specifications/2013/level3/91636-spc-2013.pdf

The assessment specifications for the Digital Technologies achievement standard can be found at

http://www.nzqa.govt.nz/nqfdocs/ncea-resource/achievements/2013/as91636.pdf

Definitions

The following are concepts, algorithms, techniques, applications, and problems that students at level 3 are likely to be able to work with; it is not a list of all the key ideas in the area.

Key concepts likely to be encountered are: complexity, exponential time complexity, polynomial time complexity, tractability, asymptotic complexity, big O notation, P and NP, and NP-complete problems.

Algorithms: there are many hundreds of algorithms that illustrate these issues; suitable intractable problems include the travelling salesperson problem (TSP), Hamiltonian path, graph colouring, vertex cover, Sudoku, and longest path; contrasting tractable problems include the Eulerian path, minimal spanning tree, and shortest path. Standard sorting or searching algorithms are excellent for exploring the concept of complexity; bogosort and bozosort can be explored as (artificial) examples of intractable algorithms.

Techniques: empirical evaluation, analysis, brute force algorithm, heuristic algorithms.

Applications: these include route planning, timetabling, optimisation, games, and encryption.

Complexity and tractability is about the relationship between problems and their algorithms, and the idea that some common problems do not have tractable solutions. This falls in the area of computational complexity theory. The focus is on the inherent complexity of a problem, that is, the time needed to solve a problem, and the best known algorithms for the problem. This area includes what is widely regarded as the largest unsolved problem in computer science: the question of whether P = NP (the details of this issue are beyond high school level, but the explorations that can be performed at high school level will give an understanding of why this is such a significant problem). The demonstration of understanding in this area can be done by describing problems with known inherent complexities (both tractable and intractable) and those for which the complexity is an open question; by illustrating the issues surrounding intractable (exponential time) algorithms; by exploring the limits on what can be done with ‘intractable’ problems (such as the various records that have been set for solving the TSP); by comparing heuristic solutions that give sub-optimal solutions; and by exploring the quest to find reasonable time algorithms for those that currently only have exponential time solutions, including recent discoveries about open questions in this area.

Further information

Useful links:

• 
  http://en.wikipedia.org/wiki/Computational_complexity_theory
  
• 
  http://www.tsp.gatech.edu/games/index.html
  
• 
  http://csunplugged.org/graph-colouring
  
• 
  http://en.wikipedia.org/wiki/Travelling_salesman_problem
  
• 
  http://en.wikipedia.org/wiki/Knapsack_problem
  
• 
  http://en.wikipedia.org/wiki/Bin_packing_problem
  
• 
  http://en.wikipedia.org/wiki/Hamiltonian_path
  
• 
  http://en.wikipedia.org/wiki/Brute-force_search
  

Further information can be found at http://www.techlink.org.nz.

Exemplars

Please read the exemplars. You can model your work on these exemplars but you may not copy the material from the exemplars. Your report must be the product of your own efforts.

Schedule

Assessment Schedule AS Digital Technologies 91636 (3.44) Demonstrate understanding of areas of computer science
Final grades will be decided using professional judgement based on a holistic examination of the evidence provided against the criteria.
Issues from the Specifications Authentic candidate submissions will be recognisable because of specific contexts associated with the work. This does not imply that submissions will arise only from the candidate’s practice. However, where the candidate’s practice does not provide the immediate source of a specific context, one would expect to see that several sources of information relating to materials had been applied within a specific context. In both cases, the marker will be able to detect the candidate’s voice. In situations where information does not have some aspect of student voice, it is difficult to establish whether the candidate has actually demonstrated understanding or simply identified information. Candidates who have simply identified information by reproducing information from sources without making use of that information have not demonstrated understanding. Where a candidate has provided a brief answer, the answer should not be penalised because of length. Candidate work in excess of 14 pages should not be marked. Where work is illegible, it cannot be marked. Digital submissions that cannot be read cannot be marked.
Achievement	Achievement with Merit	Achievement with Excellence
Demonstrating understanding of areas of computer science involves:	Demonstrating in-depth understanding of areas of computer science involves:	Demonstrating comprehensive understanding of areas of computer science involves:
describing key problems that are addressed in selected areas of computer science describing examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from the.se areas.	explaining how key algorithms or techniques are applied in selected areas explaining examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas.	discussing examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas evaluating the effectiveness of algorithms, techniques, or applications from selected areas.

Level 3 Digital Technologies 91636 (3.44) Specific Assessment Guide (Formal Languages)

Title Demonstrate understanding of areas of computer science
Credits 4

Teacher introduction

Technology assessment guides have been produced to help teachers develop their own specific assessment guides. Examples of specific assessment guides, developed from the common assessment guide for each standard, have been produced as part of the external assessment resources for level 3 Technology.

The specific assessment guides also show a variety of ways (ie case study, research, practice) to produce external assessment material. The material in the candidate exemplars for each standard reflects the content and context of the specific assessment guides.

Teachers can adapt a common assessment guide and / or a specific assessment guide to suit the specific context of their course of teaching.

Candidate introduction

You will produce a report that demonstrates understanding of areas of computer science. To complete the report you will need to report on at least two of the Areas of Computer Science from explanatory note 3 in the standard.

This specific assessment guide is one of six. Each one of the specific assessment guides relate to one of the six Areas of Computer Science.

Candidate guidance for producing the report

There are some prompts and activities below that will assist you to write the part of your report on formal languages. They will help you to produce a report that demonstrates the understanding expected in this assessment. The prompts also define the levels of description, explanation, and discussion that are discussion that are expected at each grade.

To demonstrate understanding of areas of computer science at the Achieved level you will need to:

• 
  describe key problems that are addressed in selected areas of computer science
  
• 
  describe examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas.
  

To demonstrate in-depth understanding of areas of computer science at the Merit level you will need to:

• 
  explain how key algorithms or techniques are applied in selected areas
  
• 
  explain examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas.
  

To demonstrate comprehensive understanding of areas of computer science at the Excellence level you will need to:

• 
  discuss examples of practical applications of selected areas to demonstrate the use of key algorithms and/or techniques from these areas
  
• 
  evaluate the effectiveness of algorithms, techniques, or applications from selected areas.
  

Possible Activities

The activities below are activities which generate specific content that you can use to develop your report. For example, if you were to show how a sample program could be parsed using a grammar you could generate information related to several parts of the report.

1. 
   Demonstrate how compilers, interpreters, parsers, or validators find errors in formal languages, eg introduce an error to a compiled program, XML document file, or web page, and show the effect of the error.
   
2. 
   Explore regular expressions for pattern matching using a system such as the ‘Regex dictionary’ at http://www.visca.com/regexdict/, the Microsoft Word Find command with wildcards, regular expressions available in a language such as Java (java.util.regex), JavaScript (RegExp), or Python (‘re’ module), or the ‘grep’ program, to find words in an English dictionary that match a pattern.
   
3. 
   Find a grammar for a simple arithmetic expression in a programming language, and show the parse tree for sample expressions (such as (a+b)*(c-d)).
   
4. 
   Make up a few simple Regular expressions (such as ab*a), create a (non-deterministic) finite state automaton for each one using a tool like JFLAP, and show the operation of the automaton for sample strings (aa, aba, abba, etc in the case of the example).
   
5. 
   Write regular expressions to find patterns in documents, such as a URL, email address, date, or time.
   
6. 
   Find a grammar for a programming language, and show how a sample program would be parsed using the grammar.
   
7. 
   Explore the grammar for balanced parentheses S  SS, S  (S), S  ( ).
   
8. 
   Explore using a tool such as Lex, Yacc, Flex, or Bison to parse a simple language.
   
9. 
   Generate art using the ‘context free art’ system (http://www.contextfreeart.org/).
   

Essential documents

The achievement standard governing this specific assessment guide can be found at
http://www.nzqa.govt.nz/nqfdocs/ncea-resource/specifications/2013/level3/91636-spc-2013.pdf

The assessment specifications for the Digital Technologies achievement standard can be found at

http://www.nzqa.govt.nz/nqfdocs/ncea-resource/achievements/2013/as91636.pdf

Definitions

The following are concepts, algorithms, techniques, applications, and problems that students at level 3 are likely to be able to work with; it is not a list of all the key ideas in the area.

Key concepts that are likely to be encountered are: string, grammar, parsing, parse tree, syntax, syntactically correct, regular expression, finite state automaton, lexical analysis, and Chomsky hierarchy.

Algorithms: algorithms associated with formal languages are beyond the scope of this level, although using ad-hoc solutions such as drawing a parse tree will be appropriate.

Techniques: syntax diagrams, grammars, parse trees, finite state automata (both representing and executing), regular expressions, pattern matching.

Applications: compilers, interpreters, text processing, language specification, HTML viewer.

Formal languages is about how to specify programming, markup, and other languages for computing, and systems that can parse and process programs or documents written in such languages. They are specified by formal representations such as syntax diagrams (‘railroad diagrams’), grammars, regular expressions, and finite state machines. The language could be a conventional programming language (such as Java, Python, C, or Basic), another formal language with a strict syntax (such as XML, HTML, or SQL), or the focus could be on regular expressions and lexical analysis (such as detecting a well-formed identifier or number in a programming language, or a string matching a given pattern). Most programming languages have very large formal definitions, and it would be sufficient to demonstrate understanding using a part of a language, such as expressions in a programming language, or a small selection of different kinds of tags in HTML. The demonstration would typically be done by using examples to show the parse tree (or syntax tree) for a correct and incorrect program fragment, or to show a sequence of grammar productions to construct a correct program fragment, or to show strings generated by a simple regular expression and accepted by a finite state machine that corresponds to it.

Further information

Useful links:

• 
  http://en.wikipedia.org/wiki/Formal_language
  
• 
  http://en.wikipedia.org/wiki/Context-free_grammar#Examples
  
• 
  http://en.wikipedia.org/wiki/Abstract_syntax_tree
  
• 
  http://en.wikipedia.org/wiki/Regular_expression
  
• 
  http://www.netcraftsmen.net/presos/Regex_Practice/player.html
  
• 
  http://csunplugged.org/finite-state-automata
  
• 
  http://word.mvps.org/FAQs/General/UsingWildcards.htm
  
• 
  http://www.i-programmer.info/babbages-bag/223-finite-state-machines.html
  
• 
  http://www.jflap.org/
  

Further information can be found at http://www.techlink.org.nz.

Exemplars

Please read the exemplars. You can model your work on these exemplars but you may not copy the material from the exemplars. Your report must be the product of your own efforts.

Schedule