Entry to Computer Science 200 Level Courses: Self-test

Prerequisites

The 200-level courses all have COMP 103 (and therefore COMP 102 also) as prerequisites. Students given entry to 200-level courses are responsible for ensuring they know the COMP 103 material. This document describes the content of COMP 102 and COMP 103, and contains a self test covering the important material of COMP 103. We recommend that prospective 200-level students who have not taken COMP 103 take this test seriously, and spend as many hours as necessary to be sure that they are familiar with this material.

COMP 102: Design of Computer Programs

COMP 102 covers the basic structures of programming, using an object oriented language (Java).

• Sequence, selection, iteration
• Classes, objects, methods, interfaces
• strings, arrays, files
• The basic principles of object oriented design
• Recursive procedures and functions

If you are not sure that you have covered this material, then you will benefit from taking COMP 102. Most people who have professional programming experience do not need to take the course. The course requires a total of 70-100 hours of practical programming in the laboratory. If you have spent less than 70 hours on actual programming in a general, high level language, then you almost certainly need to take COMP 102. However, some people have spent much more time than this on elementary programming without covering all the material in COMP 102. Programming in specialised, application-based languages is not generally an acceptable substitute.

COMP 103: Data Structures and Algorithms

The following questions provide a self test to determine whether you are familiar with the material in COMP 103 that is a prerequisite for our 200-level courses. We will not mark this test -- if you can do it, you will be able to check the answer yourself by writing and running test programs. You may need to refer to a text book if you are not familiar with the definitions of the terms used or the concepts. The language you use is not important, as long as it supports dynamic data structures (pointer-based structures). If at all possible, it should be an object oriented language such as Java or C++. If you are not familiar with most but not all the topics, then you can probably learn the parts you do not know from a text book. The current text for COMP 103 is Java Foundations, by Lewis, dePasquale and Chase, published by Addison Wesley. There are many other texts on data structures and algorithms that cover the same material.

Note that these questions do not cover all the material in COMP 103: they are focussed on the programming competence that is required for our 200-level courses. Note also that if you merely read the questions, you are unlikely to test yourself adequately -- unless you have written such code before, you will need to write and test the code.

Self Test

Write the code for the following questions in Java. Our 200-level courses assume that you know Java.

Collections and Enumerations/Iterators

Write a program that uses an Enumerator or an Iterator to print out all the items in a collection.

Sorting Algorithms

Write programs that implement two sorting algorithms for sorting items stored in an array. One should be an O(n²) algorithm (eg, insertion sort and selection sort) and one should be an O(n log n) algorithm (eg, Quicksort, Heap sort, and Merge sort). You should also know what O(n²) and O(n log n) mean.

Linked Lists

Write code that includes the type declarations for a linked list and procedures for

• Inserting an item onto the end of a linked list.
• Inserting an item in the middle of a linked list (arguments are the list and a pointer to the node to insert the item in front of).
• Deleting an item from a linked lists (arguments are the list and the item). It should handle the case when the item to delete is the first item in the list.

What would be the advantages and disadvantages of using a doubly linked list rather than a singly linked list?

Queues and Priority Queues

Write code for two implementations of a queue. The code should include the type declarations and procedures for initialising a queue, enqueuing and item, and dequeuing an item. One implementation should use an array; the other should use a linked list. Both implementations should have a constant cost for enqueuing and dequeuing (neither action should involve looking at all the elements of the queue).

Write code implementing a priority queue. Identify which operations are fast (O(1) or O(lg(n)) time) and which are slow (O(n) time) in your implementation.

Binary Search Trees

Write code that includes the type declarations for a binary search tree (BST) and procedures for

• Initialising a BST
• Inserting an item into a BST
• Finding an item in a BST.
• An inorder traversal of the tree to print the items in order.

You should assume that the items are Objects. You should use a dynamic structure, not an array. Note that a BST is not the same as the binary search algorithm.

What are the worst case and average case costs of finding an item in a BST?

Trees

Write code that includes the type declarations for a general tree (nodes may have any number of children) and procedures for both breadth first traversal of a tree and depth first traversal of a tree.

Heaps

Write code that implements a priority queue using a heap (partially ordered tree in an array), allowing efficient enqueuing and dequeuing.

Hashing

Write code for inserting and retrieiving an item from a hash table. You may assume that the items are Objects that implement Comparable. Assume each bucket of the hash table holds at most one item. You may use linear probing (if a bucket is full, try the adjacent bucket). You should choose an appropriate hash function.

How full can your table get before the cost of insertion becomes unacceptably high?