algorithm design homework

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 write-up 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 write-up 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.

SOE-YCSALGORITHMS1

Stanford School of Engineering

In this course you will learn several fundamental principles of algorithm design. You'll learn the divide-and-conquer 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: "Big-oh" 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 3rd-grade 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: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost 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.3-4.5 Dasgupta-Papadimitriou-Vazirani 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.1-2 --> (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:00-4:20)	5/12 Homework 5 released
5/15 Dynamic Programming and shortest paths: Bellman-Ford, Floyd-Warshall 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 Ford-Fulkerson (draft). Read: Ch. 26.1-3 (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 closed-book. In the midterm, you are allowed to bring one letter-sized double-sided page of notes, that you have prepared yourself . In the final, you are allowed to bring two letter-sized double-sided 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 min-cut/max-flow .
• 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, big-O, and recurrences.
• Section 3 : Randomized algorithms.
• Section 4 [ problems ] [ solutions ]: Universal hash functions, randomly built binary search trees.
• YouTube series on red-black 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/14-10/19) Solutions
• Recitation 4 (10/21-10/26) Solutions
• Recitation 5 (11/4-11/9) Solutions
• Recitation 6 (11/11-11/16) Solutions
• Recitation 7 (11/18-11/30) Solutions
• Recitation 8 (12/2-12/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/Addison-Wesley Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms , McGraw-Hill 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 high-quality 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 reader-friendly 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 well-known 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 algorithm-implementation 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 30-min sessions where I will be on piazza trying to answer all questions posted (First two will be Thursday 3-3:30 pm and Friday 10:30-11: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 in-class 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 late-pass 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 24-hour 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 Worst-case 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, Union-Find
• 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, NP-completeness, Polynomial-time 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	Mid-Term 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 best-selling 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 best-selling 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 self-study, while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students. The reader-friendly 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, willy-nilly; 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/Algorithm-design-homework

Folders and files.

Name		Name
1 Commit

Repository files navigation

Algorithm-design-homework.

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 Min-Cut
9/7	LP Rounding I
9/9	LP Rounding II
9/14	LP Duality
9/16	Semi-Definite 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	Johnson-Lindenstrauss
10/12	Locality-Sensitive Hashing and Approximate Nearest Neighbors
10/14	Low-Rank 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)
• Route-finding (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-θ (Big-Theta) notation (Opens a modal)
• Functions in asymptotic notation (Opens a modal)
• Big-O notation (Opens a modal)
• Big-Ω (Big-Omega) 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)
• Linear-time 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)
• Linear-time 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

Breadth-first search

• Breadth-first search and its uses (Opens a modal)
• The breadth-first search algorithm (Opens a modal)
• Challenge: Implement breadth-first search (Opens a modal)
• Analysis of breadth-first 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 Hyatt-Denesik 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 Hyatt-Denesik 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

Hyatt-Denesik'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, Hyatt-Denesik 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, Hyatt-Denesik 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, Hyatt-Denesik provided the first better-than-2 approximation for Flexible Vertex Connectivity, and also improved the currently best-known approximation factor for Flexible Edge Connectivity. Hyatt-Denesik’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 decision-making 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 (COVID-19)
• 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 Well-being
• 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 e-Cigarettes
• 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 , Afsar-Manesh 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 trade-offs; 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 trade-offs, and accountability for equity and fairness.

Health care algorithms, defined as mathematical models used to inform decision-making, 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 risk-stratified 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 data-driven, probability-based algorithms such as those using artificial intelligence and machine learning approaches. The panel’s core guiding principles also apply to rules-based 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 machine-based system that can, for a given set of human-defined 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 2-day 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 decision-making. 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 algorithm-driven 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? Trade-offs 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 trade-offs explicit, transparent, and explainable. Thus, solutions to advance health equity with health care algorithms require ethical, technical, and social approaches—there is no simple cookie-cutter technical solution. 43 , 45

Technical methods for improving fairness in algorithms can be divided into stages of modeling: preprocessing (eg, repair biased data set), in-processing (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 co-development) 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 trade-offs 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 CC-BY-NC-ND 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 Ohno-Machado, 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, Afsar-Manesh, Bierman, Chang, Colón-Rodríguez, Duran, Fair, Hernandez-Boussard, Hightower, Jain, Jordan, Konya, R.H. Moore, Rodriguez, Shaheen, Srinivasan, Umscheid, Ohno-Machado.

Acquisition, analysis, or interpretation of data: Chin, Bierman, Chang, Dullabh, Duran, Hernandez-Boussard, Hightower, Jain, Jordan, Konya, R.H. Moore, T.T. Moore, Rodriguez, Snyder, Srinivasan, Umscheid, Ohno-Machado.

Drafting of the manuscript: Chin, Bierman, Dullabh, Hernandez-Boussard, Hightower, Jordan, T.T. Moore, Rodriguez, Shaheen, Snyder, Srinivasan, Ohno-Machado.

Critical review of the manuscript for important intellectual content: Chin, Afsar-Manesh, Bierman, Chang, Colón-Rodríguez, Duran, Fair, Hernandez-Boussard, Hightower, Jain, Jordan, Konya, R.H. Moore, T.T. Moore, Shaheen, Umscheid, Ohno-Machado.

Obtained funding: Bierman, Chang, Dullabh, Duran, Jain.

Administrative, technical, or material support: Chin, Bierman, Chang, Colón-Rodríguez, Duran, Fair, Jain, Jordan, Konya, R.H. Moore, T.T. Moore, Rodriguez, Shaheen, Snyder, Srinivasan, Umscheid, Ohno-Machado.

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 Patient-Centered 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 Afsar-Manesh 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 Hernandez-Boussard was supported, in part, by grant UL1TR003142 from the National Center for Advancing Translational Sciences of the National Institutes of Health (NIH). Dr Ohno-Machado 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 full-text articles
• Access PDFs of free articles
• Manage your interests
• Save searches and receive search alerts