| STUDENTS
> Theory I
|
Theory I
Note:
Whilst every effort is made to keep the syllabus and assessment records correct
for this course, the precise details must be checked with the lecturer(s).
| Code: | 1002 |
| Year: | 1 |
| Prerequisites: | A-level Mathematics |
| Term: | 1 |
| Taught By: | Robin Hirsch (50%)
Anthony Hunter (50%)
|
| Aims: |
To introduce formal methods for reasoning about
algorithms and, more generally, to formalise the reasoning process.
|
| Learning Outcomes: | Students should be familiar with the
techniques listed below and should be able to apply them to real
problems. They should be able to extract the logical content of a
(propositional) argument and prove its validity. They should be able
to formalise an algorithm and analyse its efficiency.
|
Content:
| Argumention | what is logic?
what is a rational argument?
what are common fallacies? |
| Boolean algebra | examples
axiomatisation
normal forms
connections with hardware design and programming
logic gates and circuits |
| Induction | Simple arithmetic induction
Weak and strong induction
Structured induction |
| Propositional Logic | Syntax
Translating English into logical sentences
Semantics - truth tables
Rules of inference and correspondence with informal argument
techniques
Proof theory: Hilbert systems and tableaus
The satisfaction and validity problems
Ideas of premise and conclusions
Soundness, completeness, decidability
Using tableau for converting to disjunctive normal form
|
| Introduction to algorithms | What are algorithms?
Why study algorithms?
Pseudocode
Efficiency of algorithms
Elementary operations
Examples of maths algorithms
Recurrence and recursion
Example: Insertion sort
Optimisation problems |
| Introduction to data structures | Lists, arrays, linked lists, stacks, queues
Graphs and trees
Tree traversal
Heaps |
| Greedy algorithms | What are greedy algorithms?
Minimum spanning trees
Kruskal's algorithm
Prim's algorithm
Dijkstra's algorithm
Greedy heuristics |
| Divide and conquer algorithms | What are divide and conquer algorithms?
Binary search
Quicksort algorithm |
| Dynamic programming | What is dynamic programming?
Calculating binomial coefficients
Floyd's algorithm
Warsall's algorithm |
Method of Instruction:
Lecture presentations with associated courseworks.
Assessment:
The course has the following assessment components:
- Written Examination (2.5 hours, 95%)
- Coursework Section (2 pieces, 5%)
To pass this course, students must:
- Obtain an overall pass mark of 40% for all sections combined
The examination rubric is:
Answer all three questions. The questions carry equal marks.Resources:
T. Cormen, S.Clifford, C. Leisserson, and R. Rivest, Introduction to Algorithms, MIT Press, 2001
W. Hodges, Logic: an introduction to elementary logic, Penguin, 1977.
R. Sedgewick, Algorithms, Addison-Wesley, 1998.
R. Sedgewick, Algorithms in C++, Addison-Wesley, 1992.
J. Truss, Discrete mathematics for computer scientists, Addison-Wesley, 2nd edition, 1999.
|
+44 (0)20 7679 7214 - Copyright © 1999-2007
UCL
