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:
- It is
formatted like this sample
- You have a Table Of Contents at the beginning
- You have a List of Mastery Factor Locations at the
end
- Pages are all numbered - recommend A1,A2.. , B1,B2,
... C1,C2... D1,D2
If you have trouble automating the page numbering, you are permitted
to use a pen and number the pages by hand.
- When you print the program listing, print it in LANDSCAPE
mode (sideways)
DON'T copy the program listing into a word-processor, as that is likely
to wreck the formatting or to lose some of the commands.
Print it directly from NetBeans.
- If possible, put a header on every page with your name, the title and
the date
If you cannot figure out how to do this, it is not required.
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-condition : list
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:
- Student Name - created by counselor, stored in scheduling system,
printed on daily attendance page
- P/A/T records - entered by teacher , stored in attendance
database, displayed to office staff
- Reports - created by database manager + data entered by teacher,
stored in attendance DB, output to students and parents
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.
- Explain how the computer recursively counts the neighbors for each
square.
- Examine your own thinking. When you are playing the game,
are you thinking recursively?
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;
}
|
- Which is more efficient - the recursive method or the iterative
method?
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:
- add(String title, String artist, int seconds) // adds at
the TAIL
- first(String title,String artist, int seconds) // adds at
the beginning, before HEAD node
- delete(String title)
- delete(int position)
- sortTitles()
- sortSeconds()
- printAll()
- search(String title)
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:
- read a Linked-List method and explain how it works
- write short Linked-List methods similar to those you have already
written
- answer simple questions about Linked-Lists and pointers
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:
- remove (delete) the first node in the list
- remove (delete) the last node in the list
- delete the last node safely, with appropriate error-checking
for:
- an empty list
- a list with only one node
- SEARCH for a song in the list, and display "FOUND" or "not
found"
- delete the second node in the list, without removing the
first node,
something like this:
temp = start.next.next; //
points to the 3rd node
start.next =
temp; // makes 1st node
point at 3rd node
- remove the first node and attach it at the end -
that is, move the first node to the end of the list
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.
