Florida Institute of Technology

Instructor: Debasis Mitra

The syllabus is here: Grad,

UG.

Detailed but tentative list of topics are here: course content

Florida Tech Student Handbook on Cheating and Paligiarism: http://www.fit.edu/studenthandbook/print.php#policy_2490

Expectations from students are:

(1) Dry run on as many examples as possible for each algorithm,

(2) Analyze and be sensitive to time/steps and space requirements,

(3) Modify a problem and see how a known algorithm should be
adapted for the target problem,

Pre-requisite knowledge:

(1) Discrete Mathematics, (2) Data structures, and
(3) Programming.

WARNING:

Disclaimers to the lecture notes:

*THESE NOTES ARE FOR HELPING YOU TO STUDY THE TEXT BOOK. I
KEEP UPDATING THESE AND WILL NOT BE RESPONSIBLE IF YOU FIND
THAT THE NOTES HAVE CHANGED AFTER YOU HAVE PRINTED IT. I TRY TO CHANGE
THE ASSOCIATED DATE WHEN I MAKE THE LAST UPDATE.*

+++++++++++++++++++ Lecture Notes +++++++++++++

Lecture notes from clrs book site

The introduction , in .doc . (9/14/15)

A motivating starter talk

A lay-person's presentation on Max-subsum algorithms. (8/18/14)

Divide and Conquer slides, and Notes on sorting. (8/19/15)

A cute QuickSort animation, and another one

Kesan found some cool animation on sorting here

*You may also like to read the following modules. *

Notes on Recurrence equation. (8/23/11)

Notes on Recursive & Iterative algorithms. (8/23/11)

Dynamic Programming - Algorithm (9/16/2015),

Backtracking with Branch and bound - Algorithm types(9/21/2015),

Some notes on Game search (9/16/15).

Greedy - Algorithm types (10/1/2015),

Graph algorithms (11/23/15).

Basics of Complexity Theory (10/26/15).

Linear Programming (10/29/15).

FFT (11/30/15).

Core of the syllabus: Old notes on Algorithm types (9/29/11),

Dynamic programming approximate String alignment algorithm

Graph algorithms text notes (9/30/13).

On Union-Find (8/23/11).

Parallel Programming (11/20/2013),

Notes on String matching algorithms. (8/23/11)

Notes on Linear Programming algorithms, & Slides (10/30/12)

Summarizing on FFT. (9/5//12)

Slides on FFT from CMU ECE (8/23/11)

Here is the link to the interactive applet (found by: Bradley Watson), http://www.cse.illinois.edu/iem/fft/rcrsvfft/

Notes on NP-hardness. (11/1/11)

On Number theory algorithms from Srividya and George (8/23/11).

-------------- Resources:

A discrete math online book from Dartmout h:
https://math.dartmouth.edu/archive/m19w03/public_html/book.html

An algorithm visualization project page, Check it out!

A nice sorting vizualization
posted on youtube (brought to our attention by Samuel Knight on cs-forum)

Stanford course on Algorithms.

A nice intro to Matlab

OpenCL C++ header files from Khronos

OpenCL at Geeks3D
, points to a great tutorial from AMD with sample code targeted to ATI cards, & tons of resources

A good sample group-reoprt from Spring 2011 project by guest lecture in 2010 on CUDA.

Using of GPU on paragon system: Keith's instruction,

the 2013 instruction from Keith.

A recent faster FFT algorithm for sparse spectrum paper in SODA-2012 from MIT.

ACM Turing award 2013, Leslie Lamport, Microsoft Reasearch,
"Advances In Reliability and Consistency of Computing Systems"

<<<<<<<<<<<<<<<<<<<< Fall 2015 >>>>>>>>>>>>>>>>>>>>>>

UG CSE4081: CRF 402, MW 5 - 6:15 pm

Grad CSE5211: Olin LS 130, MW 8 - 9:15 pm

IMP: Dated activities table (always in progress, now, contains last year's activities with current semester's dates):

Grad

Undergrad

Grad Pre-course quiz 0

Exam 1 on introduction, divide and conquer, and dynamic programming: key

Exam 2 on dynamic programming, backtracking, greedy and Graph algorithms: key

Exam 3 on graph agorithms, linear programming, and complexity theory: key

Final exams: Undergrad key , and Grad key

UG Grades

Grad Grades

======================== Fall 2014 ========================

GPU Project for the Undergraduate Class.

Final key: a template version

UG student project data: unblur this image.

UG Std Grades

Grad Std Grades

======================== Fall 2013 ========================

UG CSE4081: Skurla 460, MW 5 - 6:15 pm

Grad CSE5210: Crawford 420, MW 6:30 - 7:45 pm

IMP: Dated activities table: Grad

Grad Quiz 1

Grad Quiz 2

Grad Quiz 3

UG Exam 1 key

UG Exam 2

UG Homework 3 announced, due Oct 7.

Key to Final

======================== Fall 2012 ========================

Crawford 404, MW 6:30-7:45 pm

A dated course plan for Fall 2012

Home work (UG), due 10/10/12 W.

Key of Quiz 2

Key to Final.

Grades

======================== Fall 2011 ========================

Crawford 210, TR 5-6:15pm

A dated course plan for Fall 2011

Project announced, in "plan" document

Assignment Sep 8 Thursday: complete FFT example [5 pts],

Quiz 1.

Quiz 2.

Key to Final.

Grades

======================== Fall 2010 ========================

Crawford 210, TR 5-6:15pm

A dated course plan for Fall 2010.

Some pointers on FFT:

A cute one, from Physicists: http://www.relisoft.com/Science/Physics/fft.html

Another code, with visual of the divide-N-conquer: http://cnx.org/content/m12016/latest/

Another math description, in connexion: http://cnx.org/content/m10964/latest/

A code, but not much for understanding: http://www.codeproject.com/KB/recipes/howtofft.aspx

Another intro-level article from MIT:
on fft

Good old wiki: http://en.wikipedia.org/wiki/Fast_Fourier_transform

AND, THE TEXT BOOK Chap 30, READ IT!!!

FFT-basics-myview

Quiz-1 was on Sept 9, '10

PROGRAMMING ASSIGNMENT 1 (*Due: Sep 14 Tuesday, group of 2*): Implement Quick Sort algorithm.
Make sure you have separate routines for higher level recursive QuickSort, which calls the QuickPartition.
Hard copy report: commented code, runs with two sample inputs.

Simple sample parallel code demo/presentation, on 9/16

Staus report due by e-mail 9/20 3pm

A few graph algorothims' pages (temporarily online)

Quiz 2

Test 3

Grades

========== Fall 2008 =========

A dated course plan for Fall 2008.

Short Quiz (half hr, closed book) on Sorting Algorithms on 9/2/08.

Short Quiz (half hr, closed book) on Greedy Algorithms on 9/11/08.

Submit your answers as hard copy.

Home Work 1 and Programming Project 1
*NOTE: Program Due Oct 7*

Home Work 2

Self study Schedule

Programming Project 2

First Exam Questions

Home Work 3 (Due: Oct 28, Pts: 15): Redo Exam-1

Due Nov 4: Exchange with your partner as I assign, and collaboratively write brief
comments on each one's each wrong answer (1-2 pages total for both).

DUE NOV 4: ANONYMOUS class feedback: separately on course content - what you would like to
exclude, what else to include, etc; and on delivery mechanism, what was good, what
I could do to make the course more effective. Print on one sheet total. THANKS.

Programming Project 3

* SUBMIT BY SUNDAY 12/14/08 *

Grades

---------- Fall 2007 ---------

A dated course plan for Fall 2007.

Submit your answers as hard copy.

Home Work 1/ Programming Project 1

Home Work 2/ Programming Project 2

Home Work 3/ Programming Project 3
*(Q2 formula corrected)*

Home Work 4 (CACM reading assignment)

Home Work 5/ Programming Project 4 * NEW*

First Exam Questions

Chapters presentation schedule
for November'07

Second Exam Questions

**Classes on the last week are not cancelled just because we have finished our exams!!**
We may have a quiz on 12/3/07 Tuesday on the SCC algorithm and the Articulation point algorithm.

Grades

---------- Fall 2006 ---------

Submit your answers as hard copy.

Home Work 0, due 9/3/06

Home Work 1/ Programming Project 1

Home Work 2/ Programming Project 2

*Check the Euler ckt algorithm here*

Quiz 1

Undergraduate presentations

Graduate class Mid Term, on October 19, Thursday

Graduate class Mid Term II, on November 2, Tuesday

Graduate students' self-study: Prepare for presenting at least three theorems/lemmas and their proofs
(of your choice) from this paper, and submit your
presentation to me on [Dec 5, Tuesday]

Graduate presentations:

Nov 28: Computational geometry: cross products, segmets-intersect,
any-segments-intersect, Graham's scan (Theo, Alexander)

Nov 30: Number theoretic Algorithms (RSA): Chinese remainder theorem, RSA,
correctness of RSA, anything else you want to talk on (Montri, Stephen, Nicolas)

Dec 5: Polynomial multiplication, DFT/FFT: polynomial mult, DFT, FFT (Jacek, Asim, Nathan)

Last Assignment,
(except question 3 therein, this is Graduate Comprehensive Question for Fall 2006), due Dec 5.

Programming Project 3

Please provide me some feedback about the course in 1 page. Type it and submit it
without your name/pointer on it, during the final. Divide the feedback into two groups: on the
course content, and on the course delivery. Try to be objective and helpful to me for
my future courses.
Thanks!

Grad Final answer key

Grades

---------- Fall 2005 ---------

Submit your answers as hard copy.
Home Work 0, due 8/30/05

Home Work 1, due 9/8/05

Home Work 2, due 9/20/05

Undergraduae Group Project, due 11/10/05

Graduate Class Project (individual), due 11/10/05

Home Work 3, due 9/29/05 [I NEED THE PAPERS BACK]

*Mid Term on Thursday 10/06/05 *

Self-study on Quantum Computing

Home Work 4, due 11/03/05

*Feedback: Thanks!
Final: Thursday 12/15/05 in the respective class rooms: UG: 3:30-5:30 pm, Grad: 6-8 pm.
Excluded: Big-O definition, recurrence equation and Initialization-simplex
algorithm. Exam is of the same format as before. You are allowed to bring
any text book, class note, or your hand written notes from the class,
and nothing else. You have to write answers on your own clean papers.
Grad final
Grades
*

*
---------- Fall 2004 ---------
A quiz on basics.
The Home Work 1, due Tuesday Oct 5
in class.
Graduate Class project will be developed
on this link. (11/2/04)
Undergraduate Class project will be developed
on this link. (11/2/04)
Midterm exam on Tuesday October 26
Home Work 2 due Nov 11, 2004.
Quiz on November 30, 2004.
(Closed book, possibly short questions format)
Syllabus: everything except string matching algorithms
I may take more quizes on any class in December.
Check the current grades here.
For the official cut-off on grades follow the
syllabus. I reduce the cut-off from semester
to semester in order to accommodate some borderline cases.
The reused spreadsheet templates occasionally have older information
hanging around through the semester but the issue of cut-off was also
discussed in the class repeatedly.
---------- Fall 2003 ---------
Home Work 1. Due 9/9/03 in class, in hard copy.
*

*
Home Work 2. Due 10/07/03 in class, in hard copy.
Print your name and status (Undergrad/Grad).
*

*
Home Work 3. Due 11/11/03 in class, in hard copy.
Print your name and status (Undergrad/Grad).
*

*
Fall 2003:Grades up to mid term.
*

*
Graduate Class project will be developed
on this link. (11/18/03)
Undergraduate Class project will be developed
on this link. (11/18/03)
A comment on Fall 2003 final exam: except for proving Big-Oh notations and
questions from the sorting-chapter, everything else is included.
*

*
---------- Fall 2002 ---------
Fall 2002:Key to the Short Test.
*

*
Sorry, nothing else is available for Fall02.
*

Some theory links:

Theory Workshop, March, 2007

An electronic colloquium on Computational Complexity.

A nice JAVA (TM) data structures library.

*Materials are copyrighted to me (year 2004). Most of the materials
have been developed before I joined FIT.*
*E-mail:
dmitra@cs.fit.edu*