| STUDENTS
> Theory II
|
Theory II
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: | 1004 |
| Year: | 1 |
| Prerequisites: | 1B12 |
| Term: | 2 |
| Taught By: | Denise Gorse (50%)
Anthony Hunter (50%)
|
| Aims: |
To develop programming and problem solving skills, to encourage
a thoughtful approach to analysis and design problems, to
familiarise students with logical and mathematical inference and argumentation.
|
| Learning Outcomes: |
Students should be able to apply this knowledge
to specification of algorithms and logic programming.
|
Content:
| Searching and sorting algorithms | Elementary searching - comparing sequential, binary and
interpolation
search.
Binary search trees.
Balanced trees.
B-trees.
Hashing |
| Graph algorithms | Depth-first search of undirected and directed graphs.
Articulation
points.
Strongly connected components.
Topological sorting of acyclic graphs.
Breadth-first search of directed and undirected graphs.
Network flow.
Ford-Fulkerson
method.
Euler circuits. |
| Text algorithms | String searching.
File compression including Huffman coding.
Cryptology
including public key cryptosystems. |
| Analysis of algorithms | Empirical versus theoretical analysis.
Algorithmic complexity.
O notation.
Best, worst and average cases.
Classifications of algorithms.
Hierarchies of
complexity.
Tractable and intractable problems.
Sums of series.
Simple
summation formulae.
Estimating a sum using integration. |
| Algorithms with loops | Nested loops.
Gaussian elimination.
Examples in geometric algorithms: Prim's and Kruskal's algorithms
|
| Recursive algorithms and recurrence relations | First-order recurrence relations.
Solving recurrence using the characteristic
equation.
Change of variable, conditional asymptotic notation.
Examples
of maths algorithms including exponentiation and large multiplication. |
| Analysis of searching and sorting algorithms | Sequential search in ordered and unordered arrays
Binary search.
Insertion sort, mergesort, quicksort.
Best case for comparison-based sorting. |
Method of Instruction:
Lecture presentations with associated courseworks.
Assessment:
The course has the following assessment components:
- Written Examination (2.5 hours, 90%)
- Coursework Section (2 pieces, 10%)
To pass this course, students must:
- Obtain an overall pass mark of 40% for all sections combined
The examination rubric is:
Answer 3 questions; at least 1 (out of 3) from Part I and 1 (out of 3) from Part II. All questions carry equal marks. Resources:
T. Cormen, S.Clifford C. Leisserson, and R. Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, 2001
R. Sedgewick, Algorithms, Addison-Wesley, 1998.
|
+44 (0)20 7679 7214 - Copyright © 1999-2007
UCL
