- The subject
**is**about problem-solving with computers: algorithms and data structures. - The subject
**is not**about English, it just happens to use English for notes, tutes, pracs etc.However, it is necessary that you be(come) expert in the language. . . English . - The subject
**is not**(mainly) about programming in**C**. - The subject just
*happens*to use**C**as the programming language that prac work etc. is done in.However, it is necessary that you be(come) expert in the specified programming language. . . .**C** - Algorithms will be presented in English, pseudo-code,
**C**or even other programming language(s) as convenient.

The subject aims to cover:

- (i) General problem-solving strategies and techniques, e.g.
- useful paradigms, e.g.
- analysis of algorithms and data structures, e.g.

- (ii) A selection of important computational problems, e.g.
- (iii) A selection of important algorithms and data structures
e.g.
[L5]
[L10]
[L12]
[L17]
[L19]
etc.,
- as a "tool kit" for the working programmer,
- as example solutions to problems (ii),
- as examples of solved problems, to gain insight into (i).

On completing the subject you should be able to apply these general problem-solving strategies or algorithmic paradigms

**Divide and conquer**[L6] [L8]**Dynamic Programming**[L7] [L8] [L15] [L16],**Greedy strategy**[L15] [L16] [L17],**Recursion**, linear, binary, n-ary, mutual, [L2] [L6] [L10] [L22],

to new problems that you have not seen before, problems that you cannot find solutions to in books and other sources.

For a given algorithm you should be able to:

**Prove**its correctness using logic and pre- & post-conditions, assertions, loop invariants as appropriate [L2] [L3] [L4] [L4'] [L5] [L6] ... etc. [L15] [L16] [L17] Prove termination [L3] [L8] [L20].**Analyse**its best-, average- and worst-case time- and space-complexity where possible, or give estimates otherwise [L6] [L8] [L10] [L13] [L17] [L24] etc..**Demonstrate**its operation on simple examples using diagrams etc. [L10] [L11] [L16] [L17]**Code**the algorithm in the programming language of the subject.**Modify**it to solve a new problem.

For a given abstract data type (ADT) you should be able to:

- Specify its properties by giving
**rules**/ equations that its constructors and/or operators must obey [L1] [L2] etc.. **Manipulate**expressions, e.g. to show that different expressions are equivalent in value [L2].**Code**its data representation and operators in the programming language of the subject.**Modify**it to solve a new problem.

You should be familiar with these important problems and their solutions (alphabetic order):

- connectedness in graphs [L15]
- minimum spanning trees [L16] [L17]
- numerical problems - e.g. solving f(x)=0 and integration [L20]
- ordering problems in directed acyclic graphs (DAGs) [L18]
- searching (retrieval, dictionary tables, index structures) [L9] [L10] [L11] [L12]
- shortest paths in graphs [L15]
- sorting [L4] [L5] [L6] [L18]
- string searching / matching, exact and approximate [L7] [L8] [L11] [L13] [L19]
- traversal of various data structures [L9] [L14] [L14'] [L17] [L18]

© L. Allison 2006,

Faculty of Information Technology (Clayton School),