COL100 lecture notes: 20-21 Sem 2

• What is computing, translation from a problem to an algorithm to a program
• How a computer works, how is a program compiled and executed by a computer, binary numbers, computing using 0s and 1s
• Programming in C. We are choosing C because it is close to the metal and will help you relate basic programming constructs to how they are implemented in a computer
• The importance of good algorithms, how the same problem can be solved in different ways with different degrees of efficiency
• Writing moderately complex programs. Planning first on paper how the program should be structured, and then coded in a programming language

• Lab exam 1: March 27th, 3:30-5:00pm
• Lab exam 2: April 25th, 3:30-5:00pm
• Lab exam 3: May 22nd, 3:30-5:00pm
• Re-minor/re-lab exam: May 29th, 3:30-4:30pm

• Check out some interesting links on the history of computers, the Jacquard's loom, and integrated circuits.
• The simple.c program we used to understand the storage of variables in memory, and operations on them. You can also take a look at Chapters 2 and 3 from the Kochan book.

• The datatypes.c, places.c, and round.c programs we used to understand type casting. You can also take a look at Chapter 4 from the Kochan book.
• The printmaxvals.c program we discussed in the tutorial to check for overflow when adding or subtracting two integer numbers.
• If you are curious about how mathematical functions are implemented, such as the ones in sqrt.c, take a look at the glibc source code such as for the sqrt 32-bit floating point implementation on the IEEE-764 architecture. Browse around and read the comments to understand different implementation methods on different architectures and for different precisions.
• Somebody came up with this interesting example with increment operators, and we understood what was going on by looking at the assembly language code to which the program was compiled by gcc. Details here.

• The program we used to understand the difference between assignment and equaliy operators.
• Variants of programs to find the maximum of three numbers: largest.c, another_largest.c, and yet_another_largest.c. You can also take a look at Chapter 6 from the Kochan book.

• The programs we discussed in class: calculating e, maximum of a series of positive numbers, and sum of the digits of an integer. You can also take a look at Chapter 5 from the Kochan book.
• Some additional programs for greater familiarity with loops: fibonacci series, whether a number is a palindrome or not (without using strings), printing shapes by evaluating conditions, printing a sine wave.

• Consult Chapter 12 in the Kochan book for bit operations
• Programs we discussed in class, to print the binary representation of a number, and the hexa representation, through bit operations. A twos-complement implementation to understand how negative numbers are stored and re-converted when to be displayed.
• With some pointer type conversations, we can also print the floating point representation of a number. Test with loss of precision when you go beyond 2^23.
• Floating point numbers have a representation for infinity. Check out this program with a division by zero with floats and integers - when does the program crash?

• You can also take a look at Chapter 7 in the Kochan book
• Programs we discussed in class, to show the histogram of a series of numbers, and to create sample inputs using random number generators. We also looked at redirection of input and output, and some nice tools like cat, head, and tail.
• Updated program to generate random numbers with a random seed.
• A simulation for forest fires in a 1D forest. Run the program for different values of fire and growth probabilities, and see whether the forest is able to sustain itself. Also try to simulate a circular forest, i.e. the left boundary of the forest connects with the right boundary. Later when we study 2D arrays, you can try changing the program to a 2D forest, and a circular 2D forest which is called a toroid.

• The matrix multiplication program we understood in class.
• The fun game of life program, with sample inputs for a glider, gun, and other shapes. If you are interested, you can check out more ANSI control characters here, note that you would substitute the escape character ^[ with \033 when using it in a printf in C, e.g. printf("\033[2J") to clear the entire screen (code is ^[[2J). You can also print in colour as described here, with common codes here.
• Here is also a 1D version of game of life and a sample input file.
• Strings are nothing but a 1D array of characters, terminated with a null '\0' character (decimal value 0). The program we discussed in class. ASCII codes 0..31 are control codes.
• Also check out the initial portion of Chapter 10 from the Kochan book.

• The simple programs we used to demonstrate passing by value in function calls, and passing by reference for manipulating arrays.
• The GCD program we did in class, to read arguments from the command line, convert the string arguments to integers, and compute the GCD of a series of integers.
• Also look up Chapter 8 from the Kochan book

• Variants of the fibonacci program discussed in class.
• Also look up Chapter 8 from the Kochan book

• Also look up Chapter 11 from the Kochan book
• Here are the various programs we did in class. Learning to swap numbers, array elements, pointers to arrays. Pointer arithmetic. Arrays of pointers and why command line arguments are passed as an array of pointers.

• Also look up Chapter 9 from the Kochan book
• The student records calculation and sorting program we discussed in class. Input file for stdin redirection.

• Also look up Chapter 17 from the Kochan book
• An implementation of command line parsing: trim spaces, count the number of strings, allocate an array of pointers, allocate space for each string linked from the array of pointers.