back to cs312-syllabus
Basic informal definitions: Algorithms, Computational Problems, Data Structures, Computational Complexity, Problem Instances and Problem Solutions. Models of Computation and Cost criteria. Example: computation of the factorial of large integers.
Timing the execution of a method in a Java program. The Sorting Problem. InsertionSort. The Gauss formula. Analysis of InsertionSort. Discussion on the order of growth.
The Sieve of Eratosthenes. The factoring problem. Applications: the RSA cryptosystem. Min and Max. Linear and Binary Search.
Modular exponentiation.
Order of growth and asymptotic notation.
Modular Arithmetics. Computation of the GCD: the Euclidean Algorithm.
Mergesort. Analysis of Mergesort. Divide and Conquer algorithms.
Divide and Conquer recurrence relations. The master Theorem.
Lower bound to the computational complexity of the (comparison-based) Sorting problem.
Randomized QuickSort. The QuickSort equation and its solution.
Heaps. Heapsort. Analysis.
Recursion revisited. Memoization. Introduction to Dynamic Programming. The Matrix-chain Multiplication Problem.
Data Structures. Abstract data types. Specification and Implementation. Java interfaces. Stacks, Queues: Array and Linked List implementation.
Priority Queues: heap-based implementation.
Maps and Hash Tables. Binary Search Trees.