程序代写代做代考 Java prolog algorithm data structure CO580 Algorithms

CO580 Algorithms

CO580 Algorithms

Dr Timothy Kimber

January 2018

Introduction

Course Outline

The lecturer

PhD in Computational Logic (Imperial)

5 years as Teaching Fellow/Senior Teaching Fellow

Also teach Prolog to the MAC and Specialism classes

The structure

28 hours of interactive lectures (weeks 2–9)

Sessions include unassessed group and individual exercises

Two assessed exercises (one in Java) (10%)

A 2-hour written examination next term (90%)

Books

Introduction to Algorithms, Cormen et al., 3rd edn, 2009.

Algorithms, Sedgewick & Wayne 4th edn, 2011.

Algorithms (580) Introduction January 2018 3 / 17

Introduction

Intended Learning Outcomes

At the end of this module YOU will be better able to …

1 Communicate with other engineers about how to solve a
computational problem*.

2 Organise and manage computational resources.

3 Deploy known solutions to common problems.

4 Create original solutions to problems using sound general approaches.

5 Design appropriate data structures.

6 Explain properties of a solution, existing or original, to customers.

7 Analyse performance of code using established engineering techniques
and terminology.

*e.g. at an interview

Algorithms (580) Introduction January 2018 4 / 17

Introduction

Course Summary

This course: How To Write Good Programs

A good program …

Always gives some output (terminates)

Always gives a correct output (sound)

Gives an output for every possible input (complete)

Uses as few resources as possible

Algorithms (580) Introduction January 2018 5 / 17

Introduction

Aims

This course is concerned with the resources consumed by your programs,
principally space and time.

Questions To Answer

How much time/space does a program use?

What kind of program uses least time/space?

These questions are a bit harder to answer for time, but that is what we
are usually most interested in, so that is where we will start.

Algorithms (580) Introduction January 2018 6 / 17

Time

An Algorithm

Example (Sequence Search)

Input: a sequence L = 〈a1, …, aN〉 of N integers, and
an integer k

Output: True if k is in L, False otherwise

Simplification: assume L is ordered

Procedure: SimpleSearch (Input: seq L, int k)

1 for each e in L

2 if e == k

3 return True

4 return False

Algorithms (580) Introduction January 2018 7 / 17

Time

Input Cases

When analysing an algorithm’s performance it is essential to be clear what
input cases are being considered. Most often this will be one of

Best case (least possible time/space consumed)

Worst case (greatest possible time/space consumed)

Average case (see later)

Later, you will see how to combine these analyses to describe performance
for any input.

Algorithms (580) Introduction January 2018 9 / 17

Time Formal Analysis

Formal Analysis (Worst Case)

The input has N elements

The cost (time taken) for line i is represented by ci .

We know exactly how many times each instruction happens (only
worst case considered).

Simple Search (Input: seq L and int k)

Cost Times

1 for each e in L c1 N+1

2 if e == k c2 N

3 return True c3 0

4 return False c4 1

Algorithms (580) Introduction January 2018 10 / 17

Time Formal Analysis

Simple Search (Worst Case)

So, the running time, or time complexity for a worst case input of size
N is

T (N) = c1 + Nc1 + Nc2 + c4

so,
T (N) = (c1 + c4) + (c1 + c2)N

so,
T (N) = aN + b

There is a chunk of time a that is used for each element of L

There is a chunk of time b that is used just once

Algorithms (580) Introduction January 2018 11 / 17

Time Formal Analysis

Simple Search (Worst Case) Time Complexity

Longer sequences take more time

The increase is linear

a and b will differ with language, hardware, load etc.

Algorithms (580) Introduction January 2018 12 / 17

Time Comparisons

Comparing Algorithms

Given an input of size N, the worst case time complexity for a range of
algorithms that all solve Problem X is:

(A) T (N) = a1N + a2

(B) T (N) = b1N

(C) T (N) = c1N
2 + c2N + c3

(D) T (N) = d1N
3 + d2

where a1, b1, c1 and d1 are positive. In terms of time, which is:

the best algorithm? (why?)

the worst algorithm? (why?)

Algorithms (580) Introduction January 2018 13 / 17

Time Highest Order Terms

Highest Order Terms

For large N functions are dominated by their highest order N term

Polylogarithmic functions include a term of the form (logb N)
k

Any degree d positive polynomial grows faster than any polynomial of
degree less than d , and any polylogarithm

Definition (Polynomial)

A polynomial of degree d (for d ≥ 1) is a function p(N) of the form

p(N) = a0 + a1N + a2N
2 + · · ·+ adNd

in which ad 6= 0. The polynomial is asymptotically positive iff ad > 0.

Exponential functions include a term of the form aN

If a > 1 then the function grows faster than any polynomial

Algorithms (580) Introduction January 2018 14 / 17

Time Highest Order Terms

Comparing Algorithms

Depending on the constants, the time complexities might look like this …

Regardless of constant factors, D will take longest for large N

“Large N” is usually small enough that we don’t want C or D

Algorithms (580) Introduction January 2018 15 / 17

Time Highest Order Terms

Comparing Algorithms

Or like this …

A and B are, in a sense, indistinguishable (constant factors)

The value of large N, and if it exists, for A and B needs to be
considered

Algorithms (580) Introduction January 2018 16 / 17

Time Highest Order Terms

Comparing Algorithms

So, we have clear(ish) goals

Any “N3 algorithm” is worse than any “N2 algorithm”

Any “N2 algorithm” is worse than any “N algorithm”

Unless we have big constants*, or small N

*Normally, we don’t

Algorithms (580) Introduction January 2018 17 / 17

Introduction
Time
Formal Analysis
Comparisons
Highest Order Terms