Analysis of Algorithms
CSE 4081, Fall 2013
Instructor: Debasis Mitra, Ph.D.
Office: Harris 325 E-mail: dmitra ‘at’ cs.fit. edu
Class Home Page: http://www.cs.fit. edu/~dmitra/Algorithms/
Office Hours: T/Th 1-3 pm
Detail plan for CSE 4081, Fall 2013:
Date / Activities Planned / CommentsAug 19, M / Introduction.
#arcs on complete graph: Inductive pf. / Suggestion: code Fibonacci series 2 algorithms, and time against input sizes
Aug 21, W / Four Max-sub-sum algorithms,
Divide & conquer: Merge Sort
Recurrence Eq, Master’s theorem: AlgType-slide 22 / Gang up by 2 for coding!
Project 1 prep: Look for a small game for 2 persons
Proj 2 prep: Look for a GPU accessible machine, to code on in CUDA/OpenCL
Aug 26, M / Recurrence trees of height n, log-n, binary search in second tree
Comparison sort’s omega, count-sort
D&Q: Matrix Mult, Strassen Alg: AlgType-22
Aug 28, W
(Drop w/o W grade, Aug 30) / Backtracking: basics, 0-1KS, Bounding fn
Game search – basics, Game search, Alpha-beta pruning / Homework 1: …/13Fall/UgHw1-Fa13.doc
Due: Sep 4 W
(Sep 2 M, Labor day) / - - - -
Sep 4, W / 0-1 KS BT tutorial
Game search again
(?Turnpike reconstruction)
Programming Assignment-1: Game search / Hw1 due, hard copy.
Thought of a game, each group?
Resources for GPU?
Sep 9, M / DP 0-1KS / HW2 on BT due Sep 18 W:
…/13Fall/UgHw2-Fa13.doc
Discuss on project-1 status
Sep 11, W / DP Matrix chain multiplication
DP: Optimal Binary-tree organization / Due: Board evaluation plan, submit hard copy/group
Sep 16, M / Greedy: Multi-processor Last-FT,
Huffman encoding , complexity of Huffman
Rational-KS
Sep 18, W / Graph Alg: Basics,
Graph Alg: Intro to topological sort Topological-sort,
Q-based topo-sort / Hw2 due, hard copy.
HW3 due Oct 7 M:
…/13Fall/UgHw3-Fa13.doc
Sep 23, M / Project 1 presentations.
Sep 25, W / Djikstra’s algorithm,
& proof / Project2-A small ‘hello world’ type program on GPU should be done by today! Submit a screen shot or demo in class.
Two presented GPU start-up J
Sep 30, M / Min-spanning tree: Prim, Kruskal
Depth First Search: Strong-connected component / Articulation points detection
Oct 2, W / Project-1 Presentations/ Demo (for rest of the groups).: including showing source code, and sample run.
All groups: freeze code before class.
Oct 7, M / Presentation continues / Hw 3 due
Oct 9, W / NP-hardness basics, SAT
(Fall Break Oct 14-15) / - - - -
Oct 16, W / Guest lecture / Work on your project 2 / Due: Submit a Project-1 Report / group, send me by e-mail today
Start Project-2: Output n-th row for the Pascal triangle, Implement with GPU, Presentation on Nov 20
Oct 21, M / Quiz-1 on DP, Greedy, Backtracking, & Graph Alg : Open book and clean class notes, nothing else
Oct 23, W / NP-hardness: proof 3SAT is NP-C / Project status discussion
Oct 28, M / Complexity FAQ,
What to do with NP-C problems;
Linear Programming Ch 29
Oct 30, W
(Drop with ‘W’, Oct 25) / Scientific Computing (Spring’14) as
Linear Programming Ch 29
Quiz 2 papers return and discussion / Going! Going! ..: Those who missed Hw3, must complete it, and ,
Do a two-pager report on Quantum computing, in order to recover some grade on Hw3.
Nov 4, M / Linear Programming continued / Any Proj-1 report missing?
TylerRobinsBlackjack_Report_Robbins.docx
KimReversireport.pdf
JustinBlackmanReversi.docx
JustinBlackmanBoardSquare.java
Gianella FuentesProject1 Report.doc
Gianella FuentesDeck.java
Gianella FuentesCurrentHand.java
Gianella FuentesCard.java
Gianella FuentesBlackjackHand.java
Gianella FuentesBlackjack.java
DelPreteReport.docx
Dany-report.docx
JacobDufault Checkers.docx
Nov 6, W / A short quiz on Graph Alg. & NP?
Nov 11, M
Veterans Day / - - - -
Nov 13, W / Project-2 presentation / Anyone has a softcopy of the previous Exam-1?
Freeze coding today.
Presentation: describe your algorithm briefly, give a demo, compare with CPU version, show code, any insights/experience?
Report Due: Nov 25
Nov 18, M / Project demo continued
Nov 20, W / Multi-threading / parallelization Ch 27
Nov 25, M / Multi-threading / parallelization Ch 27 / Due: Write a small report - provide/discuss: (1) your code; (2) your serial algorithm; then, (3) parallelized algorithm for shared memory; (4) description of your GPU architecture – you should know it – a snapshot output is better; (5) coding issues with this GPU configuration within your code; (6) complexity analysis; (7) comparison of actual timing with CPU based sequential implementation – against input sizes, etc.
Nov27-Dec1 Thanksgiving / - - - - / Happy Holidays!
Dec 2, M / Back up project-2 demo?
Multi-threading / parallelization Ch 27
Dec 4, W
(Last day) / Graph Algorithm –repeat?
Final Exam discussion
Dec 9, M,
6-8pm
Term Paper topics: Quantum computing at D-wave, Quantum cryptography, GPGPU computing versus Intel Xeon Phi coding, Current status of P vs NP, ,,,
/13Fall/UgPopQz1-Fa13.docx
Project-1 Adversarial game
1. Justin Blackman & Jason Fisher: Reversi / Othello
2. Kim Day & Tyler Jackson: Othello
3. Jacob Default & Russell MacDonald: Checker-like, presented 9-23-M, rules are too simple – computer do not gets chance to beat you! Strategy and rule has some conflict when the piece moves to the end of board – should be encouraged. Algorithm+implementation looks ok. Language: lua, good for scripting?
4. Joseph Del Prete & none: Gomoku
5. Qusay Alonaizan & Gianella Fuentes: Blackjack
6. Tyler Robbins & Mahjabin Alam: Blackjack
7. Shaun Davenport & Chenk Li: Blackjack
8. Iordanis Fostiropoulas & Patrick Hagarty: Checkers
Presentation/Demo:
Game rule complexity:
Correctness:
Originality:
Source code clarity:
Team work: