FIS IB Comp Sci 2013 yr 2 Blog

by  Dave_Mulkey@fis.edu  ,  Frankfurt International School  ,  Germany

Study Individually - 18 Apr 2013

Use these links (local at FIS) to STUDY for your exam:

v:\Mulkey Dave\!IBReview12\HLPastExams\index.html

v:\Mulkey Dave\!IBReview12\IBCS.pdf

The links will work on a PC connected to our LAN (cables).

With a laptop, you need to connect to \\hamlet\US Class\instruction
instead of V:

Hash Codes and Linked-Lists - 16 Apr 2013

May 2012 Paper 2 # 3

Arrays and Classes - 12 Apr 2013

Nov 2011 Paper 2 #2

Arrays Practice - 11 Apr 2013

May 2012 Paper 2 # 1

More Exam Practice - 9 Apr 2013

Today you will practice writing exam answers. 
You will be answering questions about the Case Study.

You should work with a partner.  Write the best answers you can manage for each of the following questions (below).  Each pair of partners should turn in one set of answers - only one person needs to do the writing.  Your answers must be written with a pen on a sheet of paper.  Work quickly, using the ideas we discussed yesterday.  At the end of the period TURN IN YOUR ANSWER PAGES to the teacher (or substitute).

== Questions ==

Use the Case Study to answer these questions (a-d).

(a) Suggest two principal reasons that have led to the convergence
      of technologies as shown on page 3 of the case study.  [2 marks]

(b) Two students are sitting in a café.
     They both have smartphones which have their Bluetooth facility enabled.
    (i) Describe the precautions they should take while sending files to each other. 
        [4 marks]
    (ii) State two different examples of a piconet that might be operating
          within this café.   [2 marks]
    (iii) Outline how frequency-hopping prevents the piconets
          from interfering with each other.  [4 marks]

(c) Police forces in several countries are being equipped with smartphones.

     (i) Describe two ways in which smartphones could aid police
          who have just stopped a motorist suspected of a crime.  [4 marks]

      (ii) Suggest one way in which the use of Bluetooth could
            provide additional assistance.  [2 marks]

(d) With reference to mobile phone networks, explain how
      two different mobile phones are able to use the same frequency
       within the same city at the same time.  [4 marks]

Past Exam Practice - 22 Mar 2013

May 2012 HL Paper 1

Homework : Do question 4 on May 2012 HL Paper 2 -
  these are the questions about the Case Study.

Systems - 18 Mar 2013

Computer Systems Vocabulary

Tree Program Practice - 12 Mar 2013

Dynamic Tree .zip archive

Array Tree .zip archive

PRINTING the Dossier (Project) - 6-11 Mar 2013

Remember that your dossier (project) is due on Monday 11 March.
You must print ALL PAGES - all sections A,B,C,D and the program listing -
yes, you must print section A and B again even though you did it earlier.
Turn all the pages in on Monday, in a notebook or folder.
It will probably be at least 100 pages, so plan on spending some time
printing.  Make sure that:

The printed pages are due at 15:30 on Monday 11 March, in room 276.

Binary Search Trees - 1 Mar 2013

Binary Search Trees Notes

Trees in Arrays - 28 Feb 2013

Trees In Arrays Sample Project

Trees - 26 Feb 2013

Trees - Introductory Notes

More How-tos - 29 Jan 2013

Here are some notes about Text Files:
http://ibcomp.fis.edu/inputs/FileDemo.html

Progress Check - Mastery - 23 Jan 2013

Mastery Check

In case you have forgotten, there are lots of
notes about the project here, including deadlines:

IA Dossier Notes

Continue Programming Your Project - 21 Jan 2013

*** Mon 21 Jan - SNOW DAY *********************************

Continue writing the program for your Internal Asssessment Project.

Today would be a good day to make BACKUPS.

*********************************************************

How To Show Pictures - Code Example - 14 Jan 2013

Here is a sample NetBeans program that shows how to display a picture.

Writing your Project Program - 7 Jan 2013

