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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- crm database example
- crm database free
- customer service database software
- client database software
- client database software free download
- free client database management software
- national student loan database for student
- database of accredited postsecondary institutions
- what is crm database system
- department of education database forms
- java database examples source code
- database analyst vs database administrator