Analysis of Algorithms

Unit 2: Divide and Conquer Algorithms

Unit 3: Graphs 1 (BFS, DFS, Greedy)

Unit 4: Graph 2 (Shortest Path, Minimum Spanning Tree)

Unit 5: Dynamic Programming and Randomized Algorithms

Unit 6: Linear Programming

Unit 7: Limits of Computation

Unit 8: Limits of Computation 2

Topics

Unit 2

Techniques for the Analysis of Algorithms

Lower/Upper bounds analysis

Summation Techniques

Recurrence relations

Estimating upper and lower bounds

Searching

Finding maximum value

State space algorithms

Finding the ith best element

Optimal sorting

Amortized Analysis

Divide and Conquer Algorithms

Master Theorem

Matrix Multiplications

Binary Search

Merge Sort

FFT

Unit 3: Graphs 1

Graph terminology and representation

Describe directed, undirected, labeled graphs and subgraphs

Be able to describe vertices and edges

Graph data structures

Be able to implement graphs as data structures

Graph traversals

Depth-first search

Breadth-first Search

Topological sort

Greedy Algorithms

Understand the basic characteristics and operation of greedy algorithms

Unit 4: Graphs 2

Describe Shorted Path Problems

Bellman-Ford

Dijkstra

Define Minimum-cost spanning tree and approaches to implement it

Understand and apply algorithms to solve shortest path problems

Prim’s algorithm

Kruskal’s algorithm

Articulate the characteristics of ‘greedy’ algorithms

Unit 5: Dynamic Programming

Dynamic Programming

Apply dynamic programming as an algorithm design strategy.

Articulate how dynamic programming differs from a divide and conquer approach.

The Knapsack Problem

Implement a dynamic programming algorithm to solve the knapsack problem.

Randomized Algorithms (Shaffer’s Textbook)

Describe the features and functioning of randomized algorithms.

Unit 6: Linear Programming

Recognize and be able to define the differences between the P, NP, and Co-NP classes

Unit 7: Limits of Computation

Recognize and be able to define the differences between the P, NP, and Co-NP classes

Recognize and be able to describe reductions and how they are used in determining if a problem is NP hard or NP complete

Define what a ‘hard’ problem is from the perspective of algorithm analysis

Identify problems that are NP complete

Resources

Textbooks

Data Structures and Algorithm Analysis

This is the homepage for the paper (and PDF) version of the book Data Structures & Algorithm Analysis by Clifford A. Shaffer. The most recent version is Edition 3.2.0.10, dated March 28, 2013. You probably don't want to be here. March 2013 was rather a long time ago in the life of a Computer Science textbook.

https://people.cs.vt.edu/~shaffer/Book/

Data Structures and Algorithm Analysis

This is a penultimate draft of our soon to appear textbook. For more information, visit http://www.mhhe.com/dasgupta.

https://book.huihoo.com/pdf/algorithms/

GitHub - eherbold/berkeleytextbooks: Textbooks (EE)CS majors at Berkeley would find helpful

Textbooks and notes EE(CS) majors at Berkeley would find helpful. I plan to add resources for: x = In Progress; o = Completed Also: I may post some LaTeX templates I've used during my time here for courses like CS70, EE16A, CS170 ,etc. These will be on a separate branch if they do get uploaded.

GitHub - eherbold/berkeleytextbooks: Textbooks (EE)CS majors at Berkeley would find helpful

https://github.com/eherbold/berkeleytextbooks

GitHub - eherbold/berkeleytextbooks: Textbooks (EE)CS majors at Berkeley would find helpful

Sedgewick & Wayne's Course (Princeton University)

Focuses on implementations (using Java), away from proofs and math details

Algorithms, 4th Edition

essential information thatevery serious programmerneeds to know aboutalgorithms and data structures This booksite contains tens of thousands of files, fully coordinated with our textbook and also useful as a stand-alone resource. It consists of the following elements: Excerpts. A condensed version of the text narrative, for reference while online. Lectures.

Algorithms, 4th Edition

https://algs4.cs.princeton.edu/home/

Algorithms, 4th Edition

Algorithms, Part I

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free.

Algorithms, Part I

https://www.coursera.org/learn/algorithms-part1

Algorithms, Part I

Algorithms, Part II

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free.

Algorithms, Part II

https://www.coursera.org/learn/algorithms-part2

Algorithms, Part II

Tim Roughgarden Course (Stanford)

Tim Roughgarden's Online Courses

Topics include: instance optimality; parameterized analysis and condition numbers; stable clustering; models of data (pseudorandomness, locality, diffuse adversaries, etc.); distributional models; smoothed analysis; planted and semi-random graph models; exact recovery (compressive sensing, LP decoding). Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, linear programming, hashing, etc.

