Advanced Algorithms and Data Structures Quiz

Course Team

• Instructor: Dr. Olena Syrotkina, Email: [email protected]
• Office Hours: Monday 2:45 PM - 4:15 PM, Wednesday 2:30 PM - 4:00 PM, Thursday 2:30 AM - 3:30 PM
• Office Location: 300 Ouellette Ave., Office 4004
• Preferred Communication: Teams
• Graduate Assistants: Ali Nakhaeisharif, Darpan Khanna, Sudharshan Sundararajan, Gurpartap Singh Ahluwalia and Abhishek Mahajan

Course Outline

• Covers advanced topics in algorithm design and analysis, programming techniques, advanced data structures, languages, compilers and translators, regular expressions, grammars, computing and intractability
• Participation in events is saved by registering on the attendance list or scanning a QR code

Assessments

• Random Lecture Quizzes (RLQ): Quizzes on lecture topics, multiple-choice questions, conducted randomly before or after class
• Final Project: Milestone report with a penalty for non-submission, presentation and Q&A during class

Textbooks

• Required: Introduction to Algorithms, fourth edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, The MIT Press, 2022.
• Required: Algorithm Design and Applications by M. Goodrich and R. Tamassia, Wiley, 2015.
• Required: Data Structures and Algorithms in Java, 6th Edition, by M. Goodrich and R. Charles E. Tamassia, Wiley, 2014.
• Optional: Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles, 5th Edition, by Narasimha Karumanchi, CareerMonk Publications, 2017.
• Optional: An Open Guide to Data Structures and Algorithms by Paul W. Bible and Lucas Moser, PALNI Press, 2023.

Introduction to Computing

• Refers to use of computers and electronic systems to process, store, retrieve, and manage data
• Includes calculations, problem-solving, and information processing
• Involves execution of instructions by a computer to perform tasks
• Algorithms are foundation of computational processes, and advanced computing concepts rely on their efficiency and effectiveness
• Examples of input sizes: size of an array, polynomial degree, number of elements in a matrix, number of bits in a binary representation of the input, vertices and edges in a graph

Comparing Algorithms

• Execution times: Not a good measure because it is specific to a particular computer
• Number of statements executed: Not a good measure because the number of statements varies with programming language and style of the programmer
• Ideal solution: Running time of an algorithm can be expressed as a function of the input size (i.e., f(n)) and these functions can be compared

Experimental vs Theoretical Analysis

• Experimental Analysis: Implementing the algorithm, running the program with varying inputs, keeping track of CPU time used, and plotting the results
• Limitations of Experimental Analysis: Dependent on hardware and programming language, requires implementation and debugging
• Theoretical Analysis: Focuses on analyzing function that expresses running time (f(n)) of an algorithm

Primitive Operations

• Basic computations performed by an algorithm
• Examples: evaluating an expression, assigning a value to a variable, indexing into an array, calling a method, returning from a method
• Take a constant amount of time in the RAM model (one unit of time or constant time)
• Independent of programming language

Case analysis

• Worst Case: The input that takes the longest amount of time to process