Higher Level
IB Computer Science
Schedule
2nd Semester


2002Assignment
Feb 1Review Chief Examiner's Report on May 2001 Papers and Dossiers.
Check out IB Web Sites: www.donaldson.org --> International Baccalaureate --> IB Computer Science Sites
Feb 5

In class we overview Donaldson's handout, Interpreting IB Dossier Criteria.

Feb 6

Begin to prepare the binder that contains your dossier.

Click here for Dossier Requirements
Feb 7

IB Computer Science candidates should note the Dossier Evaluation Scheme against which the IB Computer Science dossiers are evaluated.

Inspection of this scheme demonstrates that it is crucial to appropriately include nine of the eleven master techniques in order to maximize the dossier mark. Knowing this, it is prudent to include ten or even all eleven techniques in case one of the included techniques is not deemed to be appropriate.

To be appropriately included, a mastery technique must be applied in a non-trivial way in the dossier program.

Feb 11

Section J of the dossier is due at the beginning of class.

Click here for pdf version of this day's assignment.
Mon
Feb
19

Printing dossier materials to be inserted in binder.

Mon
Feb
25

Dossier Evaluation Sheets - pdf version
Dossier Evaluation Sheets - WordPerfect

We worked on preparing dossiers. Dossier Evaluation Sheets were updated to reflect weightings for both IB (unchanged) and Alberta Learning grades. Students receive two separate grades. A percentage grade is submitted to Alberta Learning in the Alberta course Computer Science 35BIB. A grade out of 35 is submitted to the IBO which is applied toward the Computer Science Certificate.

Tues
Feb
26

Case Study Essay Assignment - pdf format
Case Study Essay Assignment - WordPerfect

Discuss the Case Study Essay Assignment due Monday, March 11, 2002.

Wed thru Fri
Feb
27 thru Mar 1

Ms. Armande Bird will substitute.

Student's will read and study the Case Study.

Read up on evolution generally and the Tyrol Iceman specifically.

Mr. Donaldson attends the SIGCSE 2002 Conference in Cincinnati during February 27 through March 3, 2002.

Click here to see pdf file of Mr. Donaldson's Personal Conference Schedule.

SIGSCE is the ACM Special Interest Group on Computer Science Education. The ACM, or "Association for Computing Machinery", is the world's oldest educational and scientific computing society. It was founded in 1947.

Mon
Mar
4

ENTIRE DOSSIER DUE BY END OF DAY!!

The entire dossier was originally due on Tuesday, February 19, 2002. That date was changed to today due to classes being cancelled because of the teachers' strike and Mr. Donaldson attending a conference for most of the following week.

Click here for Dossier Requirements.


Number Systems and Representations

IB Objective: Express integer numbers in any base including decimal, binary, hexadecimal.

IB Objective: Convert integer numbers from binary to hexadecimal and vice versa, binary to decimal and vice versa.

Our Objective: Convert integer numbers from any base to any other base.

IB Objective: Add and subtract integer numbers in binary and hexadecimal.

Our Objective: Add and subtract integer numbers in any base.

Our Objective: Multiply and Divide integer numbers in any base.

IB Objective: State the mantissa and exponent of a number in floating-point representation.

IB Objective: Apply binary notation to represent real numbers. Both fixed-point and floating-point, both un-normalized and normalized, representations are required.

IB Objective: Define truncation error, underflow error and overflow error. Outline one situation when and where each one of these errors can occur.

IB Objective: Discuss the advantages and disadvantages of integer and floating-point representations.

IB Objective: Explain how data types other than integers and floating-point numbers may be represented by bit patterns including characters (both ASCII and ISO/OSI), Booleans and colours. (Recall of specific codes is not required.)

Mon
Mar
11

Case Study Essay Assignment - pdf format
Case Study Essay Assignment - WordPerfect

Case Study Essay Assignment is due.

Tues
Mar
19

