# 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