113-1 Introduction to Algorithms
Announcements.
[10/1] Program Assignment III is announced. Due: 10/20 (Sun) 23:59.
[ Notes to Read ] (updated, 10/6) for Segment Trees.
[10/1] HW3 is announced. Due: 10/17 (Thu) 5pm.
[9/17] Program Assignment II is announced. Due: 10/6 (Sun) 23:59.
[ Notes to Read ] (updated, 9/18) for Randomized Quicksort and etc.
To turn-in your HW,
bring it to the class or EC242 during the lecture time.To turn-in your programs,
login the [ NYCU-OJ ] system using your account for the NYCU portal.
Topics
Topics
Slides & Lecture Notes
Slides & Lecture Notes
W1
-------------
9/3 (Tue)
9/5 (Thu)
W1
-------------
9/3 (Tue)
9/5 (Thu)
Comparison-Based Sorting Algorithms
Comparison-Based Sorting Algorithms
Sorting in O(n^2) and O(n log n) time
Sorting in O(n^2) and O(n log n) time
Asymptotic Notations
Asymptotic Notations
-- Program Assignment I is announced. Due: 9/22 (Sun) 23:59 --
[ Notes to Read ] - Graham-Scan and etc.
-- Program Assignment I is announced. Due: 9/22 (Sun) 23:59 --
[ Notes to Read ] - Graham-Scan and etc.
W2
-------------
9/10 (Tue)
9/12 (Thu)
W2
-------------
9/10 (Tue)
9/12 (Thu)
More on Sorting Algorithms
More on Sorting Algorithms
Ω(n log n)-Time Lower-bound
for Comparison-based sorting algorithms,
Ω(n log n)-Time Lower-bound
for Comparison-based sorting algorithms,
Sorting Algorithms in O(n) time.
Sorting Algorithms in O(n) time.
Solving Recurrences
Solving Recurrences
** Program Assignment I - an introduction **
** Program Assignment I - an introduction **
-- Program Assignment II is announced. Due: 10/6 (Sun) 23:59 --
[ Notes to Read ] (updated 9/18) - Randomized Quicksort and etc.
-- Program Assignment II is announced. Due: 10/6 (Sun) 23:59 --
[ Notes to Read ] (updated 9/18) - Randomized Quicksort and etc.
W4
-------------
9/24 (Tue)
9/26 (Thu)
W4
-------------
9/24 (Tue)
9/26 (Thu)
Divide-and-Conquer
Divide-and-Conquer
Fast Fourier Transform (FFT)
Fast Fourier Transform (FFT)
-- Program Assignment III is announced. Due: 10/20 (Sun) 23:59 --
[ Notes to Read ] (updated, 9/18) for Segment Trees.
-- Program Assignment III is announced. Due: 10/20 (Sun) 23:59 --
[ Notes to Read ] (updated, 9/18) for Segment Trees.
W6
-------------
10/8 (Tue)
W6
-------------
10/8 (Tue)
Balanced Binary Tree Structures
Balanced Binary Tree Structures
Heap and HeapSort
Segment Tree
Heap and HeapSort
Segment Tree
-- The remaining content & slides are not finalized yet and are subject to change --
-- The remaining content & slides are not finalized yet and are subject to change --
W7
-------------
10/15 (Tue)
10/17 (Thu)
W7
-------------
10/15 (Tue)
10/17 (Thu)
(Balanced) Binary Search Trees (BSTs)
(Balanced) Binary Search Trees (BSTs)
Treap, Red-Black Tree
Treap, Red-Black Tree
Hashing
Hashing
W8 - 10/22
W8 - 10/22
*** Midterm Exam ***
*** Midterm Exam ***
Greedy Algorithms and General Proving Strategies
Greedy Algorithms and General Proving Strategies
W9 - 10/29,31
W9 - 10/29,31
Dynamic Programming
Dynamic Programming
-- ProgHW - IV --
-- ProgHW - IV --
W10 - 11/5,7
W10 - 11/5,7
Amortized Analysis
Amortized Analysis
Elementary Graph Algorithms
Elementary Graph Algorithms
W11 - 11/12,14
W11 - 11/12,14
Biconnected Components & Articulation Points
Biconnected Components & Articulation Points
Strongly Connected Components
Strongly Connected Components
-- ProgHW - V --
-- ProgHW - V --
W12 - 11/19,21
W12 - 11/19,21
Disjoint Set Operation
Disjoint Set Operation
Minimum Spanning Tree
Minimum Spanning Tree
W13 - 11/26,28
W13 - 11/26,28
The Shortest Path Problem
The Shortest Path Problem
-- ProgHW - VI --
-- ProgHW - VI --
W14 - 12/3,5
W14 - 12/3,5
Maximum Flow & Minimum Cut
Maximum Flow & Minimum Cut
W15 - 12/10,12
W15 - 12/10,12
String Algorithms
String Algorithms
NP-Completeness and Reductions
NP-Completeness and Reductions
W16 - 12/17
W16 - 12/17
*** Final Exam ***
*** Final Exam ***