Tim Roughgarden's Online Courses

http://timroughgarden.org/videos.html

https://learning.edx.org/course/course-v1:StanfordOnline+CSX0003+1T2020/home

The Algorithms Illuminated Book Series

"Look through the Table of Contents and you might conclude that this is just another algorithms book. Don't be fooled. What makes this book special - what makes this book the first of its kind - is Tim Roughgarden's singular ability to weave algorithm design with pedagogical design.

The Algorithms Illuminated Book Series

http://algorithmsilluminated.org/

The Algorithms Illuminated Book Series

MIT

Very theoretical (pure computer science theory and discrete math)

Design and Analysis of Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare

Course Description This is an intermediate algorithms course with an emphasis on teaching techniques for the design and analysis of efficient algorithms, emphasizing methods of application. Topics include divide-and-conquer, randomization, dynamic programming, greedy algorithms, incremental improvement, complexity, and cryptography.

Design and Analysis of Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare

https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/

Design and Analysis of Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare

MIT 6.046J Design and Analysis of Algorithms, Spring 2015

View the complete course: http://ocw.mit.edu/6-046JS15 Instructors: Erik Demaine, Srinivas Devadas, Nancy Ann Lynch 6.046 introduces students to the design o...

MIT 6.046J Design and Analysis of Algorithms, Spring 2015

https://www.youtube.com/playlist?list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

MIT 6.046J Design and Analysis of Algorithms, Spring 2015

MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

http://videolectures.net/mit6046jf05_introduction_algorithms/

MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

Summary of MIT Introduction to Algorithms course

As you all may know, I watched and posted my lecture notes of the whole MIT Introduction to Algorithms course. In this post I want to summarize all the topics that were covered in the lectures and point out some of the most interesting things in them.

Summary of MIT Introduction to Algorithms course

https://catonmat.net/summary-of-mit-introduction-to-algorithms

Summary of MIT Introduction to Algorithms course

Berkley

Main | CS 61B Fall 2020

Computer Science 61B: Data Structures

Main | CS 61B Fall 2020

https://fa20.datastructur.es/

Main | CS 61B Fall 2020

Jonathan Richard Shewchuk

Jonathan Shewchuk Professor in Computer Science University of California at Berkeley Office 529 Soda Hall Computer Science Division University of California at Berkeley Berkeley, California 94720-1776 (510) 642-3936 [(510) NICE ZEN] Office hours (510 Soda) Mondays, 5:10-6 pm, 529 Soda Hall Wednesdays, 9:10-10 pm, 411 Soda Hall Home 1988 Martin Luther King Jr.

Jonathan Richard Shewchuk

http://people.eecs.berkeley.edu/~jrs/

Jonathan Richard Shewchuk

Computer Science 61B - Fall 2006

Due to a planned power outage on Friday, 1/14, between 8am-1pm PST, some services may be impacted.

Computer Science 61B - Fall 2006

https://archive.org/details/ucberkeley-webcast-PL4BBB74C7D2A1049C

Computer Science 61B - Fall 2006

Skiena’s Lectrures and Book (Stony Brook University)

The Algorithm Design Manual

Steven Skiena 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.

The Algorithm Design Manual

https://www.algorist.com/

The Algorithm Design Manual

Skiena's Audio Lectures

Below are audio, video and lecture sides for 1997 and 2007. Since the lectures are 10 years apart some of the topics covered by the course have changed. The 1997 lectures have a better quality video and audio than the 2007, although the 2007 covers the newer material and has better lecture notes.

Skiena's Audio Lectures

https://www3.cs.stonybrook.edu/~algorith/video-lectures/

Skiena's Audio Lectures

My channel holds video lectures of the classes I've taught in the past For more information about me, please visit http://www.cs.stonybrook.edu/~skiena/ You can view my books at https://www.amazon.com/Steve-Skiena/e/B000APVVYO Steven Skiena is a Distinguished Teaching Professor of Computer Science at Stony Brook University.

https://www.youtube.com/user/StevenSkiena

Steven Skiena

Skiena's Algorithms

Introduction to mathematical analysis of a variety of computer algorithms including searching, sorting, matrix multiplication, fast Fourier transform, and graph algorithms. Time and space complexity. Upper-bound, lower- bound, and average-case analysis. Introduction to NP completeness.

Skiena's Algorithms

https://www3.cs.stonybrook.edu/~skiena/373/videos/

Skiena's Algorithms

Optimization

Welcome to the Northwestern University Process Optimization Open Textbook. This electronic textbook is a student-contributed open-source text covering a variety of topics on process optimization. If you have any comments or suggestions on this open textbook, please contact Professor Fengqi You. Northwestern University Open Text Book on Process Optimization Acknowlegement

