Skip navigation
The Australian National University

Introduction to Advanced Computing II COMP1140

Course overview

Course description

This course includes COMP1110 and extends it with 12 one-hour lecture/tutorial/laboratory sessions. It introduces students to various areas of research in computer science, especially those research areas represented in the School of Computer Science, other than those covered in COMP1130. A number of research groups in the School will be responsible for various parts of the course. Each part will consist of some introductory lectures on the data structures and algorithms most relevant to the research area and an overview lecture on the research problems, techniques, and applications of the area. These topics will include graphs, sets, probability,  propositional logic and data modelling.

Rationale

For students already with a background in (procedural) programming, this first course on the curriculum for the BInfTech and BSEng degrees provides them with a grounding in object-oriented programming. The course is based on the conviction that modern object-oriented methods can deliver software systems that are extendable, reusable and reliable, across a wide range of problem domains.

Industrially relevant problems typically require programs of a size and complexity that renders undisciplined approaches to their construction destined to failure. This course also teaches the fundamental strategies of abstraction, decomposition and reuse as methods for overcoming these problems.

Ideas

This course will carry the main responsibility for:

  • the main concepts of an object-oriented programming language and their implementation in Eiffel,
  • program maintenance and development using an editor (Emacs) in the context of a conventional operating system (Linux),
  • the systematic use of an agreed programming style (layout, name convention, documentation),
  • introducing the general idea of abstraction as a tool for combating complexity in systems (data abstraction, design by contract),
  • developing a stepwise refinement approach to implementing large programs,
  • describing the software development life-cycle as a model of the process of software construction, and
  • introducing formal systems and notations as software-engineering tools.

Topics

The following topics will be covered:

  • a review of the basic concepts of imperative programming,
  • the principles of object orientation,
  • the basic Eiffel classes (BOOLEAN, INTEGER, CHARACTER, REAL, DOUBLE) and library classes (STRING, ARRAY),
  • the run-time structures of Eiffel (object store (heap), activation stack, current object, memory management),
  • elements of algorithms (techniques using iteration, loop invariants, simple solutions to search and sort problems),
  • abstraction mechanisms (assertions on routines, design by contract, assertions on loops, assertions on classes) and extendibility mechanisms (class inheritance, generic classes),
  • basic data types: enumerations, lists, stacks, queues, tables, arrays, graphs, sets; their algebraic properties and use in problem solving,
  • data structures,
  • sorting and searching: serial and binary searching, O(n*n) sorting algorithms,
  • recursive algorithms: comparison with iteration, connection with induction,
  • simple regular expressions,
  • fundamental problem solving, and
  • software quality: unit testing strategies, pre- and post-conditions, loop and class invariants.

Technical skills

Upon completion of the course the student will be able to use a modern GUI-based computer system (Unix, CDE) to perform the following tasks:

  • effectively use web, news and email utilities,
  • construct directory subsystems to support laboratory and assignment tasks,
  • use a modern editor system (Emacs) to write simple text documents, and compile and execute Eiffel programs (GnuEiffel compiler system),
  • use the wild-card expansion facilities of the shell to match multiple files,
  • use the UNIX grep tool to find files containing targeted regular expressions, and
  • proficiently use Emacs to edit Eiffel programs and to view the short forms of Eiffel classes.

Textbooks

Alfred V. Aho and Jeffrey D. Ullman, Foundations of Computer Science, C Edition, 1995.

Workload

Forty two one-hour lectures, ten two-hour tutorial/laboratory sessions.

Responsible Officer:  JavaScript must be enabled to display this email address. / Page Contact:  JavaScript must be enabled to display this email address.