Room 411 WWH
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|
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.
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.
These are broad categories that we use to classify algorithms and are by no means exhaustive:
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:
|#||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
|5||Homework 5||July 30 at 1700hrs||Homework 5 - Sample Solutions|
|6||Homework 6||Aug 6 at 1700hrs||
Homework 6 - Sample Solutions
|#||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|
|Problem sets (written assignments)||20%|
|Self evaluation of problem sets||10%|
|#||Topics covered||Notes||Extra reading||Date|
Introduction to algorithms and their uses.
Binary search trees and AVL trees. Augmentation and range update.
||May 21, 2018|
More recursion using Fibonacci numbers. Time complexity in terms of input size in bits, modular artihmetic, matrix algebra, repeated squaring.
|CLRS-31:1,3,6; Appendix-D;||May 23, 2018|
Modular arithmetic continued.
Euclid's algorithm, Extended Euclid's algorithm, congruence relations.
||CLRS-31:2,3,4;||May 30, 2018|
Priority queues, binary heaps, in-place
Introduction to dynamic programming. Change-making problem, 0/1 knapsack problem.
||CLRS-6; CLRS-15;||June 4, 2018|
Dynamic programming continued.
Needleman–Wunsch (gene alignment) algorithm, optimal BSTs, longest increasing subsequence.
||CLRS-15;||June 6, 2018|
Divide and Conquer.
Mergesort, counting inversions, Quicksort, Quickselect.
Recursion tree analysis, master theorem.
||CLRS-4; CLRS-7; CLRS-9:3;||June 11, 2018|
Divide and Conquer continued.
Closest pair of points, convex-hull of points, Karatsuba
||CLRS-33:3,4; KT-5:5,6; CLRS-30;||June 13, 2018|
Graph representations, BFS, DFS, topological sorting.
||CLRS-22:1,2,3,4;||June 18, 2018|
|9||Strongly connected components, SCC-DAG, Kosaraju-Sharir algorithm.||
||CLRS-22:5;||June 20, 2018|
|10||Minimum spanning tree, Prim's algorithm, Kruskal's algorithm.||
||CLRS-23;||June 25, 2018|
|11||Shortest path algorithms, Dijsktra's algorithm, Floyd-Warshall algorithm.||
||CLRS-24:2,3,4,5; CRLS-25:1,2;||June 27, 2018|
|12||Midterm Exam||July 2, 2018|
Problem solving techniques: multi-source dijkstra, edge based analysis, code presentation.
|closest_special.cc||July 9, 2018|
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.||
probability_primer (Prof.Victor Shoup)
||July 16, 2018|
||July 18, 2018|
Las Vegas vs Monte Carlo algorithms.
Greatest half divisor, Karger's algorithm for minimum cut.
||July 23, 2018|
|18||Karger-Stein algorithm for minimum cut using branching amplification.||
||July 25, 2018|
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.
||July 28, 2018|
Coupon collectors problem. Analysis using Chebyshev's inequality.
Introduction to hashing. Universal hash families.
||July 30, 2018|
ε-universal hashing. Rolling Hash.
Pattern matching using rolling hash.
Longest common substring using rolling hash.
||August 1, 2018|
|22||TBD||TBD||August 6, 2018|
|23||Final Exam||August 8, 2018|