CSE 6512 Randomization in Computing Fall 2011

CSE 6512 Randomization in Computing

Fall 2011


Instructor: Sanguthevar Rajasekaran (RAJ, equivalently);


Office Hours: M W 2:00 to 3:30 PM, 257, ITEB, 6-2428; rajasek@engr.uconn.edu


Randomization is a powerful technique that has found applications in varying domains of science and engineering. Testing whether a given integer is a prime, several difficult optimization problems, protein folding, sorting a given sequence, n-body simulations, flow dynamics, linear programming problems, maximum matching, early vision problems such as histograms computation, and data mining are only a few of the numerous problems that have been solved using randomization. In this course we introduce some basic as well as advanced topics in randomization.

Topics to be Covered include Basics of probability theory, Different types of randomization, Some simple problems, Sorting and selection, Hashing and skip list, Finger-printing, Packet routing, Parallel algorithms, Combinatorial optimization, External memory algorithms, etc.

Pre-requisite: Exposure to data structures and algorithms will be helpful.


1) R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995.

2) E. Horowitz, S. Sahni, and S. Rajasekaran, Computer Algorithms, Silicon Press, 2008.

3) Additional references will be supplied.

Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Lecture 10

Lecture 11

Lecture 12

Lecture 13

Lecture 14

Lecture 15

Lecture 16

Lecture 17

Lecture 18

Lecture 19

Lecture 20

Lecture 21

Lecture 22

Lecture 23

Lecture 24

Lecture 25

Lecture 26

Homework 1 due on November 1, 2011 Solutions

Exam I on November 29th at 5PM in CB 101; Helpsheet; Solutions

Project Presentations on December 17th starting from 9AM in ITEB 125 (or ITEB 201).