We begin with Boolean Logic today. Handouts included:

  • Chapters 3 (Binary Logic Gates), 4 (Using Binary Logic Gates), and part of 10 (Arithmetic Circuits) from Roger L. Tokheim, 1993, Digital Electronics (McGraw-Hill Publishing Company: Toronto).
  • Notes by Gerry Donaldson from prior years.
  • Richard Jones' treatment of IB - Boolean Logic as found on his web site, IB Computing Home.
Wed
Mar
20

We will practice Boolean logic using Electronic Workbench Version 5.12

We look at some of the nine tutorials by Ron Reis of Los Angeles Valley College entitled Computer Simulation of Digital Circuits found on a Prentice-Hall companion web site to the textbook, Digital Fundamentals Seventh Edition by Thomas L. Floyd.

Thurs
April
1

Measuring Efficiency By Comparing Searching and Sorting Algorithms

& Replacing Searching Algorithms With Hash Tables

Subtopics focus on tracing and constructing algorithms that perform a quicksort (5.2.1, 5.2.2), hash tables including the generation of addresses using modulo arithmetic and the handling of clashes by locating next free space (5.2.3), the use of hash algorithms to save and retrieve records in a direct access file (8.1.7) and algorithmic evaluation of non-recursive algorithms for linear and binary searches as well as the bubble sort, selection sort and quick sort (topic 5.6).

REMEMBER TO RECOGNIZE THESE ALGORITHMS AS "IB-PURE" PSEUDOCODE!!

Assignments Due Monday, April 8, 2002: Read Walls & Mirrors chapter 9, pages 390 - 432. From Exercises on pages 433 - 435, do excercises 1-4, 7-11, 15, 17-19. Read Walls & Mirrors chapter 12, pages 598 - 617. Do exercise 12 on page 626. Read Walls & Mirrors chapter 14, pages 682-685. Read ECA's Basic File Organization Techniques. Read Nyhoff's Intro to Data Structures section 9.3, pages 482-486. Do all the exercises 1-6 on pages 486-487.

One of the most playful areas of Computer Science is the study of efficiency by comparing various searching and sorting algorithms. Some are faster than others. We can't just measure the speed of a couple algorithms on a specific platform because the architecture of that particular platform may favour one algorithm over the other. So we have to find ways of comparing the algorithms themselves without reference to platform.

That said, we immediately start visually comparing the executions of various algorithms on specific platforms because this gives us intuitive experiences that we can later think with when we intellectually compare the efficiency of algorithms with mathematical tools. So long as we don't confuse platform performance with algorithmic performance, it is fun and useful to play with empirical executions of the algorithms.

I discussed this topic and provided examples of sorting in 1998 at C++ Sorting Algorithms. The concept that must be internalized and applied is Big O as a measure of algorithm efficiency. The IB Syllabus objective 5.6 specifies that students must be able to state and analyse the efficiency in terms of Big O of the following non-recursive algorithms:

AlgorithmBigO Efficiency
Linear SearchO(n)
Binary SearchO(log n)
Bubble SortO(n2)
Selection SortO(n2)
Quick SortO(n log n)

You'll notice that the size of Big O measures are often expressed in terms of exponents and logarithms.

Linear Performance: This is the world that our ancestors lived in. You could run a wee bit faster than your friend, but never twice as fast.

Logarithmic Performance:Logarithmic functions sometimes confuse us because we don't use that sort of language every day, but the first log tables were invented by the Scottish mathematician John Napier (1550 - 1617) to simplify long and complicated calculations. In order to multiply a couple of numbers, you just added their logarithmic values. To divide, you substracted the values. Then you located the result in the table and read the corresponding quotient.

A logarithm is the power to which one number must be raised in order to obtain another number. The first number is the base. Since 102 = 100, then log10 100 = 2. Read this as log to the base 10 of a hundred equals 2. We use the fact that multiplication and division of powers of a number corresponds to the addition and subtraction of these powers.

