Module 18187.2 (2004)
Syllabus page 2004/2005
06-18187
Foundations of Computer Science
Level 1/C
Paul Levy
Martin Escardo
Martin Escardo
10+10 credits in Semester 1 and Semester 2
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus
The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)
Changes and updates
New module for 2004/05 (effectively replaces Introduction to Computer Science A & B).
Relevant Links
Outline
The module will introduce the fundamental concepts of Computer Science, such as the von Neumann machine, the representation of data in computer memory, programming constructs, data models and data structures and the analysis of algorithms. The ideas will be presented abstractly, although examples will be given in the language used in the parallel programming workshop modules.
Aims
The aims of this module are to:
- introduce the fundamental concepts of Computer Science
- support and underpin the programming modules
- introduce advanced abstract data types and standard operations on the same and demonstrate their various representations based on arrays and pointers
- discuss the advantages and disadvantages of the different representations of data types
- introduce the main algorithms for fundamental tasks such as sorting and searching and examine their complexity
- introduce basic concepts of numerical calculations
Learning Outcomes
| On successful completion of this module, the student should be able to: | Assessed by: | |
| 1 | describe the basics of the von Neumann architecture and how it influences the design of high-level programming language constructs | Examination |
| 2 | explain how the main imperative programming language constructs are realised at the machine level | Examination |
| 3 | explain the importance of abstract models of computation and data | Examination |
| 4 | make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity or considerations of numerical accuracy | Examination |
| 5 | explain and apply data structures such as binary trees, heap-trees, graphs and tables, together with their internal representations and relevant algorithms | Examination |
| 6 | select, with justification, appropriate data structures to ensure efficient implementation of an algorithm (e.g. searching, insertion, deletion or sorting) | Examination |
| 7 | explain the differences between basic complexity classes of algorithms (constant, linear, quadratic, logarithmic, exponential) | Examination |
| 8 | select, with justification, appropriate algorithms for basic tasks such as searching, including reference to the algorithm's complexity class | Examination |
Restrictions, Prerequisites and Corequisites
Restrictions:
None
Prerequisites:
None
Co-requisites:
None
Teaching
Teaching Methods:
2 hrs lecture, 1 hr exercise class per week
Contact Hours:
Assessment
- Supplementary (where allowed): As the sessional assessment
- 3 hr examination (70%), continuous assessment (30%). Resit by examination only.
Recommended Books
| Title | Author(s) | Publisher, Date |
| Computing Science: an Overview | Brookshear | Addison-Wesley, |
| Computer Science, a Modern Introduction | Goldschlager L & Lister A | Prentice Hall, 1988 |
| Computing Concepts with Java Essentials | Horstmann C S | 1998 |
| Foundations of Computer Science in C | Aho A V & Ullman J D | Freeman & Co., |
| Data Structures: An Object-Oriented Approach | Collins W J | 1992 |
| Computing Concepts with Java Essentials | Horstmann C S | 1998 |
| Data Structures & Algorithms: A First Course | Adamson I | 1997 |
| Data Structures in Java | Standish T A | 1997 |
| Detailed module notes will be provided. |
Detailed Syllabus
-
The von Neumann machine (6 lectures)
- Integer representation and integer arithmetic
- Real number computation
- Character representation and coding
- Memory organisation
- Machine language
- Basic imperative programming (5 lectures)
- Arrays and the for-loop
- Streams and the while-loop
- Macros, subroutines, stacks
- Functions, procedures, and methods
- Values and locations
- Basic abstract data types (5 lectures)
- Array-based implementation of lists
- Linked list implementation of lists
- Inheritance: stacks
- Inheritance: queues
- Abstract data structures
- Binary search trees. Representation, insertion, deletion, binary search, traversal.
- Heap-trees. Array representation, applications in priority queues and sorting.
- Graphs. Pointer and array-based representations.
- Sets. Representations, typical problems, some algorithms.
- Balanced binary search trees. Representation, insertion, deletion.
- Multiway Trees. B-trees, tries.
- Algorithms
- Complexity classes. Main definition, understanding of the main classes occurring in practice, determining the complexity class of a given algorithm.
- Sorting. Principles of sorting, sorting by comparison and its complexity. The main sorting algorithms (Insertion Sort, Selection Sort, Bubblesort, Heapsort, Quicksort, Mergesort), their applicability to different data structures, their complexity, strengths and weaknesses. Sorting by distribution.
- Searching. Sequential and binary searching, suitable data structures.
- Graph algorithms. Shortest path, spanning tree, traversal.
- Storing. Tables and hashing, chaining and open addressing collision handlers. Storing in trees.
- Others. Stable marriage.
Last updated: 4 Nov 2004
Source file: /internal/modules/COMSCI/2004/xml/18187.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus