Introductory Computer Science - term 2

Peter Tino

Lecture Timetable and Handouts

While the handouts are provided as PDF, I will develop most of the ideas on the whiteboard. You should take notes during the lectures.

Week Lecture Lab
1 Sorting algorithms I [PDF] no lab in week 1
2 Sorting algorithms II [PDF] Implement one of the sorting algorithms
3 Implementing sorting algorithms [Insert Sort code] [demo code] Implement one of the sorting algorithms
4 Recursion [PDF] [factorial code] [screen shot for factorial(9)] Implement and study factorial as a recursive function. Implement Fibonacci numbers as a recursive function.
5 Self-similar objects, Koch curve [PDF] [my_line code] [mother_shape code] [run_koch code] Extended lecture, no lab
6 Getting familar with the Koch curve code [my_line code] [mother_shape code] [run_koch code] Understand the Koch curve code, start work on the assignment
7 Extended lab, no lecture work on the assignment
8 Complex systems, Madelbrot and Julia sets [PDF] work on the assignment
9 Getting familar with the Mandelbrot set code [do_mandelbrot code] [run_mandelbrot_levels code] Use Madelbrot set code to create visually appealing images, try different color schemes and transformation maps
10 Getting familar with the Julia set code [do_julia code] [run_julia_levels code] Use Julia set code to create visually appealing images, try different color schemes and transformation maps
11 Extended revision lecture Extended revision lecture

• Sorting Algorithms

• Recursion
• Self-Similar Objects

Assignment (Deadline: Fri 28 March, 5pm)

Create your own self-similar object that is both visually pleasing and more complex than the basic Koch curve described in lectures and practiced in labs. The object should be composed of several different Koch-type constructions, with varying color schemes.

You should start from detailed understanding of recursive codes for the basic Koch curve: my_line.m, mother_shape.m, run_koch.m

my_line.m is a Matlab code for ploting a line og a given length, at a given angle, from a given satrt position. This is a convenient representation of line drawing for building Koch-type objects.

mother_shape.m is the main Matlab code specifying a recursive function for plotting the basic Koch curve. You will need to play around this function to create more complex Koch-like constructions.

my_line.m is a Matlab code for running a simple Koch curve demo. It iterates through several levels at which the objects are constructed and for each level saves the corresponding images and an .eps file.

After uderstanding the codes for simple Koch curve, design several more complex self-similar objects by modifying the mother_shape.m code. These objects should then be combined into a single, visually pleasing final object. You should explore using different color schemes for different parts of the final object.

Preparing for the exam - Sample Questions

• Sorting
Handouts: Sorting Algorithms
• - What constitutes a sorting problem?
- Describe sorting algorithms discussed in the module.
- What is the "Big O" notation? How can it be used for assessing computational complexity of sorting algorithms?
• Recursion
Handouts: Recursion
• - What is the main feature of recursive algorithms/functions?
- In what kinds of situations would you use recursive algorithms?
- What is the role of "base case" and why is it important?
- What is the call stack of function calls while a recursive function is evaluated?
- Write down recursive functions for problems that can be naturally cast in a recursive manner - e.g. factorial, Fibonacci series etc.
• Self-similar objects
Handouts: Self-similarity
• - What is the main feature of self-similar objects?
- What kinds of self-similar objects can be found in nature? How can their self-similarity be used to generate their images
- Why are recursive functions natural tools for generating self-similar objects?
- Decribe a simple self-similar object and outline how it can be generated using a recursive function.
• Mandelbrot and Julia sets
Handouts: Mandelbrot and Julia sets
• - What are complex numbers and how can we manupulate them (addition, multiplication)?
- Describe how a dynamical system can be defined by repeated application of the same mapping on some space
- What is the dynamics behind Mandelbrot set?
- Define Mandelbrot set
- How can visually appealing images of Mandelbrot set be created by colour-coding the escape rates of trajectories of the corresponding dynamics? - What is the dynamics behind Julia sets?
- Define a Julia set
- How can visually appealing images of a Julia set be created by colour-coding the escape rates of trajectories of the corresponding dynamics?

This page is maintained by Peter Tino. Last updated on 16 Jan 2014.