Higher Level
IB Computer Science
Schedule
2nd Semester

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

Begin to prepare the binder that contains your dossier.

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.

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

Printing dossier materials to be inserted in binder.

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 35_BIB. A grade out of 35 is submitted to the IBO which is applied toward the Computer Science Certificate.

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.

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.)

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.

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.

• 1: Introductory Digital Concepts
• 2: Number Systems, Operations and codes
• 3: Logic Gates
• 4: Boolean Algebra and Logic Simplification
• 5: Combinational Logic
• 6: Functions of Combinational Logic
• There is no Workbench tutorial for Chapter 7.
• 8: Flip-flops and Related Devices
• 9: Counters
• 10: Registers

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).

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:

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 10² = 100, then log₁₀ 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!

Algorithm Efficiency & Sorting	Searching	Hashing	Book Cover	Reference
390-437	51-53 78-87 402-403	598-617 682-685		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. 1999. C++ An Introduction to Data Structures (Prentice-Hall, Inc.: Upper Saddle River, NJ)
303-318	319-324	324-333		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. 1997. C++ How To Program Second Edition (Prentice-Hall, Inc.: Upper Saddle River, NJ)

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.

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.

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:

• JVALL Package
• General Linked List Operation
• Linked List Implementation of a Stack

To run, type the following from the command prompt:

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

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.

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.

Pages 4 - 15		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. 1999. C++ An Introduction to Data Structures (Prentice-Hall, Inc.: Upper Saddle River, NJ)
--		Richard Jones. 2002. IB Computing Home: Software Life Cycle
--		Shashi Krishna. 2002. Escuela Campo Alegre: Software Development Life Cycle