For a more thorough explanation of logarithms, check out Its The Law Too - The Laws of Logarithms.

Exponental Performance: This is the world that we now live in. Cooper's Law tells us that "the number of "conversations" (voice or data) that can theoretically be conducted over a given area in all of the useful radio spectrum ... has doubled every two-and-a-half years for the past 104 years." This exponential relationship is something that humans have only experienced in the last century. It's the sort of thing that Buckminster Fuller was thinking about when he described the function of "acclerating accleration". Now that's fast!


World Wide Web Stuff On Big O


Textbook Stuff

Algorithm Efficiency & SortingSearchingHashingBook CoverReference
390-437 51-53
78-87
402-403
598-617
682-685
[Frank Carano, Paul Helman and Robert Veroff:
               Data Abstraction and Problem Solving with C++:   Walls and Mirrors] Carrano, Frank M. and Paul Helman and Robert Veroff, 1998. Data Abstraction and Problem Solving with C++: Wall and Mirrors (Addison Wesley Longman, Inc.: Don Mills, Ontario)
349-364
573-620
354-362
316-318
720-724
482-487 [Larry Nyhoff:  C++ An Introduction to Data Structures] Larry Nyhoff. 1999. C++ An Introduction to Data Structures (Prentice-Hall, Inc.: Upper Saddle River, NJ)
303-318 319-324 324-333 [John Hubbard:  Schaum's Outline of FUNDAMENTALS OF COMPUTING WITH C++] Hubbard, John. 1998. Schaum's Outline of FUNDAMENTALS OF COMPUTING WITH C++ (McGraw Hill: Toronto)
245-252
280
281
353-354
450
742
984
[Harvey & Paul Deitel:  C++ How To Program Second Edition] Harvey & Paul Deitel. 1997. C++ How To Program Second Edition (Prentice-Hall, Inc.: Upper Saddle River, NJ)


Visual Representations of Searching and Sorting Algorithms

I became intrigued with sorting visualizations years ago with Doug Cooper's 1992 Pascal ShowSort Project but somehow left such dramatic representations on the back burner until I attended the 2002 SIGCSE Conference where I attended workshops using manipulatives with toys and robots. Using manipulatives and visualizations is so much fun that I decided to experiment with a number of resources in our coverage of sorting algorithsm.

Internet Explorer 6+ Needs Sun's Java Plug-In.
Most of the following visualizations are Java appelets. In order for a Java appelet to run under IE 6+, you must install Sun's Java plug-in.

Some Appelets Need the Tool Command Langauge (Tcl) Plug-In.
The Tcl Web browser plugin provides an easy alternative to Java programming for client-side web applications. Download it from here. Note: If the Tcl applet doesn't run in the IE 6 browser (my didn't), then download the applet and run it separately in the Tcl application. That worked for me.

One site which describes itself as The Complete Collection of Algorithm Animations provides links to oodles of them.

Algorithm Animation (National Institute of Advanced Industrial Science and Technology, Japan) http://www.aist.go.jp/ETL/~suzaki/AlgorithmAnimation/index.html
Sandeep Mitra's Sorting Animation Page (SUNY Brockport) http://www.cs.brockport.edu/cs/javasort.html
Sorting Algorithms: This page lets you simultaneously run multiple demos so that you can compare them. (University of British Columbia) http://www.cs.ubc.ca/spider/harrison/Java/index.html
The Sorter visually animates various sorting algorithms, using QuickTime movies. (Robb Cutler at The Harker School) http://users.harker.org/hs/robbc/Software/TheSorter/TheSorter.htm
Sorting Algorithms animations illustrate a number of different sequential and parallel sorting algorithms. http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
The JAWAA Home Page features Java and Web based algorithm animation. http://www.cs.duke.edu/csed/jawaa/JAWAA.html
Thurs
April
8

Great Site For Study of

Data Structures and Algorithms