We will spend 5 weeks writing the program for your project.
You must also plan on working outside class - the class sessions alone
will NOT provide enough time to write a successful program.
Be sure to bring a laptop or USB stick every day so that you
can continue your program.

Mock Exam  Review - 26 Nov - 3 Dec

Copy the Review packet (from V: drive or USB stick)

Monday :
- Online vocabulary practice program (run VocabPractice.jar)
- Recognize (click buttons to reveal answers)

Tuesday & Thursday :
- Read the SL Review Summary (check your answers with SL Review Answers)
  Concentrate on learning all the VOCABULARY words

Friday :
- Read the HL Review Summary (check your answers with the HL Review Answers)

Weekend & Monday :
- Nov 2008 exams - paper 1 and paper 2

Question 3 from Nov 2009 p2 - 12 Nov 2012

Announcement -
Stage B Design is due on Monday 26 Nov

Work on IA Project - 9 Nov 2012

Work on your Internal Assessment Project.  You are probably at the stage
of working on ALGORITHMS - review the notes about Designing Algorithms
below on 29 Oct.

Nov 2009 Exam #3 - 8 Nov 2012

We will discuss question #3.

Nov 2009 Exam #1 - 7 Nov 2012

We will discuss question #1, then start on question #3.

Practice with System Design - 5 Nov 2012

We will review Nov.09 Paper 2, as this covers some concepts that will be useful
in Designing your project, as well as providing some review for the Mock exam.

B2 - Designing Algorithms - 29 Oct 2012

Algorithms are the generic term for methods (as they are called in Java).  Algorithms perform the automation which is the main goal for most users. 

Most algorithms function invisibly in the "background" of the program.  They are usually associated with a visible task.

Pre-condition ==> Algorithm ==> Post-condition

Most algorithms accept some input, then process the data, and finally produce output. 
For the IB Dossier, you are expected to describe this as follows:

  Requirements
  Examples

method
   header(parameters)  
     pre-conditions
     algorithm
     post-conditions
     return value

    int  search(String[ ] list , String target)
       pre-conditions : list must contain a sorted list of Strings
       algorithm :  performs a binary-search for target
       post-condition :  returns the position of target in the list
       return :   the position of target in list
                     
or  -1 if target was not found in the list
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   void  sort( String[ ] list )
       pre-conditions : list is an array containing Strings
       algorithm  :  Bubble-sort
       post-conditionlist is now in alphabetical order  A..Z
       return  :  nothing

In a diagram, it looks like this:


    Starting Data                                                          New / Reorganized Data
                             =====>   algorithm  =====>
     parameters                                                                return value


- Naming Algorithms -

Just as nouns help us to define data items and data-structures,  VERBS help is to choose and name algorithms.
You can examine user-stories and identify the verbs to get ideas for needed algorithms. 
For some examples, look at Guidance Notes (p. 16)

Data-Flow - 25 Oct 2012

Every data item has a data flow path through the system,
that includes input, storage and output. 
Here are some examples from the school's attendance system:

It's not necessary to record this for every data item, but it should be in your mind.
Some large data-flows need to be documented in your Modular Design - B2.

More Work on Design Stage - 24 Oct 2012

Work on your Data Structures.

The most important Data Structures are probably the Data Files
that provide permanent storage for your data.

It is unlikely that you can manage to store all your data in one single file.
Then there will be data in one file that is linked to data in another file.

A simple data-linking example is pictures.  We can store all the pictures in a folder.
Then the names of the pictures will be stored in a data file, so that it
is easy to look up a picture with specific characteristics.  For example:

  Students.dat                                       Files on Disk Drive

Name : Bob Smith
ID : 12345
Photo : student12345.jpg
Homeroom: Mr Smith
 ...
Name : Julie Adams
ID : 24680
Photo : student24680.jpg
Homeroom : Ms Alexander
 ...
....
....
student12340.jpg
student12345.jpg
...
...
...
student24675.jpg
student24680.jpg
...
...

Another example involves lists of standard data items.
For example, the names of the Homeroom Teachers above
might be chosen from a list.  Then we need to have a list of all
the existing homeroom teachers in a data-file, perhaps a Text File,
like this:

 Homerooms Text-File

    Ms Alexander
    Mr Baker
     .....
     .....
    Mr Smith
    Ms Taylor
    ...
    ...

