Basic Algorithms

Instructor Abhinav Tamaskar avt237@nyu.edu
Room 411 WWH
Office Hours T 12:00-13:00
And by appointment if you wish to see me at other times.
Room 411 WWH
Lectures MW 17:45-19:50 Room 101 WWH
Midterm exam July 2, 2018 Room 101 WWH
Final exam August 8, 2018 Room 101 WWH
Tutor
Office Hours
Deepika Khatri
T 17:30-20:30
S 15:30-17:30
dsk420@nyu.edu
Room 705 WWH

This course will be an introduction to the theory of algorithms. The main focus will be the design and mathematical analysis of algorithms. The course is structured to gain an understanding of various algorithms by problem solving and thus the focus will be on applications of algorithms to different situations such as machine learning, game design, artificial intelligence, network analysis and computer graphics, among others. The course is designed to enable you to understand the key concepts behind any new algorithmic challenges that you will see in the future and give you the basic tools to tackle them in an efficient manner.
There will be weekly homeworks, alternating between written and programming assignments, which will need around 5-7 hours of work to be put into them.

Prerequisites:
Familiarity with one of the following object oriented programming languages for the programming assignments - C++, Python, Java.
Familiarity with data structures such as - Lists, Arrays, Queues, Stacks, Trees.
Mathematical maturity to be able to follow proofs for analysis.

Recommended textbooks:
Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein (CLRS).
Algorithm Design, Kleinberg & Tardos (KT).

Syllabus

Algorithm design techniques

These are broad categories that we use to classify algorithms and are by no means exhaustive:

  • Recursion
  • Greedy
  • Divide and conquer
  • Dynamic programming
  • Brute force (exhaustive search)
  • Backtracking (depth first search, smart exhaustive search)
  • Randomized

Algorithm analysis techniques

Most of these techniques are used in conjunction with one another and will require some mathematical maturity to understand and use to the fullest extent:

  • Asymptotic and worst case complexity
  • Recurrence relations
  • Recursion tree & master theorem
  • Probabilistic methods
  • Amortized (average case) complexity

Special topics with applications to various fields (if we get enough time)

  • NP-Completeness
  • Approximation algorithms
  • Heuristic Algorithms
  • Optimization and Markov chain Monte Carlo (MCMC) algorithms

Homework and Quizzes

Written Assignments

The written assignments will require rigorous solutions which give clean and simple explanations. Each solution will be judged on the clarity, correctness and succinctness of the explanation. A design of an algorithm requires proof of correctness and a proof of runtime for full credit along with a clear explanation of the algorithm. Pseudocodes are not necessary but if you just write a pseudocode without any explanation then you will receive zero credit for the answer.

Programming Assignments

Programming assignments will involve moderate amounts of coding with each assignment requiring you to code the solution to a small algorithmic challenge that will be hosted on HackerRank. Each code will be small, around 150-200 lines, but will require a good understand of the underlying algorithm and will be tested for correctness and speed.
There is no limit to the number of times you can submit your code and there will be no penalty incurred for the number of times you submit. The score posted on the leaderboard will be your final score.
Helper instructions for compiling and running the programs on your own computer. It is recommended to get familiar with the terminal.
compiling_instructions.txt

Quizzes

There will be pop-quizzes in class that will test your understanding of the material with small puzzles. These quizzes will generally last around 5-10 minutes and the solutions will be given out after the quizzes are over. You are not allowed to collaborate in the quizzes.
# Quiz link Quiz solution
1 Quiz 1 Quiz 1 - Solution
2 Quiz 2 Quiz 2 - Solution

Grading Policy

Weighting

Problem sets (written assignments) 20%
Self evaluation of problem sets 10%
Programming assignments 15%
Quizzes 5%
Midterm 20%
Final 25%
Class participation 5%

Collaboration policy

