Module 22754 (2013)
Syllabus page 2013/2014
06-22754
Foundations of Computer Science
Level 1/C
John Bullinaria
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 introduce the fundamental concepts of Computer Science, such as 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 | demonstrate understanding of the principles of algorithmic programming | Examination, Continuous Assessment |
| 2 | demonstrate understanding of abstract models of data and computation | Examination, Continuous Assessment |
| 3 | make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity or considerations of numerical accuracy | Examination, Continuous Assessment |
| 4 | explain and apply data structures such as binary trees, heap-trees, graphs and tables, together with their internal representations and relevant algorithms | Examination, Continuous Assessment |
| 5 | select, with justification, appropriate data structures to ensure efficient implementation of an algorithm (e.g. searching, insertion, deletion or sorting) | Examination, Continuous Assessment |
| 6 | explain the differences between basic complexity classes of algorithms (constant, linear, quadratic, logarithmic, exponential) | Examination, Continuous Assessment |
| 7 | argue that algorithms are correct, and derive their time complexity | Examination, Continuous Assessment |
| 8 | select, with justification, appropriate algorithms for basic tasks such as searching, including reference to the algorithm's complexity class | Examination, Continuous Assessment |
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
- Sessional: 3 hr examination (80%), continuous assessment (20%).
- Supplementary (where allowed): 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 |
| ML for the Working Programmer. 2nd Edition | Paulson L C | 1996 |
| Detailed module notes will be provided. |
Detailed Syllabus
- Introduction to Semester 1
- Basics of functional programming
- Recursion
- Induction
- Complexity
- Lists
- Numeric data types
- Trees
- Queues
- Combinators
- Functional programming in Java
- Introduction to Semester 2
- Basic data types
- Arrays, Linked-Lists
- Stacks, Queues, Sets
- Efficiency and Complexity
- Measuring efficiency
- Complexity classes and Big-O notation
- Trees
- Representations and primitive operators
- Quad Trees
- Binary Trees
- Binary Search Trees, B-Trees
- Heap Trees, Priority Queues
- Sorting Algorithms
- General principles and strategies
- Insertion Sort, Selection Sort, Bubblesort
- Tree Sort, Heapsort
- Quicksort, Merge Sort
- Non-Comparison Sorts
- Storing Data
- Storing in Trees
- Hash Tables
- Handling Collisions
- Graphs
- Representations
- Traversals and Planarity
- Shortest Paths (Dijkstra's and Floyds' Algorithms)
- Minimal Spanning Trees (Prim's and Kruskal's Algorithms)
- Travelling Salesmen and Vehicle Routing Problems
Last updated: 22 August 2013
Source file: /internal/modules/COMSCI/2013/xml/22754.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus