Prerequisite Modules
Description
This module serves as an
introduction to programming, program design and algorithms for
computer programs. There is a substantial amount of content in the
module, something which is reflected in the number of credits and
hours assigned to its delivery. The module is strongly oriented
towards developing the student's skills to the level required to
design, implement and test standalone computer programs that implement
well known and novel algorithms, with a suitable command line
interface and files for persistent storage. Students are introduced to
a structured, procedural programming language such as C, and are
presented with numerous tasks throughout the module which facilitate
the development of the required skills to implement computer programs
that take input from both the terminal and persistent stores, process
the input data according to complex rules and produce output to both
the terminal and persistent stores. This module also provides the
student with an opportunity to learn about the important searching,
sorting and representation algorithms as well as learning how to build
upon them to create new algorithms for novel problems.
Aims
-
To teach students how to design
and write computer programs that read input from both the user and
from files and present and store output from computer programs at
the terminal and in text and random access files.
-
To teach students how to structure
a computer program by dividing it into reusable chunks or modules.
-
To teach students how to correctly
comment and document program code.
-
To convey to students some of the
theory and application of algorithms and data structures.
-
To show how the concepts involved
can be expressed in a programming language and at the same time
expose the students to sophisticated programming.
-
To show students how to establish
an analysis of complexity and algorithm performance issues.
Learning Outcomes
On successful completion of this
module, the student will be able to:
-
Design computer programs starting
from simple requirements.
-
Write computer programs using a
structured, procedural language such as C.
-
Write computer programs that can
interact with persistent data stores such as text files and random
access files.
-
Divide computer programs into
reusable blocks of code across numerous source code files.
-
Use a text editor with command
line tools and simple Integrated Development Environment (IDE) to
compile, link and execute program code.
-
Test computer programs to ensure
compliance with requirements.
-
Both describe and use a wide
variety of well known algorithms for solving specific problems.
-
Develop new algorithms above a
foundation of the well known algorithms presented in the module.
-
Analyse, compare and contrast
algorithms to evaluate their strengths, weaknesses and uses.
-
Implement well-known and novel
algorithms and data structures in a procedural language.
Learning and Teaching Methods
Lectures, self-study, labs,
tutorials, and any combination of discussion, case study,
problem-solving exercises, readings, seminars, and computer-based
learning.
Content
Fundamental elements of
programming: Project Creation, Editing, Compiling Linking
Debugging
Introduction to programming:
Programming style, program layout, indentation, comments, choosing
variable names. Simple Input /output. Programming constructs:
Assignment Statements conditional statements, case statements, loops.
Data types, constants and variables. Built in Types Strings. User
Defined Types (UDT). Arrays of scalar data types, UDTs and objects.
Implementing Common Algorithms:
Summation, counting, numeric operations, swapping, maximum and
minimum, simple string and array manipulation. Sorting and searching.
Data Storage: Text files.
Random access files. Creation, deletion and tests for the existence of
files. Input and output for both types of files.
Modular techniques Writing reusable code with modules, subprograms and
functions. File input-output. Dynamic memory allocation.
Testing, debugging and
documentation: Objectives and principles of testing. Testing and
debugging strategies. Debugging tools. Technical and User
documentation.
Data Structures and Algorithms:
A Philosophy of Data Structures. Abstract Data Types and Data
Structures. Problems, Algorithms, and Programs. Best, Worst, and
Average Cases. A Faster Computer, or a Faster Algorithm? Asymptotic
Analysis. Calculating the Running Time of a Program. Analyzing
Problems. Space Bounds. Some Practical Considerations. P, NP and
NP-Complete.
Simple Data Structures:
Dynamic Allocation, Lists, Stacks, and Queues. The Dictionary ADT.
Priority Queues and Heaps.
Sorting:
Internal Sorting. Sorting Terminology and Notation. Three O(n^2)
Sorting Algorithms, Shellsort, Quicksort, Mergesort, Heapsort. Binsort
and Radix Sort. An Empirical Comparison of Sorting Algorithms. Lower
Bounds for Sorting.
Searching: Searching Sorted
Arrays. Binary Search, Binary Search Trees. Searching in Sets.
Hashing. 2-3 Trees, B-Trees.
Introduction to advanced
algorithms: Huffman Trees
and Huffman Coding. Simple, Euler and Hamiltonian Paths. Graph
Representation, Dense and Sparse Graphs. Graph Search. Minimum
Spanning Tree. Shortest Path.
Assessment
The methods of assessment to be used
to measure the learning objectives stated above are written
examination and continuous assessment including one or more of
assignment, essay, problem-solving exercise, oral presentation, and
class or lab tests.
-
Continuous Assessment: 30%
-
Examination: 70%
Recommended
Reading
-
Paul Kelly (1999), A Guide to C
Programming, Gill and Macmillan
-
Robert Sedgewick (1997),
Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting,
Searching (3rd Edition), Addison-Wesley
-
Harvey M. Deitel (2003), C how to
Program (4th Edition), Prentice Hall
|
|
For more information contact
Ciarán O'Leary
|
Home