This course is designed to teach you, at the graduate level, algorithm design and analysis paradigms, advanced data structures and their use in efficient algorithms, graph algorithms, the theory of NP-completeness, and some specialized topics (to be determined based on student input). At the end of the semester you should:

• be familiar with the algorithms and algorithmic techniques covered,
• be able to argue correctness and analyze the running time of a given algorithm,
• be able to design new algorithms for new situations, using as building blocks the algorithms and techniques learned,
• be able to prove a problem is NP-complete using reduction.

The text book for this course is Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein., 3rd ed., MIT Press, 2009. (also called as CLRS).

Almost all the topics covered in the class are present in CLRS. If they are not, the instructor will point to the appropriate resources. There are a number of other good books that are available for free. My favorite is the book by Dr.Jeff Erickson that can be found here.

The tentative list of topics to be covered in the class include:

• Review of Asymptotic Analysis and Growth of Functions
• Recurrences and Sorting Algorithms
• Basic data structures such as trees, heaps and hashes
• Graph Algorithms and Maximum Flow Networks
• Algorithmic techniques: Recursion, greedy, divide and conquer, dynamic programming
• Algorithms for String Matching
• NP Completeness

Your grade will be based on the following weights:

• Quizzes: 24%
  • There will be 4 short quizzes during the course to test your understanding of the concepts taught.
  • They will generally be allotted 15-20 minutes at the end of the class period.
  • They will be announced at least a week in advance.

• Midterm: 30%
  • There will one midterm exam during the semester covering first half of the course.
  • There will be no make up exams except under extenuating circumstances!

• Final : 30%
  • There will one non-comprehensive final exam during the semester covering second half of the course.
  • There will be no make up exams except under extenuating circumstances!

• Anki Project : 6%
  • Create Anki Deck for topic selected

• Programming Project : 10%
  • Details to be announced.

Make-ups: Make-ups for graded activities may be arranged if your absence is caused by illness or work/personal emergency. A written explanation (including supporting documentation) must be submitted to the Instructor. If the explanation is acceptable, an alternative to the graded activity will be arranged. Make-up arrangements must be arranged prior to the scheduled due date.

• Algorithms & Data Structures (CSE 2320) or equivalent
• Theoretical Computer Science (CSE 3315) or equivalent