Algorithms - Basic

This algorithm exam covers basic programming skills, typically seen during the first half of the first year of an IT university curriculum.
One main global cross category objective of this exam is to determine the result of an given algorithm's execution.

Scope
The purpose of this topic is to gain analysis skills that let solve unexpected problems, and exams objectives cannot be an exhaustive list of "unexpected problems".
We give clear examples of possible algorithms that are good question candidates.
Other and similar examples could be taken to write questions, as long as:

they are not too difficult (this is a basic level exam)
they don't require too specific/obscure prerequisites (as advanced statistics/math skills).

Language
While the questions may contain Java fragments, they cannot contain any Java trick. Please put Java related questions in one of the Java SE exam.
For example, the sorting section cannot contain questions about the Java API for sorting arrays or collections.

Questions may also contain code fragments written in "natural English", but not in other computer languages than Java (no C, Smalltalk, Pascal,...).
Example of natural English algorithm:
i <- 10
While i is greater than 0, do:
..i = i-1
..print i
end-while

The master rule is that syntax must be clear for everyone and bring no trick to the question.

Prerequisites

basic mathematical skills, as
- operations/functions log, sqrt, exponent, polynomials,
- notion of prime number
- calculating the area of a circle
- factorial
- greatest common divisor
basic programming and Java skills: variables, for and while loops, branches (if), arrays, objects.

References

Algorithms in Java (3rd edition) by Reobert Sedgewick.
Many points of these objectives are inspired from the book content which is a great study tool that will bring you much further than this exam level.
Wikipedia
feel free to post a comment to this objective with good references to add here

Not covered
Please keep the level of this exam basic. What is not in the objectives below is not in the exam. For example, these topics are not covered in this exam:

Compound Data Structures (as multi-lists)
Graphs
non-trivial sorts (shellsort, quicksort,...) and bubble sort.
complex tree manipulations
cross recursion.
non-recursion using a stack.

	Released	Beta	Frozen
Elementary Data Structures
Array 3 questions Solve problems by using an array to save items to process them later, during some computation. Sieve of Eratosthenes: write an algorithm that identifies prime numbers up to N, using an boolean array of size N, and of complexity O(N * sqrt(N)). Statistical simulation: write an algorithm that gathers some statistical data in an array, then computes the mean. In place processing: Compact an array in one pass by eliminating some given elements (like a defragmenter). Mathematical sequence: given the (simple) formula, compute a sequence in an array. Example: the Fibonacci numbers. Search: implement a sequential search.	9	11	22	Add a question Beta questions
Linked List 3 questions Define the notion of head and tail. Implement the different flavours of linked lists: simple, circular, with dummy head, doubly. Write algorithms that use lists. For example: Traverse a linked list and find, insert or delete elements. Reverse a linked list. Josephus problem: write an algorithm that uses a linked list to identify the remaining person from a group standing in a circle where, iteratively, the 5th person from the last eliminated person is ejected from the circle. Starting from a given element, detect a cycle in a list. Notes: The notion of "linked list" here does not refer to any implementation from the java.util collections. The convention is to use objects having a "next" attribute or method, to refer the next element of the list.	8	10	19	Add a question Beta questions
Abstract Data Types Java provides many abstract data types, for example in the java.util package. This exam does not refer to the built-in collections, but to your own classes.
Stack 4 questions Define a stack Identify a stack interface (push, pop, empty) Implement a stack using a list or an array Write algorithms that solve simple problems using a stack. For example: postfix expression evaluation, conversion of an infix to an outfix expression. Reverse an array, using a stack.	16	13	21	Add a question Beta questions
Queues 2 questions Define a FIFO queue Identify a queue interface (put, get, empty) Implement a queue using a list or an array Implement and use a double-ended queue.	3	11	10	Add a question Beta questions
Duplicate & index items 1 question Implement a stack/queue accepting no duplicate.	2	4	10	Add a question Beta questions
Recursion 4 questions Define recursion (note: to define recursion, you first need to define recursion - Anonymous) Identify obvious cases of false recursion (that could be implemented with a loop and no stack). Detect incorrect stop conditions that create never ending recursion. Implement recursion for solving problems. For example: Compute a factorial Euclid: find the greatest common divisor Evaluate a prefix expression (simple example of recursive descent parser). e.g. +2,3 (which equals 5). Find the greatest number of an array (false recursion) Move towers of Hanoi. Binary search in an ordered array.	9	37	21	Add a question Beta questions
Trees 4 questions Define: node, child/parent node, root, leaf, path, height, binary tree, ordered tree. Implement a tree representation Write an algorithm that: Traverses a binary tree: preorder, inorder, postorder, computes the height or the amount of nodes of a tree, finds an element in a binary search tree, constructs a tournament tree (from an array).	15	20	22	Add a question Beta questions
Sorting 2 questions Define a stable sort. Identify and implement: Selection sort. Insertion sort. Note: Java provides sorting algorithms, for example in the java.util package. This exam does not refer to these built-in algorithms, and require no knowledge about interfaces as Comparable.	5	36	12	Add a question Beta questions