July 2010 - csc-general

Talk: Elyot Grant: The Incompressibility Method: Tuesday July20th, 4:30pm, MC2066
by Computer Science Club 17 Jul '10

17 Jul '10

Elyot Grant is giving a talk on Tuesday July 20th at 4:30pm in MC2066. The information follows below: Title: The Incompressibility Method Abstract: Heapsort. It runs in $\Theta(n \log n)$ time in the worst case, and in $O(n)$ time in the best case. Do you think that heapsort runs faster than $O(n \log n)$ time on average? Could it be possible that on most inputs, heapsort runs in $O(n)$ time, running more slowly only on a small fraction of inputs? Most students would say no. It "feels" intuitively obvious that heapsort should take the full $n \log n$ steps on most inputs. However, proving this rigourously with probabilistic arguments turns out to be very difficult. Average case analysis of algorithms is one of those icky subjects that most students don't want to touch with a ten foot pole; why should it be so difficult if it is so intuitively obvious? In this talk, we shall explore the incompressibility method---an interesting and extremely powerful framework for determining the average-case runtime of algorithms. Within the right background knowledge, the heapsort question can be answered with an elegant 3-line proof. The crucial fact is that an overwhelmingly large fraction of randomly generated objects are incompressible. We can show that the inputs to heapsort that run quickly correspond to inputs that can be compressed, thereby proving that heapsort can't run quickly on average. Of course, "compressible" is something that must be rigourously defined, and for this we turn to the fascinating theory of Kolmogorov complexity. In this talk, we'll briefly discuss the proof of the incompressibility theorem and then see a number of applications. We won't dwell too much on gruesome mathemtical details. No specific background is required, but knowledge of some of the topics in CS240 will be helpful in understanding some of the applications.

1 0

CSCTalk: Tuesday July 13th 4:30pm MC2066: Halftoning and Digital Art
by Computer Science Club 12 Jul '10

12 Jul '10

Edgar Bering will be giving a talk tomorrow in MC2066 at 4:30pm. Title: Halftoning and Digital Art Abstract: Halftoning is the process of simulating a continuous tone image with small dots or regions of one colour. Halftoned images may be seen in older newspapers with a specled apperance, and to this day colour halftoning is used in printers to reproduce images. In this talk I will present various algorithmic approaches to halftoning, with an eye not toward exact image reproduction but non-photorealistic rendering and art. Included in the talk will be an introduction to digital paper cutting and a tutorial on how to use the CSC's paper cutter to render creations. -- Brennan Taylor b4taylor at uwaterloo dot ca Computer Science Club http://csclub.uwaterloo.ca/~b4taylor University of Waterloo Waterloo, Ontario CANADA N2L 3G1

1 0

Friday Code Party!
by Computer Science Club 08 Jul '10

08 Jul '10

There is a CSC Code Party Friday starting at 7:00PM (1900) until we get bored (likely in the early in morning). Come out for fun hacking times. -- Brennan Taylor b4taylor at uwaterloo dot ca Computer Science Club http://csclub.uwaterloo.ca/~b4taylor University of Waterloo Waterloo, Ontario CANADA N2L 3G1

1 0

How would you like to hear about your upper-year education?
by Computer Science Club 06 Jul '10

06 Jul '10

The question has been passed onto us here at the CSC. How do students want to hear about the opportunities they have for their upper-year education? In the past a number of approaches have been attempted: 1) Professors teaching the classes will give a 10 minute introduction and answer questions. 2) Students will answer questions and talk about their experiences. 3) A couple of Professors will talk about upper-year courses in general. How would you like to hear about the upper-year courses? Do you want to know the horrors of Real-Time? The shininess of Graphics? The ridiculous things compiler writers do? Send your responses to veep(a)csclub.uwaterloo.ca please! -- Brennan Taylor b4taylor at uwaterloo dot ca Computer Science Club http://csclub.uwaterloo.ca/~b4taylor University of Waterloo Waterloo, Ontario CANADA N2L 3G1

1 0

Talk: Nomair Naeem on Dataflow Analysis on Tuesday July 6th, MC2054
by Computer Science Club 03 Jul '10

03 Jul '10

Tell your friends! Again the talk is Tuesday July 6th, 4:30pm in MC2054. Nomair A. Naeem - Dataflow Analysis === Abstract After going through an introduction to Lattice Theory and a formal treatment to Dataflow Analysis Frameworks, we will take an in-depth view of the Interprocedural Finite Distributive Subset (IFDS) Algorithm which implements a fully context-sensitive, inter-procedural static dataflow analysis. Then, using a Variable Type Analysis as an example, I will outline recent extensions that we have made to open up the analysis to a larger variety of static analysis problems and making it more efficient. The talk is self-contained and no prior knowledge of program analysis is necessary. -- Brennan Taylor b4taylor at uwaterloo dot ca Computer Science Club http://csclub.uwaterloo.ca/~b4taylor University of Waterloo Waterloo, Ontario CANADA N2L 3G1

1 0