Computer programming - Review

Recursion

Understand the recursive view of a number as list of digits, and write functions that work with numbers (read number, reverse digits, max/min/sum/count digits, etc.)
Understand the use of recursion to compute recurrent sequences or limits of such sequences or series with a given precision
Understand recursively structured text and use recursion to process such text or check that it is properly structured (e.g. balanced parantheses, nested tags, prefix/infix/postfix expressions)

Sample problem
A prefix expression is either an unsigned integer or an operator + - * / followed by two prefix expressions, preceded by arbitrary whitespace. Write a program that reads a prefix expression from input and computes its value.

Iteration

Understand character-by-character processing until end of input (EOF).
Process input that has repetitive structure (all words, all numbers)
Process input searching/identifying certain characters/patterns/tags

Sample problems

Write a program that uses readnat / readint to compute the sum of unsigned/integer numbers on each line / until end of input.

Write a program that identifies all numbers in an arbitrary text (separated or not by whitespace from the rest of the text) and prints their sum.

Bit operators

Understand and work with the binary representation of integers and floats
Be able to test, set, reset single bits and extract and manipulate segments composed of several bits using the appropriate masks

Sample problem
Write a function that takes two unsigned integers n and k and returns the value obtained rotating n by k bits to the left (bits removed on the left are inserted at right).

Arrays

Use arrays to store values computed or read from input
Traverse arrays to search or to compute aggregate values
Correctly obey array limits to avoid overflow

Sample problem
Write a function that takes as argument an array of n integers and its length and checks if the array is a permutation of the numbers 0 through n-1. If so, return the number of cycles of the permutation; else return 0.

Marius Minea

Last modified: Sat Nov 7 17:00:00 EET 2015