Fundamentals of Computer Programming I

Fundamentals of Computer Programming I

Filip Uhlík

• Syllabus (PDF)

Some notes from lecture 1. A hello world example hw.c, an implementation of the Euclid algorithm gcd.c (running time of gcd(x,y) and bgcd(x,y)) and erratic progression erratic.c (running time of gcd(ers(x),ers(y))).

Some notes from lecture 2. A program for endianess determination bytesex.c, binary dump bits.c and radix conversion radix.c. Complete ASCII table. Some simple sources square.c, min3.c (min3b.c, min3c.c), pythagorian.c, leap.c, triangle.c and sort3.c (sort3b.c, sort3c.c).

Some notes from lecture 3. Floating point numbers description, dumper. Some simple sources factorial.c, fibonacci.c, prime.c, gem.c, heart.c, corner.c, Armstrong numbers arm.c and sum.c.

Some notes from lecture 4. power a number, combinations, Eratosthenes sieve (with number of factors and visualization), factor a number, Pascal's triangle (or with an array), perfect numbers, Joseph's problem and selectsort.

Some notes from lecture 5. copy a file, string to int, int to string, word count and reverse a string.

Some notes from lecture 6. recursive factorial, recursive Fibonacci, swap two values and factorial of a big number.

Some notes from lecture 7. echo, mc, fogger, snake (snake.gif), queens (queens.gif, queens.pdf), optimal calculation of powers.

Additional examples. frequency of letters (sonnets), climate statistics (klementinum), sudoku, stars, word frequency, anagrams (words from the Moby project, as one-liner shell script), print self, a way of a knight, symbolic operations on polynomials, 1d cellular automaton ca.c (with a primitive tga library tga.h and sample output ca.png), 2d cellular automaton snow.c (sample output snow.png), 2d cellular automaton bz.c (sample output bz.png), generate and find path in a maze maze.c (with sample output maze.text), funny phenomena with words (from a dictionary), queen dominancy problem, logo graphics (with sample output logo0.ps), game of othello, Conway's game of life (with sample input, more here), game of tetris.

Usefull links

top 500 computers, hello world in very many languages, implementations of different problems in many languages, very many nice problems, UTF-8 table, genealogy of programming languages, popularity of programming languages, text editors, C compilers, C IDEs, quantum experience. Check your PS (PostScript) and TGA (TARGA) viewers used here for graphics.

Examples for exam

[1] wc:: a simple version of Unix program wc (word count),
wc [-hcwl][file...]
[2] grep:: a simple version of Unix program grep (print lines matching a pattern),
grep [-hvi] fixed_sample [file...]
[2] base64:: a program for base64 encoding/decoding (method now used to send binary files via e-mail), see RFC 1521.
[2] cz2cz:: a program for conversion among various Czech encodings.
[3] polynomes:: a library for working with polynomials.
[3] permutations:: a library for working with permutations.
[1] split:: a simple version of Unix program split,
split [-h][-b bytes][-l lines] file
[1] head&tail:: simple versions of Unix programs,
head [-l lines][file...], tail [-l lines][file...]
[3] e:: a program that calculates number e to at least 1000 decimal digits.
[2] decompose:: a program that decomposes a direct product of (reducible) representations into irreducible ones.
[2] od:: a simple version of Unix program od (octal dump),
od -x [file...]
[1] strings:: a simple version of Unix program strings.
[2] SAW:: number of self-awoiding-walks in 2D.
[2] cal:: a simple version of Unix program cal, that prints a calendar, for year>1900.
[3+] othello:: desk game othello (reversi) or similar playable against a human.
[3+] rubik:: solve the Rubik cube.

Whatever else we agree upon. For an inspiration you can also check the Euler project.

For Unix utilities see corresponding manual pages, e. g. man 1 strings, to get program descriptions. The options mentioned here are obligatory. For other programs I expect something usable, but I don't want you to waste too much time on it. I give a credit for a program that is correct, it does not need to be long.

It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.

FORTRAN, 'the infantile disorder', by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is now too clumsy, too risky, and too expensive to use.

---E. W. Dijkstra