Now whenever someone types in data for a student, the program
should automatically validate the Homeroom name by searching
in the Homerooms file, and validate the photo name by searching
on the hard-disk.  These validation processes will be methods
in the finished program.

Eventually you must write section B1 of your project
describing all the data-structures that you will use in your program.
The most important are the data-files.  You must describe them
as shown above, with diagrams and sample data.  You will probably
write a longer text description of each data-structure than shown here.
Refer to the sample SL dossier to see how section B1 should look.
For now, you can start making clear notes about data-files and arrays.
Write sample data. 

While planning your program, think of specific sample data.
Then ask yourself : "Where will this be stored?"  If you are unsure,
then make a plan - or ask for help. 

Designing the program takes time - you still have a few weeks.

Some Past Paper Questions - 23 Oct 2012

The teacher will review the design overviews individually with each student.
While this is happening, other students should:

Design Overview Outline - 18-19 Oct 2012

Spend 2 class periods, and a bit of time at home,
outlining your intended solution for your IA Project.
Use this form : DesignOverviewBlank.doc

Plan on showing your outline to the teacher on Tuesday 23 Oct.

Project - Stage B Design - 17 Oct 2012

Guidance Notes

Extracting nouns for data and verbs for methods

Design Outline

Past Paper Questions - 15 Oct 2012

Practice these questions:
Past Paper Questions about Recursion

There will be a QUIZ about recursion tomorrow.

Recursive Methods Practice - 12 Oct 2012

It will be easiest to do these exercises with Processing,
but they will also work in NetBeans if you prefer.

(1) Predict what will be predicted by this method.
      After making a prediction on paper, copy the each
      method into a Java compiler and test it.

void setup()
{
   counting(10);
}

void counting(int num)
{
   if(num == 1)
   {
      println(num);
   } 
   else
   {
      counting(num-1);
      println(num);
   }  
}

(2) (a) Write a simple iterative loop that prints 1,3,5,...,97,99.

      (b) Write a recursive method, similar to #1 above,
             that prints  1,3,5,...,97,99

(3) (a)  Trace the following method an predict what it will print
           when it starts with:  mystery(4,2);

void setup()
{
   int m = mystery(4,2);
   println(m);
}

int mystery(int a, int b)
{
   if(b==0)
   {
      return 1;
   }  
   else if(a==0)
   {
      return 0;
   }
   else
   {
      int first = mystery(a-1,b-1);
      int second= mystery(a-1,b);
      return first + second;
   }
}

     (b)  Now copy the method into a Java editor and test your prediction.

     (c)  State values for A and B so that  mystery(A,B) ==> 0
           State values for C and D so that  mystery(C,D) ==> 1

Recursive Binary Search - 11 Oct 2012

We will write a binary search method -
both an iterative version and a recursive version.
Start with this Processing program below.
Homework : Write the RECURSIVE binary search method and test it.

import java.io.*;

int max = 1000000;
int[] nums = new int[max];

void setup()
{
   makeNums(max);
 

   show(0,10);

   println( nums[500000] );
   show(999990,999999);

   find(99);
   find(123456);

//   binSearch(99);
//   binSearch(123456);
}


/*****************
  void binSearch(int target)
  {
   int first = 0;
   int last = max-1;
   while(_______________)
   {
      int mid = _______________;

      if( nums[mid] == target )
      {
         println("binsearch Found " + target + " at pos. " + mid);
         return;
      }
      else if( target < nums[mid] )
      {
         ______________________;
      }
      else
      {
         ______________________;
      }
   }
   println("binsearch missing " + target);
  }
*******************/

void find(int target)
{
  for(int x=0; x < 1000000; x++)
  {
    if(nums[x] == target)
    {
      println("Found " + target + " at pos. " + x);
      println("Previous : " + nums[x-1]);
      println("Following: " + nums[x+1]);
      return;
    }
  }
  println("Missing " + target);
}

