Computer programming

Lab grades

Midterm results For short comments send e-mail.
Midterm solutions: prefix expression (see lab 3), reading terms (concise), bit segments (see lab 5), float mantissa (see last program for lect. 5), ints in string (version with indices)
Exam results (1, 2 and 3) To discuss your exam, set up an appointment.
Exam 1 solutions: change with coins, hexadecimal float, 3 reals per line, sort words in file (alternate version)
Exam 2 solutions: replace letters, unsigned to float, numeric expression (simplified), last n lines
Exam 3 solutions: n choose k letters, hexa string to num, string chars in order, extract HTML headings
set 2: balanced parantheses, rotate bits left, matrix multiply, image URLs

Course materials

last year's course

1. Introduction. Recursion.
   Sample program: box fractal
2. Recursion. Character input.
   3n+1 problem, read fractional part
3. Tail recursion. Decision. Assignment. Iteration
   HTML tag filtering (version 2), integer calculator
4. Iterative processing
   LaTeX commands, prefix to postfix, count words in line (one inner loop, two inner loops, in-word flag), balanced parantheses
5. Internal representation. Bitwise operators
   bitwise addition, stream bits, bitmap processing, float structure
6. Arrays. Matrices. Strings
   add numbers represented as strings
7. Input/Output
   add numbers on each line, find full word or substring, find URLs
   Additional reading: Aleph One, Smashing The Stack For Fun And Profit, Phrack Magazine, vol. 7(49), 1996. A classic introduction to the danger of buffer overflows.
8. Pointers. String processing
   cutting a string, building a format string, parsing floats/ints
9. Pointer arithmetic. Function pointers
   Examples: string concatenation, sorting strings, vectors and matrices
10. Dynamic allocation. Files
    Examples: write number in binary, info from bitmap
11. Structures
    Example: Date with bits and bitfields, function terms
12. Abstract data types: intlist.h, intlist.c, listprog.c, fiblist.c
13. Implementing abstract data types. Review
    listfun.h, listfun.c, using pointers to links, queue.c, myalloc.c (more here), s-expressions
14. Timing. Randomization. Hashing
    random numbers, hashing for word frequencies

Laboratory

1. Lab 1: Introduction. Recursion
   Exercise: Write a program, similar to the one done in class, that draws the Koch curve, as described here.
2. Lab 2: Recursion. Character input
3. Lab 3: Character processing (recursive and iterative)
4. Lab 4: Character processing (recursive and iterative)
   Solved problems: Comments and strings, read real number, extract phone numbers
5. Lab 5: Bitwise operators
6. Lab 6: Arrays
   Solved problems: n choose k, reverse each word, words in opposite order
7. Lab 7: Input/output
   Solved problems: numbers with commas. Intermediate stages: 00, 0, 1; filter sub/superscript tags
8. Lab 8: Pointers
   Solved problem: reorder cmdline args
9. Lab 9: Pointers
   Solved problems: paste strings, combine array elements
10. Lab 10: Dynamic allocation
11. Lab 11: Files
12. Lab 12: Structures. Abstract datatypes.
    Solved problems: remove list duplicates, number as prime factors
13. Lab 13: Abstract datatypes. Review
    Solved problems: read integer list, reconstruct tree

Training exercises

1. Recursion: fractals and grammars
2. Recursion: rewriting, combinatorics.
   sequences with sum of digits 10

Resources

• ACM/IEEE Computing Curricula, in particular Computer Science 2013 curriculum
• Allen B. Downey, Thomas Scheffler. How to Think Like a Computer Scientist - C-Version PDF
• Steven Summit, C Programming, Experimental College, University of Washington, USA.
• Essential C and Pointer Basics from the Stanford CS Education Library
• Current standard for the C programming language: ISO/IEC 9899:201x. Last publicly available version.
• GNU C Library Manual