Database Systems



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: . edu/~dmitra/Algorithms/

Office Hours: T/Th 1-3 pm

Detail plan for CSE 4081, Fall 2013:

|Date |Activities Planned |Comments |

|Aug 19, M |Introduction. |Suggestion: code Fibonacci series 2 algorithms, and time|

| |#arcs on complete graph: Inductive pf. |against input sizes |

|Aug 21, W |Four Max-sub-sum algorithms, |Gang up by 2 for coding! |

| |Divide & conquer: Merge Sort |Project 1 prep: Look for a small game for 2 persons |

| |Recurrence Eq, Master’s theorem: AlgType-slide 22 |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 |Backtracking: basics, 0-1KS, Bounding fn |Homework 1: …/13Fall/UgHw1-Fa13.doc |

|(Drop w/o W grade, |Game search – basics, Game search, Alpha-beta |Due: Sep 4 W |

|Aug 30) |pruning | |

|(Sep 2 M, Labor day)|- - - - | |

|Sep 4, W |0-1 KS BT tutorial |Hw1 due, hard copy. |

| |Game search again |Thought of a game, each group? |

| |(?Turnpike reconstruction) |Resources for GPU? |

| |Programming Assignment-1: Game search | |

|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 |Due: Board evaluation plan, submit hard copy/group |

| |DP: Optimal Binary-tree organization | |

|Sep 16, M |Greedy: Multi-processor Last-FT, | |

| |Huffman encoding , complexity of Huffman | |

| |Rational-KS | |

|Sep 18, W |Graph Alg: Basics, |Hw2 due, hard copy. |

| |Graph Alg: Intro to topological sort |HW3 due Oct 7 M: |

| |Topological-sort, |…/13Fall/UgHw3-Fa13.doc |

| |Q-based topo-sort | |

|Sep 23, M |Project 1 presentations. | |

|Sep 25, W |Djikstra’s algorithm, |Project2-A small ‘hello world’ type program on GPU |

| |& proof |should be done by today! Submit a screen shot or demo in|

| | |class. |

| | |Two presented GPU start-up ( |

|Sep 30, M |Min-spanning tree: Prim, Kruskal |Articulation points detection |

| |Depth First Search: Strong-connected component | |

|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 |Scientific Computing (Spring’14) as |Going! Going! ..: Those who missed Hw3, must complete |

|(Drop with ‘W’, Oct |Linear Programming Ch 29 |it, and , |

|25) |Quiz 2 papers return and discussion |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 |- - - - |Happy Holidays! |

|Thanksgiving | | |

|Dec 2, M |Back up project-2 demo? | |

| |Multi-threading / parallelization Ch 27 | |

|Dec 4, W |Graph Algorithm –repeat? | |

|(Last day) |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:

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download