Data Structures and Algorithms
Course Outline
​
A. Overview of Data Structures and Algorithms
B. Basic Programming Concepts: Variables, Arrays, Loops, Functions
C. Performance Analysis: Time and Space Complexity, Big O Notation
II. Fundamental Data Structures
A. Arrays and Strings
B. Linked Lists: Singly Linked Lists, Doubly Linked Lists
C. Stacks and Queues: Implementation and Applications
D. Hash Tables: Implementation and Applications
III. Recursion
A. Introduction to Recursion: Function Calls, Base Case, Recursive Case
B. Examples and Applications of Recursion
C. Analysis of Recursive Algorithms
IV. Sorting and Searching Algorithms
A. Basic Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort
B. Advanced Sorting Algorithms: Merge Sort, Quick Sort, Heap Sort, Radix Sort
C. Searching Algorithms: Linear Search, Binary Search, Hashing
V. Trees and Graphs
A. Binary Trees: Operations and Traversal
B. Binary Search Trees: Operations and Balancing
C. Heaps: Operations, Heap Sort
D. Graphs: Representation, Depth-First Search, Breadth-First Search
E. Tree and Graph Problems: Pathfinding, Topological Sort
VI. Advanced Data Structures
A. Sets and Maps
B. Tries
C. Balanced Trees: AVL Trees, Red-Black Trees
D. Disjoint Set Union
VII. Advanced Algorithms
A. Greedy Algorithms
B. Dynamic Programming: Memoization, Tabulation
C. Divide and Conquer
D. Network Flows: Maximum Flow, Minimum Cut
VIII. String Algorithms
A. String Matching: Naive Algorithm, Rabin-Karp, KMP Algorithm
B. Regular Expressions and Finite Automata
C. Text Compression and Huffman Coding
IX. Computational Geometry
A. Basic Concepts: Points, Lines, Polygons
B. Algorithms: Convex Hull, Line Intersection, Closest Pair
X. NP-Complete Problems and Approximation Algorithms
A. Introduction to P, NP, NP-Complete, and NP-Hard Problems
B. Examples of NP-Complete Problems: Traveling Salesman, Knapsack, SAT
C. Approximation Algorithms
XI. Parallel and Distributed Algorithms
A. Basic Concepts: Concurrency, Synchronization, Deadlocks
B. Models of Parallel Computation: PRAM, MapReduce
C. Examples of Parallel Algorithms
​
Textbook: "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
I. Introduction to Data Structures and Algorithms
We will discuss the overview of data structures and algorithms, revisit some basic programming concepts, and introduce the concept of performance analysis in computer science.
​
A. Overview of Data Structures and Algorithms
​
Data structures and algorithms are fundamental concepts in computer science that give us the means to efficiently store, organize, and manipulate data.
​
A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. They are the building blocks of any software/application.
​
An algorithm, on the other hand, is a step-by-step procedure to solve a particular problem. A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently.
​
B. Basic Programming Concepts: Variables, Arrays, Loops, Functions
​
Let's briefly review some basic programming concepts:
​
Variables: Variables are containers for storing data values. In a programming language, variables are used to store information to be referenced and manipulated in a computer program.
Arrays: An array is a data structure consisting of a collection of elements, each identified by an array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.
​
Loops: Loops are used in programming to repeat a specific block of code until a certain condition is met.
Functions: A function is a group of related statements that perform a specific task. Functions help break our program into smaller and modular chunks. As our program grows larger and larger, functions make it more organized and manageable.
​
C. Performance Analysis: Time and Space Complexity, Big O Notation
​
Performance analysis is a vital process in computer science to understand the efficiency of an algorithm or a computer program. This process focuses on two key resources, time and space.
​
Time Complexity: It measures the amount of time an algorithm takes to run as a function of the size of the input to the program.
​
Space Complexity: It measures the maximum amount of memory taken by an algorithm to complete its execution.
​
Big O Notation: It describes the performance or complexity of an algorithm. Big O notation specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
​
Consider a simple linear search algorithm, where we are searching for a particular value in an array. The worst-case time complexity is O(n), where n is the number of elements in the array. This is because, in the worst-case scenario, we have to look at each element in the array once.