February 14th |
Intro, algorithms "definition". Minimum, maximum search, Selection sort. Order of magnitude (big-O, Omega, Theta), |
February 21st |
Binary search. Comparison based sorts: BubbleSort, InsertionSort,MergeSort,QuickSort. Lower bound for the number of comparisons. Key manipulation sorts: BinSort, RadixSort |
February 28th |
Representing graphs: adjacency matrix, adjacency list, running times of elementary operations. DFS, Directed Acyclic Graphs (DAGs), recognizing DAGs using DFS. Comparison of DFS and BFS (provided BFS occurs already in ITC2) |
March 6th |
Topological sort, shortest and longest paths in DAGs, introduction of Dynamic Programming |
March 13th |
Dynamic programming, Knapsack problem, maximal sum subinterval |
March 20th |
Dijkstra's Algorithm, (its idea, it is correct, it can be implemented in O(n2)) compare with BFS
The material of Midterm 1 is up to here. |
March 27th |
Data structures: binary trees, transversals of binary trees, heap, HeapSort, Dijkstra using heap, binary search trees, intro of Red-Black trees
|
April 3rd |
Spring break |
April 10th |
Red-Black trees, 2-3-trees, B-trees. Hash |
April 17th |
Running time of Kruskal's algorithm, Union-FindSet, Prim's algorithm: correctness, running time, also with heap |
April 18th 8:00-10:00 A.M. |
Midterm 1. |
April 24th | Decision problems, effective witness, complexity classes P, NP, coNP and their connection |
April 30th 18:00-20:00 P.M. |
Repeat Midterm 1. |
May 1st |
National Holiday, no classes |
May 8th |
Karp reduction, NP-completeness |
May 15th |
NP-completeness |
May 23rd 8:00-10:00 A.M. |
Midterm 2. |
May 30th |
Repeat Midterm 2. |
June 5th |
RepeatRepeat Midterm |