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).

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

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

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

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.

# | Assignment link | Due Date | Solutions |
---|---|---|---|

1 | Homework 1 | June 13 at 1700hrs | Homework 1 - Sample Solutions |

2 | Homework 2 | June 20 at 1700hrs | Homework 2 - Sample Solutions |

3 | Homework 3 | June 27 at 1700hrs | Homework 3 - Sample Solutions |

4 | Homework 4 | July 18 at 1700hrs |
Homework 4 - Sample Solutions flower_fields.cc |

5 | Homework 5 | July 30 at 1700hrs | Homework 5 - Sample Solutions |

6 | Homework 6 | Aug 6 at 1700hrs |
Homework 6 - Sample Solutions equiv_substrings.cc |

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

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

# | Assignment link | Due Date |
---|---|---|

1 | Assignment 1 - Fords Dilemma (range_query_sample_io.zip) | June 6, 17:00 EDT |

2 | Assignment 2 - Hijacking the fees (range_update_sample_io.zip) | June 6, 17:00 EDT |

3 | Assignment 3 - Mutating the NBA (sequence_alignment_sample_io.zip) | June 20, 17:00 EDT |

4 | Assignment 4 - Smelling the cosmos (karatsuba_polynomial_sample_io.zip) | June 27, 17:00 EDT |

5 | Assignment 5 - Making Felix Felicis (lexically_smallest_topsort_sample_io.zip) | July 18, 17:00 EDT |

6 | Assignment 6 - Crossing Khazad-dûm (cycle_detection_sample_io.zip) | July 18, 17:00 EDT |

7 | Assignment 7 - Through the forest of Fangorn (shortest_colored_path_sample_io.zip) | July 18, 17:00 EDT |

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 |

Problem sets (written assignments) | 20% |

Self evaluation of problem sets | 10% |

Programming assignments | 15% |

Quizzes | 5% |

Midterm | 20% |

Final | 25% |

Class participation | 5% |

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.

For most other incidents the standard CIMS academic integrity policy applies.

# | 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 |
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 |