This is most impressive site that I have found to date for studying Data Structures and Algorithms. The explanation and animation of Quick Sort and hash tables is what really grabbed my attention at first. Upon further inspection I realized that this site covers most of the tough programming stuff (and more) for Higher Level IB Computer Science. Go for the animations. They really are stupendous.

Thurs
April
11

Web Assignments Due May 1, 2002

Fri
April
12

Visualization of Linked Lists

I read about this one in the proceedings from the SIGCSE Conference that I attended in Cincinnati this month. (The term "proceedings" in this context refers to a book published by the Conference that contains articles on the sessions offered at the Conference. It animates linked lists used in the Java programming language, but the visualization applies equally well to C++ as the concepts are virtually the same.

If you want to grab the files from this site, just click:

To run, type the following from the command prompt:

java -jar generalStand.jar
java -jar stackStand.jar

Mon
April
22

I have placed in one table links to all web sites of IB's Higher Level Computer Science Syllabi authored by Churchill students. Click on Past SWC Syllabi Web Sites.

Mon
Apr
22

Syllabus Topic 6: Further System Fundamentals

Topic 6.1: Processor Configuration

Processor Configuration

Computer Memory

Interrupts

IB Computing Home

Escuela Campo Alegre

Escuela Campo Alegre

Topic 6.2: Machine Instruction Cycle

Machine Instruction Cycle

Fetch & Execute Cycle

Instruction Execution Cycle

IB Computing Home

Eck's Intro Programming

Escuela Campo Alegre

Topic 6.3: Disk Storage

Topic 6.4: Operating Systems and Utilities

Operating System

Escuela Campo Alegre

Topic 6.5: Computer/Peripheral Communication

Handshaking/Communications Protocol

Direct Memory Access

Controller

Escuela Campo Alegre

Escuela Campo Alegre

Escuela Campo Alegre

Wed
April
24

Objective 1.1: Software Life Cycle

Assignment Due Friday, 26 April 2002: Compare the life cycles and the descriptions of their phases for the following four sources using a five column table, one column for each source and one column that brieflydescribes the phases.

Carrano et alNyhoffIB Comp HomeECADescription
SpecificationProblem Analysis & Specification -- -- Bring precision and detail to the original problem statement
-- -- -- Concept Formation Create objectives & limits of project.
-- -- Systems Analysis -- fact finding
-- -- -- -- --

Pages 4 - 15 [Frank Carano, Paul Helman and Robert Veroff:
               Data Abstraction and Problem Solving with C++:   Walls and Mirrors] Carrano, Frank M. and Paul Helman and Robert Veroff, 1998. Data Abstraction and Problem Solving with C++: Wall and Mirrors (Addison Wesley Longman, Inc.: Don Mills, Ontario)
Pages 1 - 25 [Larry Nyhoff:  C++ An Introduction to Data Structures] Larry Nyhoff. 1999. C++ An Introduction to Data Structures (Prentice-Hall, Inc.: Upper Saddle River, NJ)
-- [IB Computing Home] Richard Jones. 2002. IB Computing Home: Software Life Cycle
-- [Escuela Campo Alegre] Shashi Krishna. 2002. Escuela Campo Alegre: Software Development Life Cycle
Thrs
April
25

Exam Preparation Advice & Schedule


April 26, 2002

Computer Science 35IB
I GOOFED: Do May 2000 Instead

It appears that I have not given everyone a copy of May 2001 IB papers which I scheduled to be corrected on Monday. Therefore, please prepare with Paper #1 and Paper #2 from May 2000 instead. There is a very brief amount of time left. Do not take this weekend off. The time cannot be replaced later.


[Counter On Strike        [Home of Gerry Donaldson's Com Sci Gate]       
[Gerry Donaldson's Email Address]
csgate@donaldson.org
ICQ# 62833374
[EFC Blue Ribbon - Free Speech Online]

URL:   http://www.donaldson.org/    Last Revised:   April 25, 2002