back to cs312-syllabus
Basic informal definitions: Algorithms, Computational Problems, Data Structures, Computational Complexity, Problem Instances and Problem Solutions. Example: formulation of the Sorting Problem.
Mathematical preliminaries: the Gauss formula. InsertionSort. Analysis of InsertionSort. Discussion on the order of growth. Min and Max. Searching keys in sequences: linear and binary search.
Order of growth and asymptotic notation.
Computation of the modular exponentiation. The repeated squaring method.
Modular arithmetic, gcd and congruence equations. Applications: the RSA cryptosystem.
More on Modular arithmetic. Equivalence relations and congruence relations.
Evaluation of polynomials: the Horner method.
Midterm 1.
Review of the Midterm examination. The Knapsack problem.
Mergesort. Analysis of Mergesort. Divide and Conquer algorithms.
Lower bound to the computational complexity of comparison-based algorithms for the Sorting problem.
Divide and Conquer recurrence relations. The master Theorem.
Higher order linear recurrence relations. Proof of the master Theorem.
Computation of the square root of a real number using Newton's method. Randomized QuickSort. The QuickSort equation.
Preparation to the midterm examination.
Heaps. Heapsort. Analysis.
Midterm 2.
Data Structures. Abstract data types. Specification and Implementation. Java interfaces. Stacks, Queues: Array and Linked List implementation. Priority Queues: heap-based implementation.
The BinarySearchTree data structure. Linked Tree based implementation. Basic algorithms on binary search trees: inorder, postorder and preorder traversals. Insertion and deletion.