COMP103A Support Website Home

Kia ora - Welcome

These pages offer support material for the course COMP103 - Introduction to Computer Science 1. Here you will find lecture notes and associated material relating to the both the Concepts and the Programming parts of the course.

NOTE THAT THIS PAGE WAS FOR THE 2005 VERSION OF COMP103. It remains here for historical reasons only, since 2005 was the last year that we taught C++ as the introductory programming language. For current versions of COMP103, see the Department Web Page Teaching Page and click on COMP103.

General information, including the course outline, can be found elsewhere (see the quicklinks above).

What's New

In-class test, Thursday 14th April: here is a sample version of the test for you to practice on.

In-class test, Thursday 14th April: and here are some sample solutions.

Lab Tests: The test problems for the FILES lab test during your lab on Thursday 2nd June are here.
Course representatives are
- Sarah Dawson syd1@waikato.ac.nz
- Troy Dean tald2@waikato.ac.nz
- Gareth Ranger gar7@waikato.ac.nz

Errata

[17 May 2005] There is an error on slide 12 of the lecture notes. The slide says

  so now
  board[0] will describe the entire first row
  board[1] will describe the entire second row
  board[3] will describe the entire third row

The third line should read

  board[2] will describe the entire third row

because the array is indexed from 0 to 2

[21 March 2005] I caused confusion in today's lecture with my use of the word return in two different contexts. I hadn't covered the C++ "return" statement, except to say that programs normally finish with a "return 0" statement. In fact, this statement can be used to terminate the program before reaching the end. "return 1" is used to indicate an abnormal termination, "return 0" indicates a normal one. The "cin.fail()" tests are used in the program I showed to test whether the right kind of input has been supplied and, if not, to terminate abnormally. -- Ian

Lecture Notes

Concept lecture Programming lecture

Mon: ELT G.01 Wed: LG.01 Thu: ELT G.01

Date Title Who Description Resources

7 March Introduction, output Ian How the course is run, C++, C++ program structure, output

9 March Arithmetic operations Ian Integers, floating-point numbers, calculation, input, arithmetic operators

10 March Input, variables, types Ian Characters, ASCII, character input, binary numbers, base conversion

14 March Constants, libraries Ian Constants, #define, libraries, programs that print themselves

These programs print themselves! ...
... sort of
... really

16 March Boolean algebra, logic Ian AND, OR, NOT, Venn diagrams, truth tables, logical rules, precedence

17 March if-else, Boolean expressions Ian Conditional statements, logical operators, compound statements Programs

21 March if-else, the sequel Ian Nested if ... else, use of braces, if-else chains, input validation Programs
Answers

23 March Cryptography Ian
Classical cryptography: Caesar cipher, substitution cipher, Enigma machine, Vigenere cipher, Vernam cipher, digital Vernam cipher
Answers

Play with this simulation of the Enigma Machine!
Enigma
24 March While and do-while loops Steve While loops, do loops, sentinels, tracing programs Programs

28 March Easter holiday

30 March Compression Ian
Ziv-Lempel coding, symbol coding, Huffman coding
Answers

31 March Functions Steve Using functions, structure and syntax, writing a function Programs (predefined functions)
Programs (user defined functions)

4 April Functions and prototypes Steve Prototypes, parameters, functions to reflect program structure Answers to lecture questions

6 April Image coding Ian
Run-length coding, quadtrees, trees, recursive operations on quadtrees
Answers

This demo lets you play with quadtrees
Demo

Octrees are used for computer games programming Octrees

7 April Nesting function calls Steve Function as structure contd, functions calling functions chomp implementations
chomp structure diagram

11 April Switch and for Steve New control structures, examples, recursion (a little bit!) Programs

13 April Error detection and correction Ian
How nois afects ransmssion, eror dtection/crrectin schmes: parity, VRC, LRC, checksum, ISBN, UPC, Hamming codes, forward error correction
Answers

14 April CLASS TEST

18 April Teaching recess

2 May Functions and Reference parameters Steve Recap on functions. Reference parameters. Self-documenting programs Programs

4 May Searching Ian
Searching: linear, binary, interpolation, heuristic, blind, analytic. Pattern searching using skip array
Answers

5 May Arrays 1 Steve Definition, syntax, use, program examples Programs

9 May Arrays 2 Steve Linear Search, Binary Search, Counting Elements of an array Programs

11 May Sorting Ian
Selection sort, bubble sort, merge sort, quicksort, growth functions, performance classes
Answers

Watch these sorting algorithms race each other! Sorting race

CHALLENGE: You'll never understand this sorting algorithm! Trickysort

12 May Strings Steve Representing strings usings arrays of characters Programs

16 May 2D arrays Steve 2D arrays & examples: tic-tac-toe, arrays of strings Programs

18 May NP-hard problems Ian
Characteristics of NP-hard problems, binpacking strategies, scheduling, knapsack problem. Generate and test, heuristic solutions, lower bounds
Answers