https://optimization.mccormick.northwestern.edu/index.php/Main_Page

Moustafa Ibrahim Courses

https://www.udemy.com/course/skills-algorithms-cpp/

https://www.udemy.com/course/skills-algorithms-cpp2/

https://www.udemy.com/course/cpp-4skills-oop-free/

https://www.udemy.com/course/dscpp-skills/

Junior Training Sheet V7.0 - >>

Info Problem Solving Sheet,This google sheet is created by Dr Mostafa Saad Ibrahim. Overall ~950 problems for newcomers to problem solving. The goal of this sheet is to enhance algorthmic probem solving skills for both programming competitions and interviws preparations Currenet Version V7.0,<a ...

Junior Training Sheet V7.0 - >>

https://docs.google.com/spreadsheets/d/1iJZWP2nS_OB3kCTjq8L6TrJJ4o-5lhxDOyTaocSYc-k/edit#gid=84654839

Junior Training Sheet V7.0 - >>

Other

Competitive programming books

Guide to Competitive Programming is a printed book, published by Springer. It is based on Competitive Programmer's Handbook, but also discusses more advanced topics. You can buy the book, for example, through Springer or Amazon.

https://cses.fi/book/index.php

Competitive programming books

🔥1st edition, June 2019 🔥 (Amazon links:US,UK,DE,ES,FR,IT,JP) This web page contains a free electronic version of my self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998. Publication. A black-and-white paperback edition of the textbook can be purchased fromAmazon for $27.50.

https://jeffe.cs.illinois.edu/teaching/algorithms/

Søren Sandmann Pedersen

In computer science and sometimes mathematics, big-O notation is used to talk about how quickly a function grows while disregarding multiplicative and additive constants. When classifying algorithms, big-O notation is useful because it lets us abstract away the differences between real computers as just multiplicative and additive constants.

Søren Sandmann Pedersen

http://ssp.impulsetrain.com/big-o.html

Algorithms with Attitude

Algorithms, data structures, and their analysis. I am a professor at San Jose State University. There are a lot of freaking David Taylors out there, even a handful if you limit it only to computer scientists, so I go by David Scot Taylor.

Algorithms with Attitude

https://www.youtube.com/c/AlgorithmswithAttitude/playlists

Algorithms with Attitude

Share your videos with friends, family, and the world

https://www.youtube.com/playlist?list=PLl0KD3g-oDOEbtmoKT5UWZ-0_JbyLnHPZ

Edu

Data Structures & Algorithms

These are videos from an introductory class to algorithms and data structures taught as flipped classroom. I made a basic version of the course publically ac...

Data Structures & Algorithms

https://www.youtube.com/playlist?list=PLMDFPuH4ZxUFGC5ICUu8xstOxQIizMgX2

Data Structures & Algorithms

The drawing app to express, grasp, and organize your thoughts and ideas

https://okso.app/showcase/data-structures

Ok! So...

Algorithms Analysis and Design from scratch

Algorithms Analysis and Design from scratch

https://cloudnativebasecamp.com/courses/algo-01/

Algorithms Analysis and Design from scratch

Know Thy Complexities!

Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.

https://www.bigocheatsheet.com/

Know Thy Complexities!

Algorithm Implementations and Software

The fast, Open Source and easy-to-use solver

SolverFactory factory = SolverFactory.create(...); // My domain specific class as input MyRoster problem = ...; Solver solver = factory.buildSolver(); // My domain specific class as output MyRoster solution = solver.solve(problem); for (MyShift shift : solution.getShifts()) { // Each shift is now assigned to an employee assertNotNull(shift.getEmployee()); }

The fast, Open Source and easy-to-use solver

https://www.optaplanner.org/

The fast, Open Source and easy-to-use solver

The Modern Algorithmic Toolbox (CS168), Spring 2022

5/29: Greg's Monday OH will be moved to Wednesday, 3-4pm. They will be held under the tent right outside of the classroom (CEMEX). Feel free to drop by if you want to discuss your final miniproject, or anything else even vaguely related to the course. 5/24: Here is mini-project 9, withimages.

The Modern Algorithmic Toolbox (CS168), Spring 2022

https://web.stanford.edu/class/cs168/index.html

visualising data structures and algorithms through animation - VisuAlgo

VisuAlgo was conceptualised in 2011 by Dr Steven Halim as a tool to help his students better understand data structures and algorithms, by allowing them to learn the basics on their own and at their own pace.

visualising data structures and algorithms through animation - VisuAlgo

https://visualgo.net/en