Logistics for COMPSCI 330 include lecture and recitation schedules, grading breakdown, exam conflicts, contact information, and lecture format. Dr. Rong Ge emphasizes hands-on learning through proofs and recording lectures. The course covers algorithm basics such as divide and conquer, dynamic programming, and greedy algorithms, as well as examples like graph algorithms, shortest paths, and data structures.

• Lecture Schedule
• Grading
• Exam Conflicts

finnigan Follow

Uploaded on Mar 13, 2024 | 0 Views

COMPSCI 330: Design and Analysis of Algorithms

PowerPoint presentation about 'COMPSCI 330: Design and Analysis of Algorithms'. This presentation describes the topic on Logistics for COMPSCI 330 include lecture and recitation schedules, grading breakdown, exam conflicts, contact information, and lecture format. Dr. Rong Ge emphasizes hands-on learning through proofs and recording lectures. The course covers algorithm basics such as divide and conquer, dynamic programming, and greedy algorithms, as well as examples like graph algorithms, shortest paths, and data structures.. Download this presentation absolutely free.

Presentation Transcript

1. COMPSCI 330 Design and Analysis of Algorithms Rong Ge

2. Logistics Lectures: Tuesdays and Thursdays 3:05 - 4:20 PM Recitations: Check your own schedule Recitations are required! First week: Optional (Review of Induction) Students in Friday morning sessions should all go to LSRC D106. Webpage: http://www.cs.duke.edu/courses/spring19/compsci330/ Office hours: Tuesday after class to 5:30 pm Friday at 3 4 pm TA office hours: See course webpage

3. Grades Homework 40% 2 Midterms 30% Final Exam 30% Homework should be typed and submitted to Gradescope. Read (and follow) the guideline on collaboration. Go to office hours!

4. STINF,Exam conflicts Kate O Hanlon is our teaching associate. Email: kate.o.hanlon@duke.edu Please take a look at the tentative schedule and if you have a conflict for any of the exams please let Kate know as early as possible. For STINF please use a web form (will be posted on piazza later).

5. Contact us Piazza: http://piazza.com/duke/spring2019/compsci330 Please use for all general discussions. Piazza is required! All announcements will be on Piazza. Grading questions: Please submit regrade requests through GradeScope. Homework requests will be handled by grad TAs and exam requests will be handled by myself. Send me an email: rongge@cs.duke.edu

6. Lecture format Slides first, then go to the board (tablet). Best way of learning a proof is to write it down yourself. I will try to record the lectures hopefully the technology does not fail.

7. Algorithms From wiki: In mathematics and computer science, an algorithm is a self-contained sequence of actions to be performed.

8. Designing an Algorithm - Basics Divide and conquer Dynamic programming Greedy algorithms

9. Designing an Algorithm - Examples Graph algorithms Shortest paths Minimum spanning tree Bipartite matching Data structrues Hashing Disjoint sets

10. Designing Algorithm General Tools Linear Programming Formulation Duality Algorithms

11. Designing Algorithm - Intractability What (we believe) cannot have efficient algorithms. P vs. NP NP completeness Reductions

12. Analysis - Proofs Proof: Systematic way of convincing the reader that a mathematical statement is necessarily correct. Writing proofs is a major component of this course.

13. Proofs for algorithms? Correctness: 12343*9432583 = 116426471969 ? (No: 116426371969) More complicated: Why should I believe this is the shortest path to the airport?

14. Proofs for algorithms? Running time: How long should the algorithm take. Space: How much memory does the algorithm need.

15. Other aspects (not in this course) Privacy/security

16. Other aspects (not in this course) Fairness

17. Goal Design new algorithms for applications you care. Prove correctness/running time for algorithms.

18. How to write a proof? Will see many examples in class. Very similar to writing a program. Program Proof Unambiguous instructions for computers to solve a problem Function/subroutine System call/packages Loop/Recursion Unambiguous way of certifying a mathematical statement. Lemma Theorem Induction

19. Example Prove that 1+2+3+ + n = n(n+1)/2 for all integers n. Idea: Prove(n) Prove [1+ +k = k(k+1)/2] for k = 1 For k = 1 to n-1 Show if [1+ +k = k(k+1)/2], then [1+ +k + (k+1) = (k+1)(k+2)/2] Base Case Induction Hypothesis Induction Step

20. Rest of the lecture (on whiteboard) Asymptotic notations One of the earliest algorithms: Euclid s algorithm