Lots more information about the Travelling Salesman Problem
Traveling Salesman Problem

19 May Files Steve Files, streams, buffers. Reading data from text files. Programs

23 May Files Steve More on files, tic_tac_toe with loading/saving Programs

25 May Information systems analysis Ian
Different design cycles, dataflow diagrams, structure charts, perform a case study ...
Answers

26 May Testing Steve Validation, verification, black box & white box testing, automated testing, debugging

30 May Describing algorithms Steve Natural language descriptions, flow charts, pseudo code, guess_a_word game Programs

1 June Public-key encryption Ian
Modern encryption, authentication, electronic signatures, provably secure ciphers

2 June Software Lifecycle Steve

6 June Queen's Birthday

8 June Research in computer science Steve

9 June Review Steve

Date	Title	Who	Description	Resources
7 March	Introduction, output	Ian	How the course is run, C++, C++ program structure, output
9 March	Arithmetic operations	Ian	Integers, floating-point numbers, calculation, input, arithmetic operators
10 March	Input, variables, types	Ian	Characters, ASCII, character input, binary numbers, base conversion
14 March	Constants, libraries	Ian	Constants, #define, libraries, programs that print themselves
			These programs print themselves! ...	... sort of ... really
16 March	Boolean algebra, logic	Ian	AND, OR, NOT, Venn diagrams, truth tables, logical rules, precedence
17 March	if-else, Boolean expressions	Ian	Conditional statements, logical operators, compound statements	Programs
21 March	if-else, the sequel	Ian	Nested if ... else, use of braces, if-else chains, input validation	Programs Answers
23 March	Cryptography	Ian	Classical cryptography: Caesar cipher, substitution cipher, Enigma machine, Vigenere cipher, Vernam cipher, digital Vernam cipher	Answers
			Play with this simulation of the Enigma Machine!	Enigma
24 March	While and do-while loops	Steve	While loops, do loops, sentinels, tracing programs	Programs
28 March	Easter holiday
30 March	Compression	Ian	Ziv-Lempel coding, symbol coding, Huffman coding	Answers
31 March	Functions	Steve	Using functions, structure and syntax, writing a function	Programs (predefined functions) Programs (user defined functions)
4 April	Functions and prototypes	Steve	Prototypes, parameters, functions to reflect program structure	Answers to lecture questions
6 April	Image coding	Ian	Run-length coding, quadtrees, trees, recursive operations on quadtrees	Answers
			This demo lets you play with quadtrees	Demo
			Octrees are used for computer games programming	Octrees
7 April	Nesting function calls	Steve	Function as structure contd, functions calling functions	chomp implementations chomp structure diagram
11 April	Switch and for	Steve	New control structures, examples, recursion (a little bit!)	Programs
13 April	Error detection and correction	Ian	How nois afects ransmssion, eror dtection/crrectin schmes: parity, VRC, LRC, checksum, ISBN, UPC, Hamming codes, forward error correction	Answers
14 April	CLASS TEST

18 April	Teaching recess

2 May	Functions and Reference parameters	Steve	Recap on functions. Reference parameters. Self-documenting programs	Programs
4 May	Searching	Ian	Searching: linear, binary, interpolation, heuristic, blind, analytic. Pattern searching using skip array	Answers
5 May	Arrays 1	Steve	Definition, syntax, use, program examples	Programs
9 May	Arrays 2	Steve	Linear Search, Binary Search, Counting Elements of an array	Programs
11 May	Sorting	Ian	Selection sort, bubble sort, merge sort, quicksort, growth functions, performance classes	Answers
			Watch these sorting algorithms race each other!	Sorting race
			CHALLENGE: You'll never understand this sorting algorithm!	Trickysort
12 May	Strings	Steve	Representing strings usings arrays of characters	Programs
16 May	2D arrays	Steve	2D arrays & examples: tic-tac-toe, arrays of strings	Programs
18 May	NP-hard problems	Ian	Characteristics of NP-hard problems, binpacking strategies, scheduling, knapsack problem. Generate and test, heuristic solutions, lower bounds	Answers
			Lots more information about the Travelling Salesman Problem	Traveling Salesman Problem
19 May	Files	Steve	Files, streams, buffers. Reading data from text files.	Programs
23 May	Files	Steve	More on files, tic_tac_toe with loading/saving	Programs
25 May	Information systems analysis	Ian	Different design cycles, dataflow diagrams, structure charts, perform a case study ...	Answers
26 May	Testing	Steve	Validation, verification, black box & white box testing, automated testing, debugging
30 May	Describing algorithms	Steve	Natural language descriptions, flow charts, pseudo code, guess_a_word game	Programs
1 June	Public-key encryption	Ian	Modern encryption, authentication, electronic signatures, provably secure ciphers
2 June	Software Lifecycle	Steve
6 June	Queen's Birthday
8 June	Research in computer science	Steve
9 June	Review	Steve