void makeNums(int howMany)
{
  nums[0] = rand();
  for(int c=1; c < howMany; c++)
  {
    nums[c] = nums[c-1]+rand();
  }
}

int rand()
{
  return (int)(Math.random()*20 + 1);
}

void show(int first, int last)
{
  for(int c=first; c <= last; c++)
  {
     println(c + " : " + nums[c]);
  }
}

Practice with Recursion - 9 Oct 2012

Minesweeper

Play the game Minesweeper. 

Finding Prime Factors

Here is a recursive method that searches for prime factors of a number:
(written for Processing)

void setup()
{
   primeFactors( 420 );
}

void primeFactors( int num )
{
   int c = num - 1;
   while( c > 1 )
   {
      if( num % c == 0)
      {
         primeFactors( c );
         primeFactors( num / c );
         break;
      }
      c = c-1;
   }
   if(c == 1)
   {  println( num ); } 
}

Here is an iterative method for finding the prime factors of a numbers.

void setup()
{
   primeFactors( 420 );
}

void primeFactors( int num )
{
   for(int p = 2; p <= num; p++)
   {
      if(num % p == 0 && isPrime(p) )
      {
         println(p);
      }
   }
}

boolean isPrime(int p)
{
   for(int c = 2; c < p; c++)
   {
      if(p % c == 0)
      {
         return false;
      }
   }
   return true;
}

Searching for Files

Here is a method that recursively counts files in a folder and all sub-folders:
(written for Processing)

void setup()
{
   println(countFiles(new File("c:\\temp")));
}

int countFiles(File f)
{

    if (f.isFile())
    {
      println(f.getName());
      return 1;
    }
    else
    {

     // Count children & recurse into sub folders

      println("== " + f.getName() + " ==");
      int count = 0;
      File[] files = f.listFiles();
      for (File fileOrDir : files)
      {

        count += countFiles(fileOrDir);
      }
      return count;  
    }

}

 
Here are some more examples of recursion:
http://www.toves.org/books/java/ch18-recurex/index.html

Tower of Hanoi - Recursive Auto-solver - 8 Oct 2012

Towers of Hanoi with Auto-solve
You can download the source files here : Hanoi.java  EasyApp.java
and then run the Hanoi file in DrJava.

Or use this web-site with it's Java Applet (but no source code)
Web-site with simulator and explanation.

Stacks and Queus Quiz , Recursive Algorithms - 27 Sep 2012

1.  Quiz
2.  Watch this video  -  Towers of Hanoi
3.  Try to solve the Towers of Hanoi - http://wipos.p.lodz.pl/zylla/games/hanoi5e.html
4.  Try this simpler puzzle - http://www.novelgames.com/flashgames/game.php?id=54&l=e

Homework - Can you solve the missionary/cannibal puzzle with 4 missionaries and cannibals?
                    If so, is the solution in any way connected to the problem with 3 of each?

After the break - recursive thinking.

Counseling Queue and Stack - 26 Sep 2012

Here are the finished programs - they will run correctly in DrJava

CounsellingQ     CounsellingStack

Quiz tomorrow on Stacks and Queues

Stacks and Queues - 24-25 Sep 2012

Data Structures (you read this last week)

Counselor Prototype    Download DrJava

Better queues for the Counselor

Segway as an Abstract Vehicle Type - 21 Sep 2012

Segway Promotional Film

Segway Film - damaged sound-track

Segway 2 seater

Segway Crashes

Segway Spoof Film

Data Structures - Stacks and Queues - 19 Sep 2012

Read this before next class: Data Structures
In class today, you can either do this reading
or work on your Stage A, as you choose.

Writing Stage A of the Project - 11-14 Sep

You will be working on Stage A of your project in class this week.
Be sure to talk to your intended user before starting to write your documentation.
Use the class time to write the required documentation, and to ask questions
and avoid wasting time and effort doing the wrong thing.
The following notes might be helpful:

Stage A Checklist   IA Dossier Notes   Sample SL Project

Remember that the entire Stage A documentation is due Mon 24 Sep 2012.

Finish Discussing Zonker - Big O Notation - 7 Sep 2012

