Computer Science 159.102 Course Outline, Semester 2 - 2010


To take this paper you must have taken 159101 and obtained a D grade or higher.

Introduction

Computer science is a wide-ranging, quickly changing, discipline. In 101 you were introduced to one of the skills needed by a computing professional: the fundamentals of programming. You should know from that course that programming is essentially a form of problem solving. To be able to properly use computers to solve problems you need to understand their functioning, capabilities and limitations. In 102, as well as continuing to develop your programming skills, you will be introduced to some of the scope of the discipline.

A computer program consists of operations and data. The organisation of data is a very important part of programming. In 102 we will look at representations for data and how data may be structured. A thorough understanding of data structures will allow you to write programs that are more efficient and can solve more complex problems.

A computer program needs physical hardware in order to run. Although it is not usually necessary to understand the complete workings of a computer, some basic knowledge is helpful. We will look at how the structure of a computer is organised and how data may be manipulated at a very low level.

The computer programs you write do not run on top of computer hardware by themselves. Rather, they require the support of various services (provided by other programs). Specifically, code that you write must be converted into a form actually executable by the hardware and then the computer's resources must be shared amongst the running programs. This is common to all computing systems. You require some understanding of the environment in which your programs execute to be able to write successful programs.

Computers are not all-capable. There are limits to what they can achieve. There are some problems for which no computer solution is possible. For those problems which can be solved by computers, some solutions are better than others. Some of the problems which cannot be solved using computers are not obviously unsuitable for computers and you should be aware of them if you are to avoid fruitless efforts to solve them. The study of the limitations and capabilities of computing systems, of necessity, requires precision and a theoretical approach. This includes comparative evaluations of the worth of various solutions to those problems which are amenable to computing.

Computers are put to many and varied uses. One of the more interesting, is artificial intelligence. A brief overview of this area will give, in practical terms, some indication of the capabilities of computers and the uses to which they are being put.

Programming is not a skill easily learnt. It requires practice. There are various structures and techniques which are very useful in the formation of algorithms. You will be introduced to some of these during this semester and given the opportunity to practice their use. This will, obviously, also give you more practice in the general skill of programming. It is only by consistent practice that you will become a competent programmer.

Texts and Notes

Brookshear, J.G., Computer Science: An Overview. It is highly recommended that you buy this book.

Lecture Notes for the course are available from http://cs-alb-pc3.massey.ac.nz  I will not follow these notes exactly and notes you take in lectures should be quite different although covering the same material.

Assessment and Attendance

The course will be assessed by a combination of practical and theoretical work.
There will be 5 practical assignments, a mid-semester test and one three hour exam. The exam will account for 60% of the total mark, the test 15% and the assignments will account for 25%.
Lectures: 3 lectures per week. Attendance is not compulsory, but students are warned that in most cases non-attendance will not improve their final grade.
Tutorials: Each student should attend 1 tutorial per week, tutorials are again not compulsory but it is your best opportunity to ask questions, test yourself and work through examples.



Course Schedule

This is a rough plan, the course may not conform to this schedule.

1 - Data Storage
Data storage: The binary number system,
hexadecimal notation,  characters and strings,
integers. Floating point numbers. Round off errors.
Arithmetic Operations: addition, subtraction,
multiplication and division.
Logical Operations: AND, OR, NOT, XOR.
2 - Data Manipulation
Logic gates, combinational and sequential logic.
Addition and subtraction.
The CPU: datapath, control unit, execution cycle.
3 -The CPU
The instruction set, instruction types,
assembly language.
Input/Output: memory mapped, interrupt driven.
RISC/CISC, Parallel Computers.
4 - Data Structures
Data Structures: arrays, lists, queues, stacks, trees.
Implementations of data structures.
Abstract Data Types.
5 - Algorithms
Iteration and recursion: sequential search and
binary search.  Sorting algorithms.
6 - Languages
Syntax definition, BNF, terminals, non-terminals.
Interpretation and compilation.
Paradigms: imperative, functional, declarative.
7 - Computation
Computability, Turing machines, Church-Turing
thesis,  the halting problem, non-computable
problems,  partially computable problems.
Complexity theory, computer resources,
Big O notation, complexity of algorithms
Correctness
8 - Operating Systems
Process Management: Multitasking, scheduling.
Memory Management: Physical and virtual
memory, swapping  File Management:
File systems, file system interface.
9 - Artificial Intelligence
Search Methods
Heuristics



Submission of Assignments

There are five assignments to be completed.  All of the assignments will be programming tasks.
A large part of the course is practical work and to ensure a good grade you should attempt all assignments. It is OK for you to be helped by other students with the assignments, but it is not OK for you to blindly copy other students work. All submissions are tested for plagiarism and copied assignment will get zero marks. If you can explain how your solution works I will give you the marks back.
All assignments will be marked out of 10, marks will be awarded for any work handed in.


 M Johnson 2010