Fall 2023

CSE 6512 Randomization in Computing

Fall 2023


Instructor: Sanguthevar Rajasekaran (RAJ, equivalently);


Office Hours: T Th 9:30 AM to 11:00 AM, 252, ITEB, 6-2428; sanguthevar.rajasekaran@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.

Requirements: Two exams worth 50%, Two Homeworks worth 10%, and a Project worth 40%.


Lecture on October 10, 2023;   Slides

Lecture on October 12, 2023;   Slides


Homework 1  due on October 5, 2023 at 11AM;   Solutions

Homework 2 due on November 16, 2023 at 11AM;  Solutions


Model Exam 1;   Solutions

Exam I on October 24, 2023 at 5PM;   Solutions;   Helpsheet


Model Exam 2;   Solutions

Exam II on November 30, 2023 at 5PM in ITEB 301;   Solutions;   Helpsheet


Some suggested project topics

Sample Project 1

Sample Project 2

Projects Presentation on December 5, 2023 at 11AM;


Lecture Notes 

Lecture Notes on Basic Algorithms