We will finish discussing Zonker's File Fable, especially discussing Big O notation.
Here are some further notes about Big O notation.

Next week you should plan on working on your project during class.
That means you will be writing stage A. 

So you need to have already had discussions with your intended user
and taken notes that will be the basis of your user stories.

Take the opportunity to ask questions during class to make sure you are doing the right thing(s).

Binary Search vs Linear Search - 6 Sep 2012

What does "Big O notation" mean?
What is O(log n) ?
See page 12 in Zonker's File Fable

Zonker's File Fable - 3-4 Sep 2012

Read Zonker's File Fable
http://ibcomp.fis.edu/files/zonker.pdf

Dossier Projects - 30 Aug 2012

IA Dossier Notes 
We will discuss your project topics.
Stage A Checklist

Inserting in Linked-List ADT - 27 Aug 2012

We will discuss inserting nodes into a Linked-List to make a sorted list.

*** WARNING! Room Change ***

During the week of 27-30 Aug, our class will meet in

  ROOM 264

We will actually be in room 263, but you must enter through 264.
There will still be a written test on Tuesday 28 Aug.

Sorting a Linked-List - 24 Aug 2012

Sorting a Linked-List
It is possible to perform a Bubble Sort on a Linked-list.
But it is VERY inefficient, although swapping neighbours in a Linked-list
is more efficient than swapping neighbours in an array.
 

A better idea is to use ALPHABETICAL  INSERTION when adding new nodes.
If you always do this, then each new addition requires at most N steps (for a list of length N).
This isn?t actually more efficient in terms of total time, but the total processing time
is spread out over a longer period of real time, so it seems faster. 

This approach is called INCREMENTAL ? we do a little bit of work, then a bit more later, etc.

It?s tricky to program, so we will do this in class on Friday 24 Aug, and at the same time
look at how to actually USE a Linked-list ADT in a real program.

Linked-List ADT - 23 Aug 2012

Continue programming a nice Linked-List ADT.
Add any of the methods described here:

Get good at writing methods.  We will practice TRACING such methods tomorrow.

== Test Announcement ==

We will have a written test on Tuesday, 28 Aug.  You will need to be able to:

Linked-List ADT - 22 Aug 2012

We will discuss how to make an ADT (Abstract Data Type)
that implements a Linked-LIst.

Here is an overview of the idea of an ADT (Abstract Data Type)
for a Linked-List.

Linked-List Delete - 21 Aug 2012

We will discuss how to DELETE a node from a linked-list
by searching for a specific data value.

We did DELETE BY POSITION in class.

Homework :
Write a method for DELETE BY NAME - this inputs a name like "Carla",
searches through the list, then changes the PREVIOUS pointer
to point at the node AFTER Carla.  Include as much error-prevention
as is necessary to prevent obvious errors.  For example, if "Carla"
is not in the list, then nothing should be deleted.

Inserting and Deleting in Linked-Lists - 20 Aug 2012

One major advantage of linked-lists over arrays is that inserting and deleting can be done very efficiently, as it only requires changing a few links rather than moving a lot of data around. 

The teacher will demonstrate programming this in class, based on the following notes:
http://ibcomp.fis.edu/linklist/LinkList.html

Here are comprehensive notes about linked-lists.

Here is another set of notes : Linked lists in Java

That is probably too-much-information, but you might find the diagrams helpful.

Homework -
Create a NetBeans project
for the sample program.
Make a Button for each method.
Add a method to INSERT ALPHABETICALLY, as the teacher demonstrated.
We will do DELETING BY NAME next time.

Practice Linked-Lists - 16 Aug 2012

Write a method (attached to a Button) for each of the following:

Write as many of these methods as you can.

Linked-lists - 15 Aug 2012


Read about linked-lists here.

Here is a sample program using a linked-list.

Homework -
Copy the FUNCTIONAL METHODS from the sample program above,
into a NetBeans program with 3 Buttons that
  [Add First Song]
  [Add Last Sont]
  [Show All Songs]
Test that it works as the teacher demonstrated.
Don't break it - bring a working program to class tomorrow.