- 2023 Spring
- Instructor: Dov Kruger
- **Meeting Times and Office hours
- Resources
- Course Web Address ** Prerequisites** Recommended: CPE-552, EE-553 or good command of either C++ or Java
Applied Data Structures and algorithms is an intensive introduction to brilliant solutions to classical problems with wide application across computer programming. Using great solutions and approaches you can write programs that are far faster and more efficient. We cover:
- Analysis of algorithms (complexity)
- Dynamic arrays
- Linked lists, Stacks and Queues
- Trees: binary, RB Tree, BTree, Trie
- Hashing
- Sorting (Insertion, Quicksort, Heapsort, Mergesort)
- Searching (binary, golden mean)
- String algorithms including Boyer-Moore, finite state machines and LCS
- Families of optimal approaches to solve problems (like divide and conquer)
- Use dynamic programming to avoid redundant computation
- Use matrix algorithms to solve systems of linear equations in a numerically stable manner
- Use backtracking to search a large set of solutions
- Introduction to Graph Theory (DFS, BFS, Bellman-Ford, Floyd-Warshal, Prim, Kruskal, TSP)
- Solve classic number-theoretic problems like computing prime numbers, Eratosthenes’ sieve, Prime number wheel
- Compute Fermat and Miller-Rabin probabilistic prime number algorithms, learn about AKS
- Identify the theoretical and practical weaknesses in RSA encryption
- Numerical algorithms: root finding, interpolation, integration
After successful completion of this course, students will be able to
-
Analyze programs and algorithms and determine the complexity of the code
-
Identify the best possible performance based on limits to algorithmic efficiency * Write, debug, and test data structures
-
Apply the best data structure or algorithm for a particular purpose
-
Recognize and apply common approaches to high-performance such as divide-and-conquer
-
Independently research new algorithms based on knowledge of the fundamentals
-
Gain familiarity with other areas of computer algorithms for future growth and learning
- Analyze code to determine its complexity and determine whether it can be optimized
- Implement algorithms in C++ or Java
- Choose from a set of algorithms and select the most appropriate
- Work together in teams to solve problems
- Classes include slides and live coding. You are encouraged to actively participate.
- Required Text(s): Cormen, Leiserson, Rivest and Stein 3e (CLRS)
- Required Readings: materials in ref directory
- Other Readings: Papers available in ref directory
- Attendance: Attendance is crucial for an effective learning but will not be graded. Your work will speak for itself. For F1 visas however, attendance is required so I will take attendance at least once. This may be in the form of a quiz.
- Homework: Coding assignments will be submitted via canvas for individual single files, or via github.
Grades will be based on:
- Weekly homework problem sets to learn the algorithm (5%)
- Homeworks (15%)
- Mini projects (20%)
- Midterm (30%)
- Final Project (30%)
[Grading Policies] (https://github.com/stevensdeptece/DovKrugerCourses/grading.md) [Academic Honesty and Discipline] (https://github.com/stevensdeptece/DovKrugerCourses/academichonesty.md)
- Midterm ** 2023-TBD **
- Final Project ** 2023-05-?? **