Algorithms course

An Algorithms Course with Minimal Prerequisites



Here you will find lecture notes and assignments for an algorithms course, prepared by Adam Sheffer.

The course was built in a way that requires minimal background and prerequisites. The only requirements are:
  • Basic programming background: being comfortable with loops, if-else statements, and recursion.
  • No mathematical knowledge beyond calculus is required. However, the course is aimed at people who are comfortable with mathematical/abstract thinking.
In particular, the course does not require knowledge in advanced programming (such as OOP), data structures, graph theory, linear algebra, or probability.

This does not mean that the course is easy - one should be prepared to spend time on the material before getting used to algorithmic thinking. The assignments may also require a significant amount of thinking and frustration. This is the way one gains a deeper understanding of the subject.


The secret behind Google's algorithm: Pigeons.

Lecture notes

Click on the topic name to get to the pdf of the lecture notes.

# Topic Consists of
1 Introduction What is in this course. Motivation. Grading details not relevant to people who do not take this course with Adam.
2 Running Times Worst case analysis, asymptotic running time including O()-notation, binary search.
3 Sorting Selection sort, Merge sort, the Divide and Conquer approach and recurrence relations, a stock market problem, a lower bound for sorting algorithms.
4 BFS Introduction to graphs and basic graph notation, the shortest paths problem, the BFS algorithm, shortest paths graphs, an algorithm for checking bipartiteness.
5 Spanning Trees Spanning tree, minimum spanning trees, Prim's algorithm, Kruskal's algorithm.
6 Shortest paths The weighted shortest paths problem, Dijkstra's algorithm, the Bellman-Ford algorithm, finding an arbitrage, checking if systems of linear inequalities have solutions.
7 Matchings Bipartite graphs, matchings, finding a bipartite maximum matching using augmenting paths, stable marriage theorem.
8 Network Flow Flow networks, the Ford-Fulkerson algorithm, the min-cut max-flow theorem, finding disjoint paths and Menger's theorem, finding a bipartite maximum matching using network flow.
9 Dynamic Programming Cutting steel rods, longest increasing subsequence, similarities in DNA sequences, max weighted independent set in a tree, travelling salesperson problem.
10 Greedy Algorithms Transporting materials, the knapsack problem, lecture scheduling, Data compression (Huffman codes).
11 Error Correcting Codes Error detection and error correction, linear codes, check matrices, Hamming codes.
12 Cryptography Asymmetric cryptography, Diffie-Hellman key exchange, RSA, modular arithmetic.

Assignments

# Title Topics
1 Assignment 1 Running times and binary search.
2 Assignment 2 Divide and conquer, merge sort, recurrence relations.
3 Assignment 3 Graphs and BFS.
4 Practice problems 1 Running times, binary search, sorting, recurrence relations, divide and conquer, BFS
5 Assignment 4 Graph coloring and MSTs.
6 Assignment 5 Lightest paths, Dijkstra, Bellman-Ford.
7 Assignment 6 Maximum matchings and the stable marriage theorem.
8 Practice problems 2 Minimum spanning trees, lightest paths, maximum matchings, stable matchings.
9 Assignment 7 Network flow, Min-cut max-flow theorem.
10 Assignment 8 Dynamic programming.
11 Assignment 9 Greedy algorithms, Huffman codes, knapsack problem.
12 Assignment 10 Linear codes, check matrices, Hamming codes .
13 Practice problems 3 Network flow, dynamic programming, greedy algorithms.
14 More practice problems Everything.