Instructor: Sharma Thankachan, Email: sharma.thankachan@ucf.edu, Office Hours: Monday 10:30 am – 11:45 am (or by appoinment) at HEC 207
TA: Amirreza Samiei, Email: samiei.amirreza@Knights.ucf.edu, Office Hours: Thursday 3:00 pm – 4:15 pm and Friday 2:00 pm - 3:15 pm (or by appoinment) at HEC 308
Grader: Tiger Sachse, Email: tgsachse@Knights.ucf.edu Office Hours: Friday 11:00 am – 12:30 pm (or by appoinment) at HEC 308
University Course Catalog Description: Algorithm design and analysis for tree, list, set, and graph data models; algorithmic strategies and applications, and algorithmic complexity analysis; sorting and searching; practical applications.
Course Overview: Review of mathematical background, sorting and searching, algorithm design techniques such as divide and conquer, greedy approach, dynamic programming, worst case and average case analysis techniques, data structures such as binary search trees and various heaps, graph algorithms, string algorithms and geometric data structures, advanced topics (P, NP, NP-Complete, etc) if time permits.
Course Objectives: Understanding of various types of techniques for algorithms design and (run time) analysis in more detail that CS 1. Also, a gentle introduction to several advanced data structures.
Text Books and Materials: Many excellent text books are available online for free. For example, Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein or Introduction to the Design and Analysis of Algorithms by Anany Levitin. I will also be uploading sldies and extra reading materials here.
Lecture | Topics | Related Files |
1 | Getting Started | [pdf] |
2 | Growth of Function | [pdf] |
3 | Recurrences | [pdf] |
4 | Heapsort | [pdf] |
5 | Quicksort | [pdf] |
** | Probability and Expectation | [pdf] |
6 | Sorting in Linear Time | [pdf] |
7 | Lower Bound on Comparison Sorts | [pdf] |
8 | Order Statistics | [pdf] |
9 | Binomial Heaps | [pdf] |
10 | Greedy Algorithms | [pdf] |
11 | Graph Algorithms I (BFS) | [pdf] |
12 | Graph Algorithms II (DFS) | [pdf] |
13 | Graph Algorithms III (Topological Sort) | [pdf] |
14 | Strongly Connected Components | [pdf] |
15 | Minimum Spanning Trees | [pdf] |
16 | Single-Source Shortest Paths | [pdf] |
Grading Policy: Two Midterms – 15% each; Final Exam – 20%; Assignments - 40%; Class Participation - 10% and Challenge Problems (with extra credits). Grading will be on the curve. However, a score of X% or better is guaranteed to receive grade Y or better, where (X,Y) is in {(90, A), (80, A-), (70, B+), (60, B), (50, B-), (40, C+), (30, C)} and below 30 is F. Tip for success: attend lectures and take notes.