Browse Course Material
Course info, instructors.
 Prof. Erik Demaine
 Prof. Srini Devadas
 Prof. Nancy Lynch
Departments
 Electrical Engineering and Computer Science
 Mathematics
As Taught In
 Algorithms and Data Structures
 Computer Networks
 Cryptography
 Applied Mathematics
Learning Resource Types
Design and analysis of algorithms, assignments, problem sets.
Ten problem sets will be assigned during the semester.
Problem sets should be submitted in PDF format. Formatting your problem set in LaTeX will make it easier for us to read; however, any method of generating the PDF is acceptable (including scanning handwritten documents), as long as it is clearly legible.
The problem sets include exercises that should be solved but not handed in. These questions are intended to help you master the course material and will be useful in solving the assigned problems. Material covered in exercises will be tested on exams.
Guide to Writing Up Homework
You should be as clear and precise as possible in your writeup of solutions. Understandability of your answer is as desirable as correctness, because communication of technical material is an important skill.
A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand. Sloppy answers will receive fewer points, even if they are correct, so make sure that your handwriting and your thoughts are legible. If writing your problem set by hand, it is a good idea to copy over your solutions to hand in, which will make your work neater and give you a chance to do sanity checks and correct bugs. If typesetting, reviewing the problem set while typing it in often has this effect. In either case, going over your solution at least once before submitting it is strongly recommended.
You will often be called upon to “give an algorithm” to solve a certain problem. Your writeup should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your essay should provide the following:
 A description of the algorithm in English and, if helpful, pseudocode.
 At least one worked example or diagram to show more precisely how your algorithm works.
 A proof (or indication) of the correctness of the algorithm.
 An analysis of the running time of the algorithm.
Remember, your goal is to communicate. Graders will be instructed to take off points for convoluted and obtuse descriptions.
ASSIGNMENTS  SOLUTIONS 

LaTeX Template for Problem Sets (ZIP) (This file contains: 1 .cls file, 2 .sty files, 1 .pdf file and 1 .tex file.)
You are leaving MIT OpenCourseWare
We're sorry but you will need to enable Javascript to access all of the features of this site.
Stanford Online
Algorithms: design and analysis, part 1.
SOEYCSALGORITHMS1
Stanford School of Engineering
In this course you will learn several fundamental principles of algorithm design. You'll learn the divideandconquer design paradigm, with applications to fast sorting, searching, and multiplication. You'll learn several blazingly fast primitives for computing on graphs, such as how to compute connectivity information and shortest paths. Finally, we'll study how allowing the computer to "flip coins" can lead to elegant and practical algorithms and data structures.
Specific topics in the course include: "Bigoh" notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), randomized algorithms (QuickSort, contraction algorithm for min cuts), data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of BFS and DFS, connectivity, shortest paths).
Learn the answers to questions such as:
 How do data structures like heaps, hash tables, bloom filters, and balanced search trees actually work, anyway?
 How come QuickSort runs so fast?
 What can graph algorithms tell us about the structure of the Web and social networks?
 Did my 3rdgrade teacher explain only a suboptimal algorithm for multiplying two numbers?
Core Competencies
 Matrix Multiplication
 Master Theorem
 Divide And Conquer
 Data Structures
 Bloom Filter
What You Need to Get Started
 Engineering
 Computer Science & Security
 Business & Management
 Energy & Sustainability
 Data Science
 Medicine & Health
 Explore All
 Technical Support
 Master’s Application FAQs
 Master’s Student FAQs
 Master's Tuition & Fees
 Grades & Policies
 Graduate Application FAQs
 Graduate Student FAQs
 Graduate Tuition & Fees
 Community Standards Review Process
 Academic Calendar
 Exams & Homework FAQs
 Enrollment FAQs
 Tuition, Fees, & Payments
 Custom & Executive Programs
 Free Online Courses
 Free Content Library
 School of Engineering
 Graduate School of Education
 Stanford Doerr School of Sustainability
 School of Humanities & Sciences
 Stanford Human Centered Artificial Intelligence (HAI)
 Graduate School of Business
 Stanford Law School
 School of Medicine
 Learning Collaborations
 Stanford Credentials
 What is a digital credential?
 Grades and Units Information
 Our Community
 Get Course Updates
