Introduction to ECE264: Data Structures and Algorithms

ECE264: Data Structures and Algorithms I (DSA 1) Course Introduction

The Basics Lectures during the fall 2023 semester will take place on Wednesdays from 11 am 12:50 pm Lectures will take place in Rm. 105 If we are forced to be remote at any point during the semester, those lectures would take place via Teams My Cooper webpage: http://faculty.cooper.edu/sable2 From there, you can fine a link to the course webpage I ll post relevant course information including the syllabus and all assignments on the course webpage Some general course policies can also be found using the "policies" link on my Cooper webpage (not the course webpage) My email: carl.sable@cooper.edu

The Textbook "Data Structures and Algorithm Analysis in C++" by Mark Allen Weiss Please get the 4thEdition (updated for C++11) The same book will be used for DSA II Other references (not required): "Algorithms", by Sedgewick, the 3rdedition "Introduction to Algorithms", the 3rdedition, by Cormen, Leiserson, Rivest, and Stein

Grading and Workload The grading breakdown for the course is: Three programs (accounting for 10%, 20%, and 25% of the grade, respectively) Three problem sets (each accounting for 15% of the grade) All programs will be written in C++ C++ is a superset of C It is important to gain experience with an object-oriented language C++ is one of the most widely used programming languages in industry There are no tests or quizzes in this course

What are Data Structures and Algorithms? Informal definitions: Data structures are constructs for organizing data Algorithms are methods of solving a problem Or: An algorithm is a well-defined sequence of computational steps that transforms structured input into structured output If you take DSA 2, we will see a formal definition of an algorithm near the end of that course These two topics are almost always taught together The data structures and algorithms that we learn about in this class can be implemented in any modern programming language Most of the time in class, I will use pseudo-code, which is informal

How is this Related to Software Engineering? Software engineering deals with the planning and implementation of large, user- friendly, well-documented, robust, expandable systems as part of a team Related tasks include formalizing requirements, designing the system, implementing the program, documenting the product, testing, maintaining the system, etc. The process may be more traditional, involving a sequence of phases, or more modern, involving an agile method of development For larger systems, various types of software engineers (e.g., programmers, program managers, testers, etc.) work together The algorithms we cover in this class are used to implement small pieces of large systems Although small in terms of code size, these parts may be extremely important A large percentage a system's execution time may involve a small percentage of its code As a programmer, you will be using algorithms and data structures from this course very often, but you will be implementing them rarely

Choosing a Data Structure or an Algorithm Often, when you are given a programming task, there are many possible algorithms and data structures that would give the correct answer Example of a task for which this is true: sorting In general, if we are dealing with small amounts of data, the choice of algorithm might not be too important When dealing with huge amounts of data, however, it can be crucial Choosing the best algorithm often relies on a deep understanding of how the algorithm works as well as the specific properties of the problem you are solving There are problems for which no efficient solutions exist (e.g., NP-complete problems) There are also well-defined problems for which no algorithm exists at all; these unsolvable problems are said to be undecidable If you take DSA 2, you will learn about some of these advanced topics In DSA 1, we will typically be dealing with problems that do have efficient solutions

Evaluating Algorithms Generally, when we analyze the efficiency of an algorithm, we don't truly estimate time Instead, we estimate the number of computational steps The amount of actual time depends on the hardware, as well as other factors The number of computational steps depends on the algorithm and the input Typically, only the worst-case scenario is considered (this is called worst- case analysis); sometimes average-case analysis is used instead Often, Big-O notation, or one of a few other related notations, is used to analyze the efficiency of an algorithm We will learn about these notations in our next topic

The Selection Problem The selection problem: Choose the kthsmallest or largest element out of N elements (as if the N elements were sorted) Example: Determine the 250,000thlargest integer out of 1,000,000 integers According to the textbook (page 1), if a "simple algorithm" is used on a modern machine for k=15 million and N=30 million, this would take days I add: By "simple algorithm", they mean something such as a quadratic sort I further add: Using an efficient sort might take only a few seconds An implementation of an algorithm we will learn later in the course takes about one second

Hardware vs. Software For decades, the speed of hardware improved exponentially over time according to Moore s law Moore s law has slowed down in recent years, but performance improvements still occur due to other hardware improvements According to Moore s law, if you wait 15 to 20 years, any given implementation of an algorithm might run 1000 times faster If you spend more money today to obtain the fastest possible machine, an implementation might run 2 or 10 times faster Sometimes, coming up with a better algorithm can lead to an implementation that runs millions of times faster!