For all the assignments (written and programming) you are encouraged to discuss with your peers and consult other supplementary material if necessary, but the final written solution must be your own. For each solution that you discussed or looked at extra materials for hints, you are required to mention it in your solution. This will not incur any penalty but if noticed otherwise by the graders it might bring about into question your academic integrity and there might be more serious repercussions.
For most other incidents the standard CIMS academic integrity policy applies.

Lecture notes and extra readings

# Topics covered Notes Extra reading Date
1 Introduction to algorithms and their uses.
Binary search trees and AVL trees. Augmentation and range update.
lec1.pdf
avlTree.cc
avl_solution.java
avl_tree_range_update_example.txt
CLRS-12; CLRS-14:1,3;
May 21, 2018
2 Continuing augmentation.
More recursion using Fibonacci numbers. Time complexity in terms of input size in bits, modular artihmetic, matrix algebra, repeated squaring.
lec2.pdf
fibonacci.cc
CLRS-31:1,3,6; Appendix-D; May 23, 2018
3 Modular arithmetic continued.
Euclid's algorithm, Extended Euclid's algorithm, congruence relations.
lec3.pdf
CLRS-31:2,3,4; May 30, 2018
4 Priority queues, binary heaps, in-place heapsort.
Introduction to dynamic programming. Change-making problem, 0/1 knapsack problem.
lec4.pdf
CLRS-6; CLRS-15; June 4, 2018
5 Dynamic programming continued.
Needleman–Wunsch (gene alignment) algorithm, optimal BSTs, longest increasing subsequence.
lec5.pdf
CLRS-15; June 6, 2018
6 Divide and Conquer.
Mergesort, counting inversions, Quicksort, Quickselect.
Recursion tree analysis, master theorem.
lec6.pdf
CLRS-4; CLRS-7; CLRS-9:3; June 11, 2018
7 Divide and Conquer continued.
Closest pair of points, convex-hull of points, Karatsuba, FFT: Cooley-Tukey algorithm (depending on time).
lec7.pdf
CLRS-33:3,4; KT-5:5,6; CLRS-30; June 13, 2018
8 Graph algorithms.
Graph representations, BFS, DFS, topological sorting.
lec8.pdf
CLRS-22:1,2,3,4; June 18, 2018
9 Strongly connected components, SCC-DAG, Kosaraju-Sharir algorithm. lec9.pdf
CLRS-22:5; June 20, 2018
10 Minimum spanning tree, Prim's algorithm, Kruskal's algorithm. lec10.pdf
CLRS-23; June 25, 2018
11 Shortest path algorithms, Dijsktra's algorithm, Floyd-Warshall algorithm. lec11.pdf
CLRS-24:2,3,4,5; CRLS-25:1,2; June 27, 2018
12 Midterm Exam July 2, 2018
13 Midterm solutions.
Problem solving techniques: multi-source dijkstra, edge based analysis, code presentation.
closest_special.cc July 9, 2018
14 Bridges in graphs, cut vertices.
Problem solving: Complex algorithms using Kruskals and bridges.
edges_type_MST.cc July 11, 2018
15 Introduction to probability theory. lec15.pdf
probability_primer (Prof.Victor Shoup)
July 16, 2018
16 Randomized quicksort. lec16.pdf
July 18, 2018
17 Randomized quickselect.
Las Vegas vs Monte Carlo algorithms.
Greatest half divisor, Karger's algorithm for minimum cut.
lec17.pdf
July 23, 2018
18 Karger-Stein algorithm for minimum cut using branching amplification. lec18.pdf
July 25, 2018
19 P vs NP. Decision vs Search problems. Phase transitions in problems.
Erdős–Rényi model for random graphs. Phase tansition for graph connectivity in random graphs.
lec19.pdf
July 28, 2018
20 Coupon collectors problem. Analysis using Chebyshev's inequality.
Introduction to hashing. Universal hash families.
lec20.pdf
July 30, 2018
21 ε-universal hashing. Rolling Hash.
Pattern matching using rolling hash.
Longest common substring using rolling hash.
lec21.pdf
August 1, 2018
22 TBD TBD August 6, 2018
23 Final Exam August 8, 2018