
Lectures  Teaching Assistant  Resources
Description:
This
course is an introductory graduate course on the design and analysis of
algorithms. The course builds on an undergraduatelevel study of the analysis
and implementation of data structures and algorithms (COMPSCI 201). The goal is
to introduce a number of important algorithm design techniques as well as basic
algorithms that are interesting both from a theoretical and also practical
point of view. We will cover basic algorithm design techniques such as
divideandconquer, dynamic programming, and greedy techniques for
optimization. We will cover techniques for proof of the correctness of algorithms
and also asymptotic analysis of algorithm time bounds by the solution of
recurrence equations. We will apply these design and analysis techniques to
derived algorithms for a variety of tasks such as sorting, searching, and graph
problems. Some specific algorithm topics include: deterministic and randomized
sorting and searching algorithms, depth and breadth first search graph
algorithms for finding paths and matchings, and algebraic algorithms for fast
multiplication and linear system solving.
Lectures
will focus on introducing major algorithmic principles of design and analysis,
along with mathematical analysis of algorithmic problems. The weekly lab
section will build on that material to explore questions of implementations and
applications to real world problems.
Prerequisites:
An
undergraduatelevel course on the analysis and implementation of data
structures and algorithms (COMPSCI 201 or equivalent) and also four semesters
of college mathematics. This course requires a certain amount of mathematical
sophistication (e.g., as required to solve recurrence equations). A quiz on
recurrence equations early in the course will provide you with some feedback on
whether your mathematics training will suffice. If you feel that you may not
have sufficient background, please talk with an instructor.
Meetings:

Times: Tues
& Thurs 11:45 PM – 1:00 PM Room: LSRC B101 
Instructor:
Professor John Reif 

Office: 

D223 LSRC Building 
Phone: 

9196606568 
Email: 


Web page: 


Office hours: 

Tues, Thurs: 1:00PM – 3:00 PM 
TA: Sravya Yandamuri 





PhD Student 


Office: 

see Office
Hours 

Phone: 

9196604019 

Email: 


Web page: 


Office hours: 

Tuesday 3:00pm4:00pm
at N306 and Friday 3:00pm4:00pm at LSRC D301 

TA: Tiancheng Liu: 





PhD Student 


Office: 

LSRC N306 

Phone: 

4243871212 

Email: 


Web page: 


Office hours: 

Friday
9:30am11:30am 

TA: Xiaoming Liu: 





Masters Student 


Office: 

N004 North
Building 

Phone: 

9196604019 

Email: 


Web page: 


Office hours: 

Monday and
Wednesday 2:00pm3:00pm 

Course material:
· Solutions to Selected exercises and
problems in CLRS
Optional
auxiliary reading (other good reference books):
Course Topics:
Summary of topics covered
and lecture notes:
Consult
the schedule of Lectures for
a list of topics and a copy of lecture notes for the lectures to date. Other
handouts can be found in the handouts directory. See resources page for additional information.
Homework assignments:
All assignments will be
released to Students on the course Sakai webpage, and all solutions should
similarly be submitted on the course Sakai webpage. No credit is given for late
solutions. You should turn in what you have on time for partial credit rather
than receive a 0. For exceptional circumstances, see the instructor in advance,
rather than after the due time. Our policy is that one (and only one) homework
during the entire term is allowed not to be handed in, at no loss of credit.
Furthermore, if you hand in all the homework, then we will drop the lowest
graded homework.
Students will be asked to
design algorithms for classic problems and provide mathematical analysis of
correctness and asymptotic efficiency. Students will turn in a written set of
solutions. It is recommended but not required that LaTeX be used for
typesetting homework problems. If
handwritten solutions are illegible, they will not be graded. Details about proper style for writing up homework solutions and some guidelines
for grading are available.
Homeworks are due roughly
every second week and must be turned in before class on Wednesday of the week
they're due. No credit is given for late solutions. For
exceptional circumstances, see John Reif in advance, rather than after
the due time.
Honor code: For
homework problems, discussion among students is permitted, but students must
write up solutions independently on their own. discussion among students is
permitted, but students must write up solutions independently on their own. No
materials or sources from prior years' classes or from the Internet can be
consulted. For details about what is acceptable, see this honesty matrix.
During
every exam: all calculators, computers, cell phones, wireless or
bluetoothconnected devices, and all other electronic devices must be
identified and handed over to the person proctoring the exam. Breaking
the rules can result in expulsion. Each student is required to make a
copy of this paragraph, sign it indicating that the contents are understood,
and turn it in to John Reif.
Grading:
There
will be no makeup exams for missed exams. Missing one of the three
midterm exams will result in the remaining midterms and final exam grades being
reweighted appropriately. By University Policy, missing the Final exam results
in a grade X.
Anonymous course feedback: Anonymous comments