CS 161: Design and Analysis of Algorithms (Spring 2017)
[ Course Schedule  Midterm and Final  Homework Assignments  Recitations  Resources ]
Instructor: Mary Wootters (email: marykw at cs)
Location and time: Monday and Wednesday 3:00 PM  4:20 PM, Hewlett 200
Important! Sign up on Piazza for discussions and announcements. We strongly encourage discussion and asking questions on Piazza. Questions to the course staff (that are not addressed to a specific person) can be sent using a private post in Piazza.
Course Description This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divideandconquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimumcost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching.
Prerequisites: CS 103 or CS 103B; CS 109 or STATS 116.
Requirements: 7 homework assignments (35%), a midterm (25%), and a final exam (40%). There will be no late days. However, we will drop your lowest homework grade. Note: In order to compute scores on the homework (in deciding which to drop and for averaging), we will normalize the scores by the number of points possible. That is, if 40 points were possible on the homework and you scored a 35, this would count as 35/40 = 0.875.
Course Schedule and Lecture Notes
Topics and readings for future lectures are tentative and may be changed as the course proceeds. The readings refer to the 3rd edition of CLRS (see Resources below), but older editions should be fine as well.
4/3 Introduction, Why are you here? Read: Ch. 1 (draft)  4/5 MergeSort, Recurrences, Asymptotics Read: Ch. 2.3, 3 (draft) (draft) (draft) (draft)  4/7 Homework 1 released 
4/10 Asymptotics (for real this time). Solving recurrences and the master theorem. Read: Ch. 4.34.5 DasguptaPapadimitriouVazirani Sec. 2.2: (draft) (draft) (draft)  4/12 Median and Selection Read: Ch. 9 (draft) (draft) (Note: Slides have been updated since lecture. Now with fewer typos!)  4/14 Homework 1 due Homework 2 released 
4/17 Quicksort, Probability and Randomized Algorithms Read: Ch. 7, 5 (draft) (draft)  4/19 Sorting Lower Bounds, Counting Sort Read: Ch. 8.12 > (draft) (draft)  4/21 Homework 2 due Homework 3 released 
4/24 Binary Search Trees Read: Ch. 12 > (draft) (draft)  4/26 Hashing Read: Ch. 11 > (draft) (draft)  4/28 Homework 3 due Homework 4 released 
5/1 Graphs, DFS, BFS Read: Ch. 22 Additional Reading that might be helpful: (draft) (draft)  5/3 Strongly Connected Components Read: Ch. 22.5 (NOTE: this reading assignment was garbled before, it is fixed now!) (draft) (draft)  5/ Homework 4 due (NOTE the extension to Monday) 
5/8 Dijkstra's Algorithm Read: Ch. 24.1, 24.3 (draft) (draft)  5/10 MIDTERM In class (Hewlett 200, 3:004:20)  5/12 Homework 5 released 
5/15 Dynamic Programming and shortest paths: BellmanFord, FloydWarshall Read: Ch. 25.2, 15.1 (draft) (draft)  5/17 Examples of dynamic programming: Longest common subsequence, Knapsack, Independent Set Read: Ch. 15.4 (draft) (draft)  5/19 Homework 5 due Homework 6 released 
5/22 Greedy Algorithms Read: Ch. 16.1,16.2,16.3 (draft) (draft)  5/24 Minimum Spanning Trees (MST) Read: Ch. 23 (draft) (draft)  5/26 Homework 6 due Homework 7 released 
5/29 Memorial Day (no class)  5/31 Minimum Cut and Karger's algorithm (draft) Read: (draft)  6/2 Homework 7 due 
6/5 Maximum Flow and FordFulkerson (draft). Read: Ch. 26.13 (draft)  6/7 Course recap; What's Next?  6/9 FINAL EXAM 
Midterm and Final
Midterm: Wednesday, May 10, in class (Hewlett 200, 3:00 pm  4:20 pm)  [ problems ] [ solutions ] Final: Friday, June 9, Hewlett 200, 3:30 pm  6:30pm Final Problems and Solutions
Both the midterm and final are closedbook. In the midterm, you are allowed to bring one lettersized doublesided page of notes, that you have prepared yourself . In the final, you are allowed to bring two lettersized doublesided page of notes that you have prepared yourself .
The following practice exams are posted here as a resource; the material covered is similar to what we covered this quarter, but not identical.
Practice Midterm 1 Solutions to the Practice Midterm 1 Practice Midterm 2 Solutions to the Practice Midterm 2
Finals from Previous Years
The following final exams are taken from previous offerings of the class. They are posted here as a resource, but the material covered in them may differ what the material covered this quarter, and their structure may differ from this quarter's final exam.
Final Exam 2016 Final Exam 2016 Solutions
Homework Assignments
 Homework 1 (released 4/7, due 4/14 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 Homework 2 (released 4/14, due 4/21 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 Homework 3 (released 4/21, due 4/28 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 Homework 4 (released 4/28, due 5/8 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 Homework 5 (released 5/12, due 5/19 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 Homework 6 (released 5/19, due 5/26 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 Homework 7 (released 5/26, due 6/2 at 3pm). [ pdf ] [ raw LaTeX file ] [ solutions ]
 There is no Homework 8. However, if you want some practice on Minimum Cut and Maximum Flow, here are some practice problems (with solutions) from Kleinberg and Tardos: Solved exercise 1 here on randomized algorithms in graphs and Solved exercises 1 and 2 here on mincut/maxflow .
 Homework 2 (released 10/7, due 10/14 at 3pm) Assignment Solutions
 Homework 3 (released 10/14, due 10/21 at 3pm) Assignment Solutions
 Homework 4 (released 10/21, due 10/28 at 3pm) Assignment Solutions
 Homework 5 (released 11/4, submission deadline extended  see Piazza) Assignment Solutions
 Homework 6 (released 11/12, due 11/19 at 11:59pm, late submission until 11/21 at 11:59pm) Assignment Solutions
 Homework 7 (released 11/19, due 12/2 at 3pm) Assignment Solutions
Submission Instructions and Policies
 All assignments are posted on Fridays, and are due the next Friday at 3pm.
 All assignments must be submitted electronically as a PDF file using Gradescope (access code: MWRJ89).
 All assignments should be typed using LaTeX, LyX, Microsoft Word, or a similar editor. For first time LaTeX users, see the resources section. Scanned handwritten assignments are not accepted.
 Each student is allowed to discuss the assignment (verbally) with any classmates enrolled in CS161. Each student should write and submit their own solution. Solutions must be written in your own words. When you submit the assignment, you should indicate with whom you have discussed the solutions.
 You are allowed to use textbooks and resources that are listed on this page. You may not google around hoping to find a similar problem worked out, but you may use other resources (like Wikipedia, other lecture notes, textbooks) that you find online. If you are using other resources, you must properly cite them, and you must prove any statement from them that you use.
 You are not allowed to look for the answers for any of the homework assignments (online or otherwise). If you accidentally find a solution for a question, do not read it (if it is not too late), and indicate that clearly on your assignment (including where you found the solution).
 Please follow the honor code .
 Late homeworks will not be accepted. However, we will consider your highest 6 (out of 7) homework grades when computing your final course grade.
 For each assignment, regrade requests will open on Gradescope on Wednesday (after the grades have been published) and close on Sunday.
 Please provide a detailed explanation for your regrade request.
 Note that we may regrade any part of the assignment, and the new grade may be greater than, equal to, or less than the original grade.
Recitations
 Section 1 : Loop and recursion invariants, weak and strong induction.
 Section 2 [ problems ] [ solutions ]: Selection, bigO, and recurrences.
 Section 3 : Randomized algorithms.
 Section 4 [ problems ] [ solutions ]: Universal hash functions, randomly built binary search trees.
 YouTube series on redblack trees: Introduction , Rotations , Insertions 1 , Insertions 2
 Section 5 : Midterm review.
 Section 6 [ problems ] [ solutions ]: Graphs.
 Section 7 : Dynamic programming.
 Section 8 [ problems ] [ solutions ]: Greedy algorithms.
 Recitation 1 (week 1) Solutions
 Recitation 2 (week 2) Solutions
 Recitation 4 (week 4) Solutions [Slides from David's Recitation]
 Recitation 5 (week 5) [Slides from David's Recitation]
 Recitation 6 (week of 3/7) Recitation Solutions
 Recitation 3 (10/1410/19) Solutions
 Recitation 4 (10/2110/26) Solutions
 Recitation 5 (11/411/9) Solutions
 Recitation 6 (11/1111/16) Solutions
 Recitation 7 (11/1811/30) Solutions
 Recitation 8 (12/212/7) Solutions
The main textbook we use is: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 3rd Edition, MIT Press The book is available online through the Stanford library.
We will also occasionally use: Jon Kleinberg, Éva Tardos, Algorithm Design , Pearson/AddisonWesley Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms , McGrawHill Education
Homework Resources
 Expected level of detail: Your homework solutions should make it clear that you understand what's going on. This means that they should have enough detail to convince the grader that your solution is correct; but they needn't have so much detail that it obfuscates the main points. This is a difficult balance to strike. To help you, here is an example of what we are looking for on the homework assignments.
 Read the submission instructions and policies above.
 Read the submission instructions and policies above. Seriously, do it.
 Look over the problems early. Algorithm design takes time, and even simple algorithms can be surprisingly tricky to develop. We suggest reading over all the problems as soon as the problem set goes out so that you will have the time to play around with them over the course of the week.
 Work on your own before working in a group or attending office hours. Although you are allowed to work in groups, we strongly recommend not doing so until you have already thought about each of the problems and tried out various solutions. The problem sets tend to have solutions that are not particularly complicated but which require some insight to discover. If you immediately start working on the problem sets in a group, you will miss out on the opportunity to come up with these insights on your own.
LaTeX Resources
We strongly recommend typesetting solutions to the homework assignments using LaTeX. LaTeX provides a convenient way to produce highquality documents and it is the standard used for typesetting computer science papers.
Guide: An introduction to LaTeX can be found here . Other guides can be found at howtoTeX and!> Wikibooks and NYU .
Online environments: If you do not wish to install LaTeX, ShareLaTeX and Overleaf are online environments that compile previews of your documents as you type and allow you to share documents with collaborators (this feature won't be useful in this course, though). As a Stanford student, you get a free Overleaf Pro account.
LyX: LyX is a version of LaTeX with graphical interface.
Finding mathematical symbols: The introduction mentioned above contains a table of mathematical symbols in LaTeX. Alternatively, consider Detexify .
Examples: homework1.tex homework2.tex homework3.tex homework4.tex homework5.tex homework6.tex homework7.tex > LaTeX Homework Template: Here is an example of of a LaTeX document, including several elements (section numbering, pseudocode, tables, images, etc) that you might find helpful.
The Algorithm Design Manual, 2nd Edition
Steven skiena.
>Second Edition now available!
This newly expanded and updated second edition continues to take the "mystery" out of designing algorithms, and analyzing their efficacy and efficiency. Expanding on the first edition, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students.
The readerfriendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations and an extensive bibliography.
Learn/Teach Algorithms the Skiena Way!
First Edition
From the publisher.
Written by a wellknown algorithms researcher who received the IEEE Computer Science and Engineering Teaching Award, this new edition of The Algorithm Design Manual is an essential learning tool for students needing a solid grounding in algorithms, as well as a special text/reference for professionals who need an authoritative and insightful guide.
"...the book is an algorithmimplementation treasure trove, and putting all of these implementations in one place was no small feat. The list of implementations [and] extensive bibliography make the book an invaluable resource for everyone interested in the subject." ACM Computing Reviews
"It has all the right ingredients: rich contents, friendly, personal language, subtle humor, the right references, and a plethora of pointers to resources."  P. Takis Metaxas, Wellesley College
"This is the most approachable book on algorithms I have."  Megan Squire, Elon University, USA
Spring 2020  COMPSCI 330  Design and Analysis of Algorithms
Course information.
Homework  Post Date  Due Date  Solution 
Example only; no need for submission  
 1/15/2020  1/22/2020, by 11:59 pm  
 1/29/2020  2/5/2020, by 11:59 pm  
 2/5/2020  2/12/2020, by 11:59 pm  
 2/26/2020  3/4/2020, by 11:59 pm  
 3/4/2020  3/25/2020, by 11:59 pm  
 4/1/2020  4/8/2020, by 11:59 pm  
 4/8/2020  4/15/2020, by 11:59 pm  
 4/15/2020  4/22/2020, by 11:59 pm  
Instructor Rong Ge D226 LSRC Email: [email protected] Office Hour: Tuesdays 1:00  2:00 PM, Fridays 11:00 AM  12:00 at LSRC D226 (First office hour Friday 1/17)
After Spring break: I'm going to keep the Tuesdays 1  2 PM office hour on zoom. Instead of the Friday office hour, I will offer two 30min sessions where I will be on piazza trying to answer all questions posted (First two will be Thursday 33:30 pm and Friday 10:3011:00 am, 4/2 and 4/3). For the first two office hour Tuesday 3/24 and 3/31 I need to change the time to 12:30  1:30 PM.
Teaching Assistants
TA office hours
Recitations: Check your individual recitation sessions.
After Spring break: See this post on piazza, you are recommended to stay with your section if your TA is still teaching at the same time and it's possible for you to attend. If you have any difficulty, you can go to a different recitation session that is most convenient for you. We will also record one of the session so you can watch it offline even if you cannot attend.
For most recent recitation materials please check this folder on Sakai.
Notice: The first recitation will be a review of materials already covered in 230 and is optional. Only some of the sessions will be open, you should go to the classroom based on your time. 1:25 pm and 4:40 pm in LSRC D106, 3:05 pm in Soc. Psych. 126
 [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw Hill, 2006.
 [KT] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
 [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
Prerequisites:
There are two hard prerequisites (equivalent courses are also acceptable):
 COMPSCI 201 Data Structures and Algorithms
 COMPSCI 230 Discrete Math for Computer Science
Evaluation:
 Homework (35%): Expect roughly 1 problem set per week. Please read the guideline on collaboration.
 Midterm Exams (30%): There will be two inclass midterm exams on 2/17 and 4/1.
 Final Exam (30%): Final exam is scheduled on 4/30, 2 pm  5pm.
 Recitation Attendance (5%).
Updated Evaluation:
Note: According to school policy, the course is defaulted to S/U grading. All of you should expect to get an S as long as you continue to work on the homework/exams to your capacity, and I'd be happy to discuss with anyone who has more difficulties. If you do want a letter grade, you need to submit a form by April 22 (the form is required by Trinity so check your email for the exact date).
 Homework (55%): Expect roughly 1 problem set per week. Please read the guideline on collaboration. Two homeworks with lowest score will be dropped. You will also have one latepass so you can submit your homework two days late without any reason (just submit the form on piazza).
 Exams (40%): Final exam is scheduled on 4/30. Final exam will be online (on gradescope) and open book/open notes. You can pick any 3 hours during a 24hour period to finish the exam (with possibly more time if you need accomodations). Second midterm is cancelled.
 Final exam counts as two scores, together with your midterm score, the lowest one of the three will be dropped. That is, if your final score is higher, that will be your exam score; if your final score is lower, the average of that and the midterm is going to be your exam score.
 Recitation Attendance (Prior to spring break) (5%). Note that we will no longer check attendance for recitations after spring break. Attending recitations (or at least watching the recorded material) is still strongly recommended.
There will be 8 homeworks. In normal cases homeworks are due one week after they are posted. The worst two grade out of 8 homeworks will be dropped. Homework will be submitted through GradeScope . Homework should be typed and submit as a PDF file. LateX is highly preferred. If you are not familiar with LaTeX and want to learn, I learned how to use it by reading this (but there are also other resources you can find online). Please make sure to read the guideline on collaboration. Every incidence of cheating will be reported . Questions about homework problems should be posted to Piazza (instead of emailing the TAs or the instructor).
 Introduction: History of Algorithms, Asymptotic and Worstcase Analysis
 Algorithm Design Techniques: Divide and Conquer (Recurrences), Dynamic Programming and Memoization, Greedy Algorithms
 Graph Algorithms: Graph Representations, Graph Traversal and Applications, Shortest Path, Minimum Spanning Tree, Maximum Matching
 Data Structures: Amortization and Potential Functions, UnionFind
 Algorithms for Machine Learning: Principled Component Analysis, Least Squares, Gradient descent
 Randomized Algorithms: Monte Carlo and Las Vegas Algorithms, Hashing
 Linear Programming: Simplex Algorithms, LP Duality
 Intractability: P and NP, NPcompleteness, Polynomialtime Reductions, Approximation Algorithms
Tentative Schedule
Date  Contents  Notes  Homework  References 
1/8  Intro: Algorithms, Asymptotic Notations   
Basic Algorithm Design Techniques  
1/13  Divide and Conquer   DPV 2, KT 5, CLRS 4  
1/15   Homework 1  
1/20  Martin Luther King, Jr. Day holiday. No classes are held.  
1/22  Dynamic Programming   DPV 6, KT 6, CLRS: 15  
1/27   
1/29   Homework 2  
2/3  Greedy Algorithm   DPV 5, KT 4, CLRS: 16  
2/5   Homework 3  
2/10   
2/12  Review   
2/17  MidTerm Exam 1 (in class) All previous materials.   
Graph Algorithms  
2/19  Graph representations and traversal   DPV 3, KT 3, CLRS 22  
2/24   
2/26  Shortest Path Algorithms   Homework 4  DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 
3/2  Minimum Spanning Tree   DPV: 5 KT: 4 CLRS: 16, 23  
3/4   Homework 5  
3/9,11,16,18  Spring Break  
Linear Programming  
3/23  Linear Programming, Relaxations   CLRS 29  
3/25  Duality   
3/30  Bipartite Matching, Max Flow   
4/1  Linear Programming Algorithms   Homework 6  
Topics: Randomized Algorithms and Amortized Analysis  
4/6  Basic Probabilities, Quicksort revisited, fast selection   DPV: virtural chapter KT: 13 CLRS: 5, 11  
4/8  Hashing   Homework 7  
Intractability  
4/13  P vs NP, reductions   DPV: 8 KT: 8 CLRS: 34  
4/15  More reductions   Homework 8  
4/20  Even more reductions   
4/22  Amortized Analysis   KT 4.6 CLRS 17, 20  
4/30  Final Exam Everything covered in class  
Steven Skiena
 Dept. of Computer Science
 Stony Brook University
 Algorithm Repository
The Algorithm Design Manual, 3rd Edition
This newly expanded and updated third edition of the bestselling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficacy and efficiency. Expanding on the first and second editions, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students.
Useful Links
"My absolute favorite for this kind of interview preparation is Steven Skiena’s The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace … graph problems are  they should be part of every working programmer’s toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. … every 1 – pager has a simple picture, making it easy to remember."  Steve Yegge  Get that Job at Google" : "Steven Skiena’s Algorithm Design Manual retains its title as the best and most comprehensive practical algorithm guide to help identify and solve problems. … Every programmer should read this book, and anyone working in the field should keep it close to hand. … This is the best investment … a programmer or aspiring programmer can make."  Harold Thimbleby, Times Higher Education "It is wonderful to open to a random spot and discover an interesting algorithm. This is the only textbook I felt compelled to bring with me out of my student days.... The color really adds a lot of energy to the new edition of the book!"  Cory Bart, University of Delaware
Our Other Fine Products
From the Publisher
This newly expanded and updated third edition of the bestselling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficiency. It serves as the primary textbook of choice for algorithm design courses and interview selfstudy, while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students. The readerfriendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Practical Algorithm Design, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, the Hitchhiker's Guide to Algorithms, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations, and an extensive bibliography.
More Information
Supplementary material can be found at my CSE 373 (Analysis of Algorithms) course page. Lecture videos for my classes on Data Science , Analysis of Algorithms , Computational Biology , and more are on Youtube . Take a look at them if you have the chance.
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.
by Jeff Erickson
More information, get the book, more algorithms lecture notes, models of computation.
If were not a little mad and generally silly I should give you my advice upon the subject, willynilly; I should show you in a moment how to grapple with the question, And you'd really be astonished at the force of my suggestion. On the subject I shall write you a most valuable letter, Full of excellent suggestions when I feel a little better, But at present I'm afraid I am as mad as any hatter, So I'll keep 'em to myself, for my opinion doesn't matter! —W. S. Gilbert and Arthur Sullivan, "My Eyes are Fully Open" , Ruddigore; or, The Witch's Curse (1887)
It is time we did away with “publish or perish” and replace it with “publish and perish.” Nothing will be more blasphemous than writing a textbook that anyone can go out and buy. — Daniel J. Woodhouse , “An Open Letter to the Mathematical Community” , McSweeny’s (January 15, 2019)
Navigation Menu
Search code, repositories, users, issues, pull requests..., provide feedback.
We read every piece of feedback, and take your input very seriously.
Saved searches
Use saved searches to filter your results more quickly.
To see all available qualifiers, see our documentation .
 Notifications You must be signed in to change notification settings
Homework for the "Algorithm design" course at "La Sapienza" University of Rome
Ivagnesmanuel/Algorithmdesignhomework
Folders and files.
Name  Name  

1 Commit  
Repository files navigation
Algorithmdesignhomework.
This folder contains the homework for the "Algorithm design" course at "La Sapienza" university of Rome
 Python 100.0%
Advanced Algorithm Design
Princeton university.
Instructors: Mark Braverman, Matt Weinberg
TAs: Linda Cai, Zhou Lu
For contact information, course description, collaboration/grading policy, etc., please see the course infosheet .
Ed: We will use Ed for course discussion. The link is: https://edstem.org/us/courses/8773/discussion/ . If you are enrolled in the course, you should have access to Ed. Please email the instructors if you cannot access Ed.
codePost: Course assignments will be submitted to codePost. You can enroll in the course using this link (must use an @princeton or @cs.princeton email address).
Announcements will be posted below:
 Guidelines for the final exam/project are posted: final guidelines .
Homework: Homeworks will be posted below when they become available. Here is a LaTeX template you may use for the homework, and here is a short guide to LaTeX. Feel free to visit office hours for help installing/setting up LaTeX. Submit your homework through codePost here .
Lecture Notes: We will use lecture notes from previous iterations, and mostly follow the same schedule. Below is a tentative schedule:



9/2  Randomized MinCut 

9/7  LP Rounding I 

9/9  LP Rounding II 

9/14  LP Duality 

9/16  SemiDefinite Programs 

9/21  Hashing 

9/23  Concentration Inequalities 

9/28  Martingales  See Ed 
9/30  Random Walks and Markov Chains 

10/5  Multiplicative Weights 

10/7  JohnsonLindenstrauss 

10/12  LocalitySensitive Hashing and Approximate Nearest Neighbors 

10/14  LowRank Approximations and SVD 

10/19  Fall Break 

10/21  Fall Break 

10/26  Coding Theory 

10/28  Online Algorithms I 

11/2  Online Algorithms II 

11/4  Computation of Nash 

11/9  Ellipsoid Algorithm 

11/11  Submodular Minimization 

11/16  Communication Complexity 

11/18  Hashing to Reals 

11/23  Differential Privacy 

11/25  Thanksgiving Break 

11/30  Combinatorial Auctions I 

12/2  Combinatorial Auctions II 

If you're seeing this message, it means we're having trouble loading external resources on our website.
If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.
To log in and use all the features of Khan Academy, please enable JavaScript in your browser.
Unit 1: Algorithms
About this unit.
We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges.
Intro to algorithms
 What is an algorithm and why should you care? (Opens a modal)
 A guessing game (Opens a modal)
 Routefinding (Opens a modal)
 Discuss: Algorithms in your life (Opens a modal)
Binary search
 Binary search (Opens a modal)
 Implementing binary search of an array (Opens a modal)
 Challenge: Binary search (Opens a modal)
 Running time of binary search (Opens a modal)
 Running time of binary search 5 questions Practice
Asymptotic notation
 Asymptotic notation (Opens a modal)
 Bigθ (BigTheta) notation (Opens a modal)
 Functions in asymptotic notation (Opens a modal)
 BigO notation (Opens a modal)
 BigΩ (BigOmega) notation (Opens a modal)
 Comparing function growth 4 questions Practice
 Asymptotic notation 5 questions Practice
Selection sort
 Sorting (Opens a modal)
 Challenge: implement swap (Opens a modal)
 Selection sort pseudocode (Opens a modal)
 Challenge: Find minimum in subarray (Opens a modal)
 Challenge: implement selection sort (Opens a modal)
 Analysis of selection sort (Opens a modal)
 Project: Selection sort visualizer (Opens a modal)
Insertion sort
 Insertion sort (Opens a modal)
 Challenge: implement insert (Opens a modal)
 Insertion sort pseudocode (Opens a modal)
 Challenge: Implement insertion sort (Opens a modal)
 Analysis of insertion sort (Opens a modal)
Recursive algorithms
 Recursion (Opens a modal)
 The factorial function (Opens a modal)
 Challenge: Iterative factorial (Opens a modal)
 Recursive factorial (Opens a modal)
 Challenge: Recursive factorial (Opens a modal)
 Properties of recursive algorithms (Opens a modal)
 Using recursion to determine whether a word is a palindrome (Opens a modal)
 Challenge: is a string a palindrome? (Opens a modal)
 Computing powers of a number (Opens a modal)
 Challenge: Recursive powers (Opens a modal)
 Multiple recursion with the Sierpinski gasket (Opens a modal)
 Improving efficiency of recursive functions (Opens a modal)
 Project: Recursive art (Opens a modal)
Towers of Hanoi
 Towers of Hanoi (Opens a modal)
 Towers of Hanoi, continued (Opens a modal)
 Challenge: Solve Hanoi recursively (Opens a modal)
 Move three disks in Towers of Hanoi 3 questions Practice
 Divide and conquer algorithms (Opens a modal)
 Overview of merge sort (Opens a modal)
 Challenge: Implement merge sort (Opens a modal)
 Lineartime merging (Opens a modal)
 Challenge: Implement merge (Opens a modal)
 Analysis of merge sort (Opens a modal)
 Overview of quicksort (Opens a modal)
 Challenge: Implement quicksort (Opens a modal)
 Lineartime partitioning (Opens a modal)
 Challenge: Implement partition (Opens a modal)
 Analysis of quicksort (Opens a modal)
Graph representation
 Describing graphs (Opens a modal)
 Representing graphs (Opens a modal)
 Challenge: Store a graph (Opens a modal)
 Describing graphs 6 questions Practice
 Representing graphs 5 questions Practice
Breadthfirst search
 Breadthfirst search and its uses (Opens a modal)
 The breadthfirst search algorithm (Opens a modal)
 Challenge: Implement breadthfirst search (Opens a modal)
 Analysis of breadthfirst search (Opens a modal)
Further learning
 Where to go from here (Opens a modal)
 Search News and Events
 News overview
 Media relations
Towards survivable network design using approximation algorithms
Algorithms applied by Dylan HyattDenesik strengthen the connectivity of networks and ensure continued operation in the event of node failure
Today's society relies heavily on networks for a great variety of applications. Telecommunications and transportation, for example, cannot be imagined without the use of networks. While networks must first and foremost perform their task of enabling communication or transporting goods or people, on the other hand, they must be resilient enough to meet the challenges that real life presents to them. PhD researcher Dylan HyattDenesik aims to tackle these demands by providing algorithms that take a given network and increase its level of connectivity. He defended his thesis on Wednesday, July 10 th .
Augmenting edge connectivity
HyattDenesik's work focuses primarily on the survivable network design problem of edge connectivity augmentation. In this, additional connections should be added to an existing network by an algorithm. The advantage of the added connections is that when a single node fails, the overall connectivity of the network remains intact. In addition to augmenting the network to be resilient to failures, the goal of the algorithm is to select the fewest number of links possible in order to reach the desired connectivity properties.
Optimizing runtime efficiency
One major stumbling block that occurs when tackling these problems in all but the simplest instances is that of runtime efficiency. This refers to the efficiency of an algorithm concerning the time it takes to execute based on the size of the input. The lower the runtime complexity, the more efficient the algorithm. To optimize runtime complexity, HyattDenesik introduced Approximation Algorithms, which trade finding an optimal solution inefficiently with efficiently finding a solution that is suboptimal but guaranteed to be within some specific fraction of the optimal value.
Flexible edge connectivity
In addition to the connectivity augmentation, HyattDenesik also considered a problem that has been recently introduced in the field of network design: the Edge (or Vertex) Flexible Connectivity problem. This involves identifying a network whose edges (or nodes) are considered safe or unsafe. The researcher then tries to select the smallest number of edges so that the failure of an unsafe edge (or node) does not break the network. To do so, HyattDenesik provided the first betterthan2 approximation for Flexible Vertex Connectivity, and also improved the currently bestknown approximation factor for Flexible Edge Connectivity. HyattDenesik’s work provides a valued contribution to the reliability and safety of networks, which is essential for us all. In the future, other researchers can further build on his work. Title of PhD thesis: Approximation Algorithms for Connectivity Augmentation and Flexible Graph Connectivity Supervisors: L. Sanità , prof.dr. F.C.R. Spieksma
Media contact
Latest news.
 News Overview
keep following us
Experience life at our university on Instagram. With every week a different person taking over.
On our YouTube channel you find the latest videos and animations about research, education and working at TU/e.
Follow the latest TU/e updates on our Facebook page.
Be part of our community and stay up to date on everything that happens at TU/e by following us on LinkedIn.
Be the first to know the latest TU/e news via our Twitter channel.
 Introduction
 Conclusions
 Article Information
This conceptual framework builds on a National Academy of Medicine 13 algorithm life cycle framework adapted by Roski et al. 14
 Experts Tackle Racial Bias in Clinical Algorithms JAMA Medical News & Perspectives February 13, 2024 This Medical News article discusses efforts to evaluate the inclusion of race as a factor in widely used clinical decisionmaking algorithms. Bridget M. Kuehn
 Proactive Algorithm Monitoring to Ensure Health Equity JAMA Network Open Invited Commentary December 15, 2023 Mark Sendak, MD, MPP; Suresh Balu, MBA, MS; Adrian F. Hernandez, MD, MHS
See More About
Sign up for emails based on your interests, select your interests.
Customize your JAMA Network experience by selecting one or more topics from the list below.
 Academic Medicine
 Acid Base, Electrolytes, Fluids
 Allergy and Clinical Immunology
 American Indian or Alaska Natives
 Anesthesiology
 Anticoagulation
 Art and Images in Psychiatry
 Artificial Intelligence
 Assisted Reproduction
 Bleeding and Transfusion
 Caring for the Critically Ill Patient
 Challenges in Clinical Electrocardiography
 Climate and Health
 Climate Change
 Clinical Challenge
 Clinical Decision Support
 Clinical Implications of Basic Neuroscience
 Clinical Pharmacy and Pharmacology
 Complementary and Alternative Medicine
 Consensus Statements
 Coronavirus (COVID19)
 Critical Care Medicine
 Cultural Competency
 Dental Medicine
 Dermatology
 Diabetes and Endocrinology
 Diagnostic Test Interpretation
 Drug Development
 Electronic Health Records
 Emergency Medicine
 End of Life, Hospice, Palliative Care
 Environmental Health
 Equity, Diversity, and Inclusion
 Facial Plastic Surgery
 Gastroenterology and Hepatology
 Genetics and Genomics
 Genomics and Precision Health
 Global Health
 Guide to Statistics and Methods
 Hair Disorders
 Health Care Delivery Models
 Health Care Economics, Insurance, Payment
 Health Care Quality
 Health Care Reform
 Health Care Safety
 Health Care Workforce
 Health Disparities
 Health Inequities
 Health Policy
 Health Systems Science
 History of Medicine
 Hypertension
 Images in Neurology
 Implementation Science
 Infectious Diseases
 Innovations in Health Care Delivery
 JAMA Infographic
 Law and Medicine
 Leading Change
 Less is More
 LGBTQIA Medicine
 Lifestyle Behaviors
 Medical Coding
 Medical Devices and Equipment
 Medical Education
 Medical Education and Training
 Medical Journals and Publishing
 Mobile Health and Telemedicine
 Narrative Medicine
 Neuroscience and Psychiatry
 Notable Notes
 Nutrition, Obesity, Exercise
 Obstetrics and Gynecology
 Occupational Health
 Ophthalmology
 Orthopedics
 Otolaryngology
 Pain Medicine
 Palliative Care
 Pathology and Laboratory Medicine
 Patient Care
 Patient Information
 Performance Improvement
 Performance Measures
 Perioperative Care and Consultation
 Pharmacoeconomics
 Pharmacoepidemiology
 Pharmacogenetics
 Pharmacy and Clinical Pharmacology
 Physical Medicine and Rehabilitation
 Physical Therapy
 Physician Leadership
 Population Health
 Primary Care
 Professional Wellbeing
 Professionalism
 Psychiatry and Behavioral Health
 Public Health
 Pulmonary Medicine
 Regulatory Agencies
 Reproductive Health
 Research, Methods, Statistics
 Resuscitation
 Rheumatology
 Risk Management
 Scientific Discovery and the Future of Medicine
 Shared Decision Making and Communication
 Sleep Medicine
 Sports Medicine
 Stem Cell Transplantation
 Substance Use and Addiction Medicine
 Surgical Innovation
 Surgical Pearls
 Teachable Moment
 Technology and Finance
 The Art of JAMA
 The Arts and Medicine
 The Rational Clinical Examination
 Tobacco and eCigarettes
 Translational Medicine
 Trauma and Injury
 Treatment Adherence
 Ultrasonography
 Users' Guide to the Medical Literature
 Vaccination
 Venous Thromboembolism
 Veterans Health
 Women's Health
 Workflow and Process
 Wound Care, Infection, Healing
Get the latest research based on your areas of interest.
Others also liked.
 Download PDF
 X Facebook More LinkedIn
 CME & MOC
Chin MH , AfsarManesh N , Bierman AS, et al. Guiding Principles to Address the Impact of Algorithm Bias on Racial and Ethnic Disparities in Health and Health Care. JAMA Netw Open. 2023;6(12):e2345050. doi:10.1001/jamanetworkopen.2023.45050
Manage citations:
© 2024
 Permissions
Guiding Principles to Address the Impact of Algorithm Bias on Racial and Ethnic Disparities in Health and Health Care
 1 University of Chicago, Chicago, Illinois
 2 Oracle Health, Austin, Texas
 3 Agency for Healthcare Research and Quality, Rockville, Maryland
 4 US Department of Health and Human Services Office of Minority Health, Rockville, Maryland
 5 NORC at the University of Chicago, Bethesda, Maryland
 6 National Institute on Minority Health and Health Disparities, Bethesda, Maryland
 7 Association of American Medical Colleges, Washington, DC
 8 Stanford University, Stanford, California
 9 Equality AI, Park City, Utah
 10 American Medical Association, Chicago, Illinois
 11 Office of the National Coordinator for Health Information Technology, Washington, DC
 12 Prudential Financial, Arlington, Virginia
 13 NORC at the University of Chicago, Chicago, Illinois
 14 Elevance Health, Indianapolis, Indiana
 15 Yale School of Medicine, New Haven, Connecticut
 Invited Commentary Proactive Algorithm Monitoring to Ensure Health Equity Mark Sendak, MD, MPP; Suresh Balu, MBA, MS; Adrian F. Hernandez, MD, MHS JAMA Network Open
 Medical News & Perspectives Experts Tackle Racial Bias in Clinical Algorithms Bridget M. Kuehn JAMA
Importance Health care algorithms are used for diagnosis, treatment, prognosis, risk stratification, and allocation of resources. Bias in the development and use of algorithms can lead to worse outcomes for racial and ethnic minoritized groups and other historically marginalized populations such as individuals with lower income.
Objective To provide a conceptual framework and guiding principles for mitigating and preventing bias in health care algorithms to promote health and health care equity.
Evidence Review The Agency for Healthcare Research and Quality and the National Institute for Minority Health and Health Disparities convened a diverse panel of experts to review evidence, hear from stakeholders, and receive community feedback.
Findings The panel developed a conceptual framework to apply guiding principles across an algorithm’s life cycle, centering health and health care equity for patients and communities as the goal, within the wider context of structural racism and discrimination. Multiple stakeholders can mitigate and prevent bias at each phase of the algorithm life cycle, including problem formulation (phase 1); data selection, assessment, and management (phase 2); algorithm development, training, and validation (phase 3); deployment and integration of algorithms in intended settings (phase 4); and algorithm monitoring, maintenance, updating, or deimplementation (phase 5). Five principles should guide these efforts: (1) promote health and health care equity during all phases of the health care algorithm life cycle; (2) ensure health care algorithms and their use are transparent and explainable; (3) authentically engage patients and communities during all phases of the health care algorithm life cycle and earn trustworthiness; (4) explicitly identify health care algorithmic fairness issues and tradeoffs; and (5) establish accountability for equity and fairness in outcomes from health care algorithms.
Conclusions and Relevance Multiple stakeholders must partner to create systems, processes, regulations, incentives, standards, and policies to mitigate and prevent algorithmic bias. Reforms should implement guiding principles that support promotion of health and health care equity in all phases of the algorithm life cycle as well as transparency and explainability, authentic community engagement and ethical partnerships, explicit identification of fairness issues and tradeoffs, and accountability for equity and fairness.
Health care algorithms, defined as mathematical models used to inform decisionmaking, are ubiquitous and may be used to improve health outcomes. However, algorithmic bias has harmed minoritized communities in housing, banking, and education, and health care is no different. 1 Thus, addressing algorithmic bias is an urgent issue, as exemplified by a Biden Administration Executive Order stating that “agencies shall consider opportunities to prevent and remedy discrimination, including by protecting the public from algorithmic discrimination.” 2
An unbiased algorithm is one that ensures patients who receive the same algorithm score or classification have the same basic needs. 3 Health care algorithms are used for diagnosis, treatment, prognosis, risk stratification, triage, and resource allocation. A biased algorithm that used race to estimate kidney function resulted in higher estimates for Black patients compared with White patients, leading to delays in organ transplant referral for Black patients. 4 A commercial algorithm that riskstratified patients to determine eligibility for chronic disease management programs effectively required Black individuals to be sicker than White individuals to qualify for such services. 5 Potentially biased algorithms have been developed for heart failure, cardiac surgery, kidney transplantation, vaginal birth after cesarean delivery, rectal cancer, and breast cancer, often affecting access to or eligibility for interventions or services, and resource allocation. 4
The Agency for Healthcare Research and Quality (AHRQ) and the National Institute on Minority Health and Health Disparities (NIMHD) convened a panel to recommend core guiding principles for the development and use of clinical algorithms in health care, including datadriven, probabilitybased algorithms such as those using artificial intelligence and machine learning approaches. The panel’s core guiding principles also apply to rulesbased approaches derived from data (eg, if acute myocardial infarction, give aspirin), since these rules may reflect the specific data sets and patient populations from which they were generated and the potential biases within.
The Council on Artificial Intelligence of the Organization for Economic Cooperation and Development defines an artificial intelligence system as “a machinebased system that can, for a given set of humandefined objectives, make predictions, recommendations, or decisions influencing real or virtual environments. Artificial intelligence systems are designed to operate with varying levels of autonomy.” 6 Machine learning is a subset of artificial intelligence that analyzes data using mathematical modeling to learn patterns that can make predictions or guide tasks. 7 Traditional statistical regression techniques, often used in earlier risk prediction models, estimate relationships between predictors and outcomes. In contrast, machine learning models can “learn” by using mathematical techniques that infer relationships within large data sets to inform predictions. 8
This article describes guiding principles for health care algorithms and key operational considerations. This work is not exhaustive because synergistic efforts, such as those of the Office of the National Coordinator for Health Information Technology (ONC), are ongoing. 9 , 10 Algorithmic bias is neither inevitable nor merely a mechanical or technical issue. Conscious decisions by algorithm developers, algorithm users, health care industry leaders, and regulators can mitigate and prevent bias and proactively advance health equity.
The AHRQ received a congressional letter in fall 2020 inquiring about the contribution of clinical algorithms to racial and ethnic bias in health care. In response, the AHRQ published a request for information to elicit perspectives from public stakeholders on this topic and commissioned an evidence review to examine the impact of health care algorithms on health disparities and to identify potential solutions to mitigate biases. 11 The subsequent evidence review underscored the limits of current knowledge and research about health care algorithms in the literature.
The AHRQ, the NIMHD, the US Department of Health and Human Services (HHS) Office of Minority Health, and the ONC collaboratively recruited 9 stakeholders with diverse backgrounds and expertise to serve on a panel to develop guiding principles to address racial and ethnic bias in health and health care resulting from algorithms. The panel heard from a group of national and international thought leaders involved in algorithm design, development, implementation, and oversight during a 2day hybrid public meeting and received feedback on draft principles from patient and community representatives and the public during a subsequent virtual meeting. 12 These perspectives were particularly important for the panel’s recommendations, given the limitations of the published literature. The panel’s work, including this article, was developed iteratively.
The conceptual framework to mitigate and prevent bias in health care algorithms ( Figure ) built on a National Academy of Medicine 13 algorithm life cycle framework adapted by Roski et al. 14 Within the context of structural racism and discrimination, 15 the goal is to promote health and health care equity for patients and communities. An algorithm’s life cycle comprises 5 phases that typically occur sequentially. 16 Problem formulation (phase 1) defines the problem that the algorithm is designed to address, relevant actors, and priority outcomes. Problem formulation is followed by selection and management of the data used by the algorithm (phase 2) and subsequent development, training, and validation of the algorithm (phase 3). The algorithm is deployed and integrated in its intended setting (phase 4). Mechanisms should monitor performance and outcomes and maintain, update, or deimplement the algorithm accordingly (phase 5).
Guiding principles apply at each phase to mitigate and prevent bias in an algorithm. Operationalization of principles takes place at 3 levels: individual (developers and users), institutional (organizational policies and procedures), and societal (legislation, regulation, and private policy).
Tables 1 and 2 list the guiding principles and their operational considerations. Each principle is described hereinafter.
Advancing health equity should be a fundamental objective of any algorithm used in health care. 7 The World Health Organization defines equity as the “absence of unfair, avoidable, or remediable differences among groups of people, whether those groups are defined socially, economically, demographically, or geographically or by other dimensions of inequality (e.g., sex, gender, ethnicity, disability, or sexual orientation).” 17 Algorithms should be designed with goals of advancing health equity, promoting fairness, and reducing health disparities.
Formulating the problem appropriately is critical (phase 1), and improving health and health care equity for patients and communities should be central. 3 During the data selection, assessment, and management phase of the algorithm life cycle (phase 2), data used for algorithm development should be assessed for biases, accuracy, fitness for the intended purpose, and representativeness of the intended population. Engagement of key diverse stakeholders—which includes communities—during problem formulation (phase 1) and data selection (phase 2) is critical to avoid knowledge gaps. Any issues identified should be documented, and corrective actions should be taken before moving to algorithm development, training, and validation (phase 3).
It is critical to use rigorous methods, wise human judgment, and checks and balances in algorithm development to mitigate and prevent bias and ensure that conclusions are accurate, robust, and reproducible. 24 Compared to traditional statistical techniques in which statisticians have more manual control over the analyses, artificial intelligence models can be more opaque and more difficult to interpret. They risk being overfitted to the data at hand, threatening generalizability. Artificial intelligence models sometimes lack common sense and are more difficult to audit. Thus, rigorous methods and processes are essential for algorithm development. 25  29
Algorithms should be validated across populations to ensure fairness in performance. After an algorithm is deployed, continuous monitoring for performance and data drift is necessary. Monitoring should assess the fairness and equity of the algorithm output as well as the impact of the algorithm on patients, populations, and society, including data privacy and resource allocation. Measurement and comparison of outcomes between advantaged and historically marginalized populations such as racial and ethnic minoritized groups or individuals with lower income should be assessed routinely by health care systems, algorithm vendors, and the research community and supported by research sponsors (eg, funders, scientific journals). Algorithm end users should supplement model outputs with human judgment. Furthermore, access to information technology for all should be ensured.
Algorithm developers, health care institutions, algorithm users, and regulators are responsible for ensuring that algorithms are transparent, easy to explain, and readily interpretable at all steps in the algorithm life cycle for diverse audiences. 30 , 31 The HHS states that “all relevant individuals should understand how their data is being used and how AI systems make decisions; algorithms, attributes and correlations should be open to inspection.” 20 Development of transparent and explainable algorithms requires algorithm developers and stewards to present evidence for impact on processes and outcomes and to provide understandable and accurate explanations to clinicians and patients to enable informed decisionmaking. 32 In addition, an algorithm should only operate under the conditions for which it was designed, and outputs should only be used when there is confidence in the results. 31
Transparency includes multiple domains, such as availability of technical information, algorithm oversight, and communication of impact to stakeholders. 20 , 31 , 32 Algorithm developers should create profiles of the data used to train the algorithm, describing distribution of key aspects of the population in the data set (eg, race and ethnicity, gender, socioeconomic status, and age); they should also make data exploration analysis readily available for independent review. Algorithm developers should disclose types, sizes, and overall distributions in data sets used in their formulation, testing, and validation. Regulation should require algorithm information labels or model cards sufficient to assess design, validity, and the presence of bias. 10 , 21 Implementers should disclose the purpose of algorithms and their impact. If biases have been identified in an algorithm, the developers, implementers, and users should disclose such biases. Any bias mitigation attempts should also be disclosed to all with a stake in the algorithm, including patients, caregivers, and communities. A structured reporting process could identify signals of emerging problems both locally and nationally and facilitate addressing such problems systematically.
Several reporting guidelines promote transparency of research examining algorithms. 33 However, these guidelines do not include concrete ways to report on fairness, and they rarely make explicit mention of equity. 34 Reporting guidelines for algorithms should therefore be updated with specific equity approaches as has been done for observational studies and randomized clinical trials. 35 , 36
Authentically engaging and partnering with patients and communities is essential to understand both a problem affecting them and its solutions. 22 Moreover, it is an ethical imperative to engage with patients and communities around health care algorithms and earn their trust, as these tools can provide great benefit or harm. Patients and communities, including populations who have been historically marginalized, should be engaged authentically and ethically when identifying and assessing a problem that requires use of an algorithm as part of its solution and during algorithm data selection, development, deployment, and monitoring.
Early and intentional engagement can help identify priorities of patients and communities and any concerns they have regarding algorithm use. 37 All patients and communities should be informed when an algorithm is used in their care, should be advised about impact of the algorithm on their treatment, and should be provided alternatives if appropriate. 38 They should know how the algorithm performs for their demographic group compared with other groups and be made aware of any opportunities to opt out of algorithms or to pursue alternatives to algorithmdriven decisions.
Algorithms should be bound by concepts of data sovereignty, the idea that data are subject to legal regulations of countries, nations, or states. Sovereignty is of particular importance to Indigenous nations. 39 Health care organizations, vendors, and other model developers earn trustworthiness through authenticity, ethical and transparent practices, security and privacy of data, and timely disclosures of algorithm use.
The panel recommends that advancing health and health care equity for patients and communities should be the goal of health care algorithms. Advancing health equity requires expertise in algorithmic fairness—the field of identifying, understanding, and mitigating bias. 40  42 Health care algorithmic fairness issues arise from both ethical choices and technical decisions at different phases of the algorithm life cycle. 16 , 43 For example, fundamental ethical choices can arise during problem formulation (phase 1; eg, Is the goal of the algorithm to improve and advance equitable outcomes or is the primary goal to maximize profit?). Additionally, if a particular algorithm use involves choosing a cutoff point for action during model development and implementation, should that cutoff be chosen to maximize sensitivity of the tool to identify someone who might benefit from an intervention, or should it be chosen to maximize specificity of the tool so inappropriate patients are not exposed to unnecessary risk from the intervention? Tradeoffs among competing fairness metrics and values are common. Different technical definitions of algorithmic fairness, such as sufficiency, separation, and independence, are mathematically mutually incompatible, trading off maximizing accuracy of an algorithm and minimizing differences among groups across definitions. 44 It is critical to make health care algorithm fairness issues and tradeoffs explicit, transparent, and explainable. Thus, solutions to advance health equity with health care algorithms require ethical, technical, and social approaches—there is no simple cookiecutter technical solution. 43 , 45
Technical methods for improving fairness in algorithms can be divided into stages of modeling: preprocessing (eg, repair biased data set), inprocessing (eg, use fairness metrics in the model optimization process to maximize accuracy and fairness), and postprocessing (eg, transform model output to improve prediction fairness). 46 , 47 Key issues for fairness metrics include prioritization of fairness for group or individual, binary classification (eg, qualifies for service or not) vs continuous classification (eg, regression output), and use of regularization methods (fairness metrics to balance accuracy and fairness), reweighting methods (weight samples from underrepresented groups more highly), or both. 48 Of note, technical definitions and metrics of fairness often do not translate clearly or intuitively to ethical, legal, social, and economic conceptions of fairness. 46 , 47 Thus, close collaboration and discussion are essential among stakeholders, including algorithm developers, algorithm users, and the communities to whom the algorithm will be applied.
We recommend considering fairness of algorithms through the lens of distributive justice, the socially just distribution of outcomes and allocation of resources across different populations. 49 Distributive justice metrics include clinical outcomes, resource allocation, and performance measures of algorithms (eg, sensitivity, specificity, and positive predictive value). 8 , 43 , 50 When unfairness is identified, bias should be mitigated using both social (eg, diverse teams and stakeholder codevelopment) and technical (eg, algorithmic fairness toolkits, fairness metrics, data set collection, and deimplementation) mitigation methods. 51 Algorithms and accompanying policies and regulations should also be viewed through frames of equity of harms and risks and explicit identification of tradeoffs among different competing values and options. 41  43 Algorithms with a higher risk of substantial harm and injustice should have stricter internal oversight by organizations and more stringent external regulation. 20
Model developers and users, including vendors, health care organizations, researchers, and professional societies, should accept responsibility to achieve equity and fairness in outcomes from health care algorithms and be accountable for the performance of algorithms in different populations. Institutions such as vendors and health care provider organizations should establish processes at each phase of the algorithm life cycle to promote equity and fairness. Transparency in the types of training data, processes, and evaluations used is paramount. For example, an academic medical center recently published its framework for oversight and deployment of prediction models, which includes checkpoint gates and an oversight governance structure. 52 Current evidence suggests that such governance infrastructure is rare. 53
Organizations should have an inventory of their algorithms and have local, periodic evaluations and processes that screen for and mitigate bias. It is crucial for organizations to engage stakeholders throughout the entire algorithm life cycle to ensure fairness and promote trust. This means incorporating model developers, end users, health care administrators, clinicians, patient advocates, and community representatives. Different organizations and experts have recommended various accountability metrics and oversight structures. 3
Regulations and incentives should support equity and fairness while also promoting innovation. 54 There should be redress for persons and communities who have been harmed by biased algorithms. An ethical, legal, social, and administrative framework and culture should be created that redresses harm while encouraging quality improvement, collaboration, and transparency, similar to what is recommended for patient safety. 55
ChatGPT and other artificial intelligence language models have spurred widespread public interest in the potential value and dangers of algorithms. Multiple stakeholders must partner to create systems, processes, regulations, incentives, standards, and policies to mitigate and prevent algorithm bias in health care. 47 Dedicated resources and the support of leaders and the public are critical for successful reform. It is our obligation to avoid repeating errors that tainted use of algorithms in other fields.
Accepted for Publication: October 5, 2023.
Published: December 15, 2023. doi:10.1001/jamanetworkopen.2023.45050
Open Access: This is an open access article distributed under the terms of the CCBYNCND License . © 2023 Chin MH et al. JAMA Network Open .
Corresponding Authors: Marshall H. Chin, MD, MPH, University of Chicago, 5841 S. Maryland Ave, MC2007, Chicago, IL 60637 ( [email protected] ); Lucila OhnoMachado, MD, PhD, MBA, Yale School of Medicine, 333 Cedar St, New Haven, CT 06510 ( [email protected] ).
Author Contributions: Dr Chin had full access to all of the data in the study and takes responsibility for the integrity of the data and the accuracy of the data analysis.
Concept and design: Chin, AfsarManesh, Bierman, Chang, ColónRodríguez, Duran, Fair, HernandezBoussard, Hightower, Jain, Jordan, Konya, R.H. Moore, Rodriguez, Shaheen, Srinivasan, Umscheid, OhnoMachado.
Acquisition, analysis, or interpretation of data: Chin, Bierman, Chang, Dullabh, Duran, HernandezBoussard, Hightower, Jain, Jordan, Konya, R.H. Moore, T.T. Moore, Rodriguez, Snyder, Srinivasan, Umscheid, OhnoMachado.
Drafting of the manuscript: Chin, Bierman, Dullabh, HernandezBoussard, Hightower, Jordan, T.T. Moore, Rodriguez, Shaheen, Snyder, Srinivasan, OhnoMachado.
Critical review of the manuscript for important intellectual content: Chin, AfsarManesh, Bierman, Chang, ColónRodríguez, Duran, Fair, HernandezBoussard, Hightower, Jain, Jordan, Konya, R.H. Moore, T.T. Moore, Shaheen, Umscheid, OhnoMachado.
Obtained funding: Bierman, Chang, Dullabh, Duran, Jain.
Administrative, technical, or material support: Chin, Bierman, Chang, ColónRodríguez, Duran, Fair, Jain, Jordan, Konya, R.H. Moore, T.T. Moore, Rodriguez, Shaheen, Snyder, Srinivasan, Umscheid, OhnoMachado.
Supervision: Duran, Umscheid.
Conflict of Interest Disclosures: Dr Chin reported receiving grants or contracts from the Agency for Healthcare Research and Quality (AHRQ), the California Health Care Foundation, the Health Resources and Services Administration, Kaiser Foundation Health Plan Inc, the Merck Foundation, the PatientCentered Outcomes Research Institute, and the Robert Wood Johnson Foundation; and receiving personal fees for advisory board service from the US Centers for Medicare & Medicaid Services, Bristol Myers Squibb Company, Blue Cross Blue Shield, the US Centers for Disease Control and Prevention, and the American College of Physicians outside the submitted work. Dr Chin also reported serving as a member of the Families USA Equity and Value Task Force Advisory Council, the Essential Hospitals Institute Innovation Committee, the Institute for Healthcare Improvement and American Medical Association National Initiative for Health Equity Steering Committee for Measurement, the National Committee for Quality Assurance Expert Work Group (on the role of social determinants of health data in health care quality measurement), and The Joint Commission Health Care Equity Certification Technical Advisory Panel outside the submitted work. Dr Chin also reported being a member of the National Advisory Council of the National Institute on Minority Health and Health Disparities (NIMHD), the Health Disparities and Health Equity Working Group of the National Institute of Diabetes and Digestive and Kidney Diseases, and the National Academy of Medicine Council. Finally, Dr Chin reported receiving honoraria from the Oregon Health Authority and the Pittsburgh Regional Health Initiative and meeting and travel support from America’s Health Insurance Plans outside the submitted work. Dr AfsarManesh reported being employed by and holding equity in Oracle outside the submitted work, and their spouse is employed by and holds equity in Amgen. Dr Dullabh reported receiving grants from the AHRQ during the conduct of the study. Dr Hightower reported serving as cofounder and chief executive officer of Equality AI outside the submitted work. Dr Jordan reported engaging with this article as part of regular work duties as an employee of the American Medical Association. Dr Rodriguez reported receiving grants from the AHRQ during the conduct of the study. Dr Snyder reported receiving a federal contract from the US Department of Health and Human Services (to NORC at the University of Chicago) during the conduct of the study. Dr Srinivasan reported funding for this work under a contract (to NORC at the University of Chicago) from the AHRQ during the conduct of the study. No other disclosures were reported.
Funding/Support: This work was supported by funding from the AHRQ and the NIMHD. Dr Chin was supported, in part, by grant P30DK092949 from the National Institute of Diabetes and Digestive and Kidney Diseases to the Chicago Center for Diabetes Translation Research. Dr HernandezBoussard was supported, in part, by grant UL1TR003142 from the National Center for Advancing Translational Sciences of the National Institutes of Health (NIH). Dr OhnoMachado was supported, in part, by grants U54HG012510 and RM1HG011558 from the NIH.
Role of the Funder/Sponsor: Coauthors from the Agency for Healthcare Research and Quality and the National Institute on Minority Health and Health Disparities participated in the design and conduct of the study; collection, management, analysis, and interpretation of the data; preparation, review, or approval of the manuscript; and decision to submit the manuscript for publication.
Disclaimer: The findings and conclusions in this document are those of the authors, who are responsible for its content, and do not necessarily represent the views of the Agency for Healthcare Research and Quality, the Office of the National Coordinator for Health Information Technology, the Office of Minority Health, the National Institute on Minority Health and Health Disparities, the National Institutes of Health, or the US Department of Health and Human Services. No statement in this report should be construed as an official position of the Agency for Healthcare Research and Quality, the Office of the National Coordinator for Health Information Technology, the Office of Minority Health, the National Institute on Minority Health and Health Disparities, the National Institutes of Health, or the US Department of Health and Human Services. The thoughts and ideas expressed in this article are those of the authors and do not necessarily represent official American Medical Association policy. The thoughts and ideas expressed in this article are those of the authors and do not necessarily represent the views or policies of their employers or other organizations associated with the authors.
Meeting Presentation: This work was presented, in part, at an Agency for Healthcare Research and Quality virtual meeting (Opportunity for Feedback: Principles to Address the Impact of Healthcare Algorithms on Racial and Ethnic Disparities in Health and Healthcare); May 15, 2023; and at a symposium (Reconsidering Race in Clinical Algorithms: Driving Equity Through New Models in Research and Implementation) organized by the Doris Duke Foundation in partnership with the Gordon and Betty Moore Foundation, the Council of Medical Specialty Societies, and the National Academy of Medicine; June 27, 2023; Washington, DC.
 Register for email alerts with links to free fulltext articles
 Access PDFs of free articles
 Manage your interests
 Save searches and receive search alerts
IMAGES
VIDEO
COMMENTS
A description of the algorithm in English and, if helpful, pseudocode. At least one worked example or diagram to show more precisely how your algorithm works. A proof (or indication) of the correctness of the algorithm. An analysis of the running time of the algorithm. Remember, your goal is to communicate.
The lectures slides are based primarily on the textbook: Algorithm Design by Jon Kleinberg and Éva Tardos. AddisonWesley, 2005. Some of the lecture slides are based on material from the following books: Introduction to Algorithms, Third Edition by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. MIT Press, 2009.
Homework •Written Homework: Each has 34 problems.Solutions must be typeset, not handwritten! •Oral Homework: Collaborate in groups of three and present your solutions to a TA •Programming Problems: Zero or one of these on each homework. Submitted via Autolab. •Officially recommended/supported languages are C++ and Python •We will also try to accept C, Java, OCaml, Rust, SML
General Advice. to approach the problems on t. the homework:Look over the problems early. Algorithm design takes time, and even simple alg. ithms can be surprisingly tricky to develop. We suggest reading over all. he problems as soon as the homework goes out. Starting the night before is a particularly bad idea in this class, where insights ...
This specialization is an introduction to algorithms for learners with at least a little programming experience. This course is not an introduction to programming, and it assumes that you have basic programming skills in a language such as Python, Java, or C. There are several outstanding free online courses that teach basic programming.
Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divideandconquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimumcost spanning tree, connected components, topological sort, and shortest paths. ... Homework 5 (released 11/4 ...
General advice: Here are a few pieces of general homework advice: Read the submission instructions and policies above. Read the submission instructions and policies above. Seriously, do it. Look over the problems early. Algorithm design takes time, and even simple algorithms can be surprisingly tricky to develop.
COS 521: Advanced Algorithm Design Homework 1 Due: Sun, April 7 Collaboration Policy: You may collaborate with other students on these problems. Collaboration is limited to discussion of ideas only, and you should write up the solutions entirely on your own and list your collaborators as well as cite any references (book, paper, etc.) you may ...
CS580 Algorithm design and analysis. Schedule (subject to change) Jan. 9 Lecture 1 (Slides). Introduction. The stable matching problem. [Read Chapter 1 of Algorithm Design]. Homework 0. Jan. 11 Lecture 2 (Slides).
More and Improved Homework Problems  This edition of The Algorithm Design Manual has twice as many homework exercises as the previous one. Exercises that proved confusing or ambiguous have been improved or replaced. Degree of difficulty ratings (from 1 to 10) have been assigned to all problems. SelfMotivating Exam Design  In my algorithms ...
in algorithm design becomes properly modeling your application, more so than becoming intimate with the details of the actual algorithm. This focus ... Design Manual has twice as many homework exercises as the previous one. Exercises that proved confusing or ambiguous have been improved or replaced. Degree of diﬃculty ratings (from 1 to 10 ...
COMPSCI330 Design and Analysis of Algorithms Assignment 1 Due Date: Wednesday, January 22, 2020 Guidelines Describing Algorithms If you are asked to provide an algorithm, you should clearly de ne ... (3 points out of 60 for this homework). LATEX is preferred, but answers typed with other software and converted to pdf is also accepted. Please ...
COS 521: Advanced Algorithm Design Homework 4 Due: Mon, May 10 Collaboration Policy: You can collaborate in groups of at most two students. If you do refer to any sources, indicate this on your homework. 1. Given a graph G(V;E), de ne the sparsest cut to be (G) = min SˆV jE(S;S )j jSjjS j Consider the following LP min X (i;j)2E xij xij = xji ...
In the class we will see classical examples of algorithms design including graph algorithms, data structures and Linear Programming. The goal of this course is to familiarize undergraduate students with algorithm design techniques that can be generalized to many application areas. Course Information. Homework
Algorithm. [webster.com] A procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves repetition of an operation. [Knuth, TAOCP] An algorithm is a finite, definite, effective procedure, with some input and some output.
The readerfriendly The Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference, and ...
The textbook assumes knowledge of discrete math (especially induction) and basic data structures and algorithms (especially recursion) consistent with the prerequisite courses CS 173 and CS 225 at Illinois. (See the for more details.) For a thorough overview of prerequisite material, I strongly recommend the following resources: Building Blocks ...
Course Text: Algorithm Design by Jon Kleinberg and Éva Tardos. The text is available at Water Street Books or online. Course Description. ... The homework counts significantly toward your grade. I expect you will discuss the problems with members of the class, but I expect you will not discuss the solutions, nor will you write up solutions ...
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior.
Advanced Algorithm Design Princeton University . Instructors: Mark Braverman, Matt Weinberg . TAs: Linda Cai, Zhou Lu . ... Homework: Homeworks will be posted below when they become available. Here is a LaTeX template you may use for the homework, and here is a short guide to LaTeX. Feel free to visit office hours for help installing/setting up ...
We've partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn with a combination of articles, visualizations, quizzes, and coding challenges.
Now, with expertverified solutions from Algorithm Design 1st Edition, you'll learn how to solve your toughest homework problems. Our resource for Algorithm Design includes answers to chapter exercises, as well as detailed information to walk you through the process step by step. With Expert Solutions for thousands of practice problems, you ...
Understanding Algorithm Design 1st Edition homework has never been easier than with Chegg Study. Why is Chegg Study better than downloaded Algorithm Design 1st Edition PDF solution manuals? It's easier to figure out tough problems faster using Chegg Study. Unlike static PDF Algorithm Design 1st Edition solution manuals or printed answer keys ...
HyattDenesik's work focuses primarily on the survivable network design problem of edge connectivity augmentation. In this, additional connections should be added to an existing network by an algorithm. The advantage of the added connections is that when a single node fails, the overall connectivity of the network remains intact.
The panel heard from a group of national and international thought leaders involved in algorithm design, development, implementation, and oversight during a 2day hybrid public meeting and received feedback on draft principles from patient and community representatives and the public during a subsequent virtual meeting. 12 These perspectives ...