Abstract

Programs run much faster than they used to do a few decades ago not only because of better hardware but also because of better algorithms developed for solving problems. In this course we look into algorithms for some traditional problems like sorting, and those related to graph theory, etc. We will see different styles of algorithm development with emphasis on resource sensitivity: divide and conquer, greedy strategy, dynamic programming, and branch & bound techniques. Some examples will be worked out in the class to explain these strategies, and students are expected to be able to hand simulate runing the algorithms on problem instances. The course concludes with a simple introduction to the theory of NP-completeness and its significance in computer science.

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.

Quantum Computing Resources:
Google-2019 machine
MIT Ising machine using common analog electronic circuit's spin coupling.

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
An animated presentation for lay-audience with 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:
Diophantine equation for 42 is solved (the last unsolved number between 1-100)! Using crowd-sourced parallelization.

2019 Goedel Prize on PCP theorem
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"

PRE-MIDTERM-KEY for Dr. Shoaff, 2/28/18/W/11am/Crawford2010.

<<<<<<<<<<<<<<<<<<<< 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).

Test 1 key.

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

Final.

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.