Module 11338 (2001)
Syllabus page 2001/2002
06-11338
Introduction to Computer Science B
Level 1/C
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.)
Relevant Links
Outline
The module will continue to introduce the fundamental concepts of Computer Science, such as the analysis of algorithms and advanced data structures and 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 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 including error analysis
Learning Outcomes
| On successful completion of this module, the student should be able to: | Assessed by: | |
| 1 | understand data structures such as binary trees, heap-trees, graphs and tables, together with their internal representations and relevant algorithms | Examination |
| 2 | judge the suitability of a particular type of data structure for a given application | Examination |
| 3 | select appropriate algorithms for basic tasks such as searching | Examination |
| 4 | select appropriate data structures to ensure efficient searching, insertion, deletion and sorting | Examination |
| 5 | appreciate differences between basic complexity classes of algorithms (constant, linear, quadratic, logarithmic, exponential) | Examination |
| 6 | estimate numerical errors of approximations and of results of arithmetic operations | Examination |
| 7 | define selected simple numerical methods and estimate their error | Examination |
Restrictions, Prerequisites and Corequisites
Restrictions:
None
Prerequisites:
None
Co-requisites:
06-11337 (Introduction to Computer Science A) (linked module)
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 (80%), continuous assessment (20%), divided equally between this module and 06-11337 (Introduction to Computer Science A). Resit by examination only.
Recommended Books
| Title | Author(s) | Publisher, Date |
| Detailed course notes will be provided. | ||
| Foundations of Computer Science in C | Aho A V & Ullman J D | Freeman & Co., |
| Computer Science, a Modern Introduction | Goldschlager L & Lister A | 1988 |
| 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 Syllabus
-
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.
- Numerical methods
- Numerical methods. Scope, roots of equations, bisection method.
- Error analysis Numbers, expressions.
- Linear interpolation.
Last updated: 29 July 2001
Source file: /internal/modules/COMSCI/2001/xml/11338.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus