COMPSCI 330: Design and Analysis of Algorithms

 
COMPSCI 330
Design and Analysis of Algorithms
 
Rong Ge
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
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!
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).
 
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
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.
Algorithms
 
From wiki: In mathematics and computer science,
an algorithm is a self-contained sequence of actions
to be performed.
 
 
Designing an Algorithm - Basics
 
Divide and conquer
Dynamic programming
Greedy algorithms
Designing an Algorithm - Examples
 
Graph algorithms
Shortest paths
Minimum spanning tree
Bipartite matching
Data structrues
Hashing
Disjoint sets
Designing Algorithm – General Tools
 
Linear Programming
Formulation
Duality
Algorithms
 
Designing Algorithm - Intractability
 
What (we believe) cannot have efficient algorithms.
P vs. NP
NP completeness
Reductions
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.
Proofs for algorithms?
 
Correctness:
12343*9432583 = 116426471969 ?
(No: 116426
3
71969)
 
More complicated:
Why should I believe this is the
shortest path to the airport?
Proofs for algorithms?
 
Running time: How long should the algorithm take.
 
 
 
 
 
Space: How much memory does the algorithm
need.
 
Other aspects (not in this course)
 
Privacy/security
 
Other aspects (not in this course)
 
Fairness
Goal
 
Design new algorithms for applications you care.
 
Prove correctness/running time for algorithms.
How to write a proof?
 
Program
Unambiguous instructions
for computers to solve a
problem
Function/subroutine
System call/packages
Loop/Recursion
……
 
Proof
Unambiguous way of
certifying a mathematical
statement.
Lemma
Theorem
Induction
……
 
Will see many examples in class.
Very similar to writing a program.
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
]
Induction Hypothesis
Induction Step
Base Case
 
Rest of the lecture (on whiteboard)
 
Asymptotic notations
 
One of the earliest algorithms: Euclid’s algorithm
Slide Note
Embed
Share

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.


Uploaded on Mar 13, 2024 | 1 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

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

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#