^subject^ [other A&DS]

Algorithms and Data Structures prerequisite knowledge

The following are entrance requirements for the subject.

Requirement 1

The following abilities are assumed for entry to the subject.
Given an English and/or mathematical description of a new problem [e.g.(click here)],
identify the underlying abstract problem,
devise an efficient algorithm to solve the problem, and
turn the algorithm into an efficient piece of code in the designated programming language,
e.g.
F is an array of N floating point numbers.
An interval, F[i..j], consists of the elements F[i], F[i+1], ..., F[j] if i <= j and is empty if j < i.
The interval is said to be non-decreasing if F[k] <= F[k+1] for all k such that i <= k < j.
Write an efficient piece of code to find the longest non-decreasing interval in F and print its start position and its end position.
The problem will not have been seen before. Examples may or may not be provided.
A solution with a certain time- and/or space-complexity may be required, e.g. linear-time above.
The solution may involve nested loops, recursion, conditionals, arrays, pointers, functions, parameters.
The candidate must be able to produce a correct solution, minor syntax errors excepted, in 10 minutes, without the use of a computer or a reference book. Any non-trivial error results in a `fail'.
A high level of competence (90+%) is required.

Requirement 2

All candidates starting the subject must already be fluent (90+%) with all of the terms and concepts listed below, i.e. must be able to

  1. manipulate and write mathematical formulae and computer programs involving . . .
  2. give definitions for . . .
  3. understand computer programs, English sentences & descriptions, and mathematical formulae involving . . .

English Mathematics Programming The Designated Language
e.g. if C e.g. if Java
adjacent;
alphabet, alphabetic;
always;
annotate;
append;
assert;
at least, at most;
condition, conditional;
conjunction;
contradiction;
contrary;
disjunction;
distinct;
efficient;
element;
equal;
equivalent;
grammar;
hence;
hypothesis;
implies, implication, implied by, stronger, weaker;
inverse;
least;
length v size;
lexicographic;
magnitude;
minimum, min, maximum, max;
must;
negation;
never;
nil (not as in C);
null (not as in C);
operand;
operator;
opposite;
predicate;
prefix;
resolve;
required;
retrieve;
search;
semantics;
shall;
should;
sometimes;
suffix;
syntax;
tautology;
theorem;
theory;
tie,  ties, =;
terminates;
traverse;
unique;
value;
verify;
whenever;
 =, <>, <, <=, >, >=;
abs, absolute value, size;
area of circle, triangle, square, rectangle, trapezoid;
associative, left right;
ceiling;
CNF;
commutative;
composition;
differentiation of polynomials, x-n, log, exp;
DNF;
e;
exponential, natural, 210, 220, 2x, 10x, xy+z, xy×z, (xy)z, sqr, sqrt;
factor;
factorial n!;
floor;
function, S->T, definition by cases, composition, fog, f2(x);
GCD, HCF;
identity;
interval, open, (x,y), closed, [x,y], [x,y), (x,y];
integration of polynomials, x-n, log;
inverse;
LCM;
log, log(x×y), base 2, e, 10, conversion, log-plot, log-log plot;
grammar of arith' exp' & of simple(!) English,
magnitude;
matrices, transpose, multiplication, determinant;
mean;
median, quartile;
mod, modulo;
permutation;
pi, π;
polynomial, quadratic, cubic, degree;
predicate logic, p(x);
prime number;
proof by contradiction & by induction;
propositional logic, &, or, =>, <=, <=>, not, ¬;
recurrence relation (simple);
relation;
series, arithmetic, geometric, convergence, limit, sum ∑ (Sigma), product Π (Pi);
set notation, {x|p(x)}, empty-set, member, subset, containment, intersection, union, product, S×T, S2, S*, S+, S->T, power set;
simplification of negation;
term;
transitive;
vector, dot product, multiplication by matrix;
 abstraction;
ADT;
algorithm v. program;
allocate space;
and;
array 1-D 2-D;
assembly code equiv' of C (say);
assertion;
binary numbers;
binary tree;
bit operations, byte;
Boolean;
by-reference, by-value;
case/switch;
char Ascii;
command line parameters;
compiler;
complexity, linear, quadratic, time, space, best, average, worst;
directory structure;
editor (text);
file, text, redirection, < and >;
floating-point, real;
generalisation;
goto;
if, conditional;
indirection;
integer;
interpreter;
invariant (of loop);
label;
linked-list, cons, head, tail, nil, null, (not C);
loop, pre-test, post-test;
n-tuple;
not ¬;
or;
parameter, formal, actual;
parameter passing, by-value, by-reference;
pipe, |;
pointer;
postcondition;
precondition;
procedure, function, subroutine, routine;
random access;
recursion, linear, binary;
redirection, input, output;
sequential access;
sorting, bubble, insertion & selection;
space complexity;
stack (system & ADT);
string & operations;
subroutine;
time complexity;
types;
 +, -, *, /, %, <, <=, >, >= ,==, !=, ., &&, ||, &, |, (_?_:_), ++, --, &, *, ->;
.c, .h, .o, .out;
#define, #include;
argc argv, array, 1-D, 2-D;
by-value, by-reference;
char;
char *;
command-line params;
float, double;
for(;;), if(...), while(...), switch;
gcc;
goto;
int;
labels;
main();
malloc;
NULL;
printf;
prototype;
return;
scanf;
sizeof;
string, *char;
struct;
typedef;
 +, -, *, /, %, <, <= >, >=, ==, !=, ., &&, ||, &, |, (_?_:_), ++, --;
.java, .class;
abstract;
application;
array, 1-D, 2-D;
boolean;
byte;
char;
class;
command-line params;
constructor;
dynamic;
exception;
extends;
final;
float, double;
for(;;), if(...), while(...), switch;
import;
instanceof;
int;
interface;
java, javac, javadoc;
just in time compiler;
length;
local;
main();
member;
method;
nested;
new;
null;
package;
parameter;
public, private, protected;
reference;
return;
static;
String;
Sun microsystems;
switch case;
this;
try catch;
wrapper;
 
<S>  ::= <NP> <VP> .  | <VP> !
<VP> ::= <Verb> <NP>
<NP> ::= <Article> <Noun>
<Article> ::= a | the
<Noun> ::= cat | dog | man
<Verb> ::= bite | chase
--- Simple(!) English ---
  
               S
             .   .
           .       .
         .           VP
       .            . .
     .             .   .
   NP             .     NP
  . .            .     . .
 .   .          .     .   .
a    dog    chase(s) the cat.
--- Parse Tree ---
  
<Exp>  ::= <Exp> <PM> <Term> | <Term>
<Term> ::= <Term> <TD> <Factor> | <Factor>
<Factor> ::=  ( <Exp> ) | - <Factor> | <Num> | <Id>
<PM>  ::= + | -
<TD>  ::= × | ÷
<Num> ::= 0 | 1 | 2 | ... etc.
<Id>  ::= x | y | z | ... etc.
--- Arithmetic Expression ---

Requirement 3

It may be that some of these terms and concepts have not been covered in any of the preceding prerequisite-subjects, in which case it is the candidate's responsibility to master them prior to starting this subject.


© L. Allison, Computer Science, Software Engineering.
Created with "vi (IRIX)",   charset=iso-8859-1