• First examples
• Run-time analysis
• $\mathcal{O}$-notation
• Divide and conquer

• Comparison sorts
• Counting Sort, Radix sort
• Median and order statistics

• Dynamic Programming: RodCutting, Longest Common Subsequence, Knapsack
• Greedy: Interval scheduling, Huffman Code

• Graph: basics
• Classical algorithms: Kruskal, Prim, Dijkstra, Floyd-Warshall, etc.
• P vs NP, NP completeness

Homework (due Tuesday 12 September)

Send me a Jupyter file by email (nguyen.khoi@nyu.edu) with the following exercises solved.

• 2-2. Bubble sort (Cormen et al., 2022, p. 46): use Python instead of pseudo-code
• 2-3. Horner (Cormen et al., 2022, p. 47): use Python instead of pseudo-code
• Leetcode problem

Homework (due Tuesday 12 September)

Send me a Jupyter file by email (nguyen.khoi@nyu.edu) with the following exercises solved.

• 2-2. Bubble sort (Cormen et al., 2022, p. 46): use Python instead of pseudo-code
• 2-3. Horner (Cormen et al., 2022, p. 47): use Python instead of pseudo-code
• Leetcode problem

Homework due next Monday

• Implement Gauss and Karatsuba's algorithm in Python so that given two arrays of integers, it results a the digits of the product of the two numbers associated with the arrays.

  karatsuba([1, 3], [1, 2]) # returns [1, 5, 6]

• Using a plotting library such as matplotlib, plot the time both algorithms take as a function of n random digits. Roughly when is your Karatsuba implementation faster?
• Use your Karatsuba implementation and a divide-and-conquer approach to write an algorithm that computes the $n$th power of a number. You may not use

  power([1, 3, 4, 2], 2) # return 1342**2

Homework due Tuesday

• Implement Gauss and Karatsuba's algorithm in Python so that given two arrays of integers, it results a the digits of the product of the two numbers associated with the arrays.

  karatsuba([1, 3], [1, 2]) # returns [1, 5, 6]

• Using a plotting library such as matplotlib, plot the time both algorithms take as a function of n random digits. Roughly when is your Karatsuba implementation faster?
• Use your Karatsuba implementation and a divide-and-conquer approach to write an algorithm that computes the $n$th power of a number. You may not use

  power([1, 3, 4, 2], 2) # return 1342**2

• Radix sort: stable counting sort on last, then penultimate, etc.
• Running time: $\mathcal{O}(n\log k)$
• Why is stability important in sorting?

Dynamic programming

• Break down problem into overlapping subproblems
• Subproblems are often created via substrings or subarrays (often prefixes/suffixes)
• Recursion and memoization to reduce to smaller problems (top-down) and ultimately to base cases
• Notion of order (bottom-up)
• Running time: number of subproblems $\times$ non-recursive work

Homework

• Homework 1 and 2 due today
• Homework 3 on